GO语言学习进阶2：理解递归函数在栈里面的底层运行机制

大部分开发语言都支持递归函数，递归是一个可以自己调用自己的方法/函数，每次调用时传入不同的变量，可以帮助我们解决很多复杂的问题，让代码变得简洁化，如快速排序就是使用递归来实现的，速度超级快。

但是理解递归还是比较复杂的，理解递归前我们先要了解递归在内存栈的存储模型，首先，栈是一个后进先出(LIFO)结构（弹夹）由系统管理。当把数据放入栈时，我们把数据push进入；当从栈取出数据时，我们把数据pop出来。栈随着数据被压入或者弹出而增长或者减小。最新压入栈的项被认为是在“栈的顶部”。当从栈中弹出一个项时，我们得到的是位于栈最顶部的那一个。就像给弹夹上子弹，只能在顶部进行操作。

一、 堆与栈的区别：

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式。

1、栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制（cc++等容易产生内存泄漏）。

2、每个进程拥有的栈的大小要远远小于堆的大小。

3、堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。

4、堆都是动态分配的，没有静态分配的堆。栈有静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由操作系统进行释放，无需我们手工实现。

5、栈由操作系统自动分配，会在硬件层级对栈提供支持：压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由程序语言自带的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。

通过下面的代码理解一下堆与栈：

//fact 利用递归实现阶乘
func fact(n int) int {
	fmt.Println("入栈：", n) //打印n，以了解【栈】的后进先出
	if n == 1 {
		return 1 //输入的参数是1，直接返回1
	} else {
		return n * fact(n-1) //递归 存放在【栈】由操作系统自动分配释放
	}
}
func main() {
	var num = 5                          //存放在【堆】由GO语言运算符来完成申请
	fmt.Println(num, "的阶乘为：", fact(num)) //5*4*3*2*1=120
}

/*
入栈： 5
入栈： 4
入栈： 3
入栈： 2
入栈： 1
5 的阶乘为： 120
*/

二、递归需要遵守几个重要的原则：

1、每执行一个函数时，就会创建一个新的受保护的独立栈空间。

2、函数的局部变量也是独立的，不会相互影响。

3、递归必须向退出递归的条件逼近，否则将会无限循环报错。

4、当函数执行完成或者return，就会返回，遵守谁调用谁接收，系统并会立即销毁该函数。

下面是递归函数在栈里的示意图：

通过栈我们需要这样理解阶乘的运行：

入栈：5*（5-1）*（5-1-1）*（5-1-1-1）* 1

出栈：1 * 2 * 3 * 4 * 5

三、递归实现迷宫找路

我们可以使用递归模拟科幻电影《永无止境》里主角向多个方向找路的情况（分析需求如下）：

1、首先我们要定义一个地图，为了保证使用同一个地图我们要使用指针传递值。

2、没有走过的坐标=0；并设置障碍（值=1）；能走通的路=2；走过的路不通=3。

3、起点是左上面，始点是右下角，中间有墙，所以使用递归函数在wayMap的下、右、上、左的路径去探测 wayMap[8][8]==2 的地方为出路。

//mapShow 显示地图
func mapShow(wayMap [10][10]int) {
	for _, v := range wayMap {
		for _, v2 := range v {
			fmt.Print(v2, "   ")
		}
		fmt.Println()
	}
}

//letGo 通过递归探路
func letGo(wayMap *[10][10]int, x int, y int) bool {
	if wayMap[9][8] == 2 {
		fmt.Println("我成功走出来了~") //找到出口坐标
		return true
	}
	if wayMap[x][y] == 0 { //没有走过的坐标
		wayMap[x][y] = 2 //设置能走通的路径
		//根据起点和地图实际情况设置行走策略为：下 -> 右 -> 上 -> 左
		if letGo(wayMap, x+1, y) {
			return true //向下走通
		} else if letGo(wayMap, x, y+1) {
			return true //向右走通
		} else if letGo(wayMap, x-1, y) {
			return true //向上走通
		} else if letGo(wayMap, x, y-1) {
			return true //向左走通
		} else {
			wayMap[x][y] = 3 //此路不通
			return false
		}
	} else {
		return false //找到一堵墙，此路不通
	}
}
func main() {
	var wayMap [10][10]int
	//先把地图上、下、左、右都设置为1（墙）
	for i := 0; i < 10; i++ {
		wayMap[0][i] = 1 //地图上
		wayMap[9][i] = 1 //地图下
		wayMap[i][0] = 1 //地图左
		wayMap[i][9] = 1 //地图右
		if i < 5 {
			wayMap[3][i] = 1 //给迷宫第3行前面增加一些墙
		} else {
			wayMap[6][i] = 1 //给迷宫第6行后面增加一些墙
		}
	}
	wayMap[9][8] = 0     //定义出口位置
	letGo(&wayMap, 1, 1) //走迷宫,定义左上角为起始点
	mapShow(wayMap)      //显示运行路径结果
}

/*
	我成功走出来了~
	1   1   1   1   1   1   1   1   1   1
	1   2   3   3   3   3   3   3   3   1
	1   2   2   2   2   2   3   3   3   1
	1   1   1   1   1   2   3   3   3   1
	1   0   0   0   0   2   3   3   3   1
	1   0   0   0   2   2   3   3   3   1
	1   0   0   0   2   1   1   1   1   1
	1   0   0   0   2   0   0   0   0   1
	1   0   0   0   2   2   2   2   2   1
	1   1   1   1   1   1   1   1   2   1
*/

 画个图给人类看的：

当然可以测试这个递归是否准确，可以尝试一下把所有的路堵死试试，我们只需要设置：wayMap[4][5] = 1;wayMap[5][5] = 1;wayMap[6][5] = 1即可。

除非注明，网络人的文章均为原创，转载请以链接形式标明本文地址：https://www.55mx.com/post/91