golang数据结构与算法——递归、迷宫回溯和二叉树的遍历

---

一 递归

1.1 递归的概念

简单的说: 递归就是函数/方法自己调用自己,每次调用时传入不同的变量.第归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

使用递归函数最重要的三点：

• 递归就是自己调用自己。
• 必须先定义函数的退出条件，没有退出条件，递归将成为死循环。
• go语言递归函数很可能会产生一大堆的goroutine，也很可能会出现栈空间内存溢出问题。

1.2 快速入门

package main

import "fmt"

func test(n int) {
   
	if n > 2 {
   
		n--
		test(n)
	} else {
   
		fmt.Println("n=", n)
	}
}

func main() {
   
	n := 4
	test(n)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
n= 2

[Done] exited with code=0 in 3.936 seconds
1
2
3
4

示意图：

1.3 应用场景

• 各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大
  赛)
• 将用栈解决的问题–>第归代码比较简洁

1.4 递归需要遵守的重要原则

1. 执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)
2. 函数的局部变量是独立的，不会相互影响, 如果希望各个函数栈使用同一个数据，使用引用传递
3. 递归必须向退出递归的条件逼近【程序员自己必须分析】，否则就是无限递归，死循环了
4. 当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁

二 迷宫回溯问题

问题描述：

​ 有一个迷宫地图，其中地图中有一些不过达的位置（墙壁、障碍）。从一个起点开始，一步一步走到终点，如何找到一条到达的道路呢？

思路分析：

​ 利用二位数组来模拟迷宫地图，0表示没有走过的点，1表示墙壁，2表示走通的点，3表示走不通的点，按照自定义的寻路策略，遍历寻找路径，如果是死路则标示该路径走不通，回到起点，再重新找一条新路，以此类推，直到走通为止。这种方法又称作为回溯法（递归）。

代码实现：

package main

import "fmt"

// SetWay 寻找出路 i,j表示地图的坐标起点
func SetWay(myMap *[8][8]int, i, j int) bool {
   

	// 设置终点
	if myMap[6][6] == 2 {
   
		return true
	}

	if myMap[i][j] == 0 {
   
		// 假设可以走通
		myMap[i][j] = 2
		// 寻路策略：下右上左
		if SetWay(myMap, i+1, j) {
    // 下
			return true
		} else if SetWay(myMap, i, j+1) {
    // 右
			return true
		} else if SetWay(myMap, i-1, j) {
    // 上
			return true
		} else if SetWay(myMap, i, j-1) {
    // 左
			return true
		} else {
    // 死路
			myMap[i][j] = 3
			return false
		}
	}

	return false
}

// ShowMap 输出地图
func ShowMap(myMap [8][8]int) {
   
	for i := 0; i < 8; i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44