开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法—递归机制剖析】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9861
数据结构和算法—递归机制剖析
内容介绍：
一、引出递归
二、递归是什么
三、分析过程
四、总结
一、引出递归
前面内容的递归中没有涉及回溯问题，现在来看一个相对比较复杂的，涉及递归回溯的问题。有一个实际应用场景
小老鼠从左上角走到右下角，但是存在问题：中间的方格中可能存在障碍无法通过，并且小老鼠行走的路径有很多条选择，我们不知道小老鼠最终能到哪个位置，或者说并不知道哪条路最短，这就需要用递归来解决。
用这个应用场景引出递归，接下来先来看一下递归的应用概论。
递归是什么？
简单的讲，递归就是函数或者一个方法，自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。
二、递归快速入门
列举两个小案例，帮助大家理解递归，递归在讲函数时已经讲过，这里再给大家回顾一下递归调用机制
打印问题
阶乘问题
先以打印数字为例
package main
import(
“fmt”
)
func test(n int) {
if n > 2 {
n--
test(n)
}
fmt.Println(“n=”,n)
}
func main() {
n :=4
test(n)
}
代码中有一个函数 test，可以接受一个n值，如果这个n值大于二，n--，再调用自己，就是递归调用。
调用完后继续进行循环最终输出结果。
三、分析过程
分析过程：
画一个框可以理解它是一个内存，内存中有一部分是栈。栈中有一部分为主栈，栈中有一个变量为 n，n=4。
当我们的程序从主函数 func main(){n:=4 test(n)}开始执行时，执行 n=4，然后进行调用，这时会去开辟一个新的空间，我们可以理解成一个新的栈，但是它仍然是在大的栈里面。
在调用 test 的时候，会先对原值做一个保存，栈创建了一个新的空间，调用的函数的新的栈压在空间上面。
继续执行 func test(n int){}的代码，而此处的 n 也存在栈的一个空间中， n=4。但是两个空间的 n 不冲突，现在继续判断 n 是否>2，执行到 n--，注意 n--是对上方栈里的 n--，4减成了3。
之后又调用 test，又开辟了一个新栈，该新栈中也有一个 n，n=3。再判断是否>2，又执行 n--，该 n 变成2。又调用 test，这时 test 又根据函数调用的规则又开辟一个新的栈，n=2，再判断n是否>2，执行代码 fmt.Println(“n=”,n)，输出 n 等于2。
从栈顶开始依次往下不断执行代码。从 test 进去，往下执行，不断输出栈，输出完之后又继续往下面走，相当于从 test 进入，不断执行下面，当它把 n 等于3输出之后，到了主栈，主栈又返回。结果就是输出n=2 n=2 n=3
运行代码：
分析过程结束后，来运行代码查看结果，运行结果为 n=2 n=2 n=3。
再来做一个改变：
在代码 if 块增加 else，即
if n > 2 {
n--
test(n)
}else{
fmt.Println(“n=”,n)
}
先来分析：
主栈位置不变，在栈顶时 n=2，所以执行 else 语句，输出 n 等于2，一旦输出后栈顶往下，对第二个栈，是从 if 中的 test 进入，所以不会输出。到第三个栈也是从 if 中的 test 进入，也不会输出。
最后只输出 n=2
所以数据是独立的，代码也要根据实际情况执行，加了 else 输出的结果只有一个，栈顶输出2。
再尝试执行代码 ，结果显示 n=2
四、总结
以上内容回顾了递归调用的机制，
总结笔记：
首先提出一个递归应用场景，《迷宫的问题》，由迷宫问题引出了递推概论即方法自己调用自己。
例如显示目录数或者排序或者查找都是方法自己调用自己，因此引出递归。借助原先讲的案例打印问题进行回顾。
此外还有阶乘问题，快速入门的示意图。
快速入门的示意图如下
