网络人

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

Kwok: 2020-11-15 12:11:24 点击:2 评论: 0

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

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

一、 的区别:

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

1、堆的申请和释放工作由程序员控制(cc++容易产生内存泄漏)。

2、每个进程拥有的的大小。

3、由高到低

4、操作系统进行释放,无需我们手工实现。

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即可。

本文地址:http://m.neter8.com/go/91.html
标签:递归GO

本站推荐阅读

热门点击文章