75142913在线留言
GO语言学习进阶2:理解递归函数在栈里面的底层运行机制_Go语言_网络人

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

Kwok 发表于:2020-11-15 09:15:47 点击:48 评论: 0

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

但是理解递归还是比较复杂的,理解递归前我们先要了解递归在内存栈的存储模型,首先,栈是一个后进先出(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,就会返回,遵守谁调用谁接收,系统并会立即销毁该函数。

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

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

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

入栈: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
*/

 画个图给人类看的:

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

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

除非注明,网络人的文章均为原创,转载请以链接形式标明本文地址:https://www.55mx.com/post/91
标签:递归GOKwok最后编辑于:2020-11-15 12:15:24
0
感谢打赏!

《GO语言学习进阶2:理解递归函数在栈里面的底层运行机制》的网友评论(0)

本站推荐阅读

热门点击文章