算法图解｜递归算法和栈的应用

递归算法：

什么是递归呢？其实，递归就是函数自己调用自己来解决问题

我们用下面这个例子讲解一下递归的概念

开盒子找钥匙

有一天，你需要找一把开启宝库的钥匙，你知道这个箱子能给你一些线索，钥匙很可能在这个箱子里，

你知道钥匙一定在这些盒子里，你打开了发现，箱子里有盒子，盒子里还有盒子，钥匙到底在哪个盒子里面呢？

我们用算法来解决这个问题，为了找到这个钥匙，你将使用什么算法？

方法一：先发现但未打开的盒子和打开盒子又发现的盒子，处于同一优先级别上，随机选取盒子打开找钥匙

方法二：打开盒子如果发现盒子里还有盒子，那就继续打开这个盒子，一直到盒子里没盒子也没钥匙时，再向上找之前未打开的盒子打开

两种方法的伪代码：

后面这种方法中，便利用了递归算法，自己调用自己，从代码中看到，是不是递归的方法更加清晰一些。

特点：递归只是让解决方案更清晰，并没有性能上的优势。

基线条件和递归条件：

对于循环，我们都知道有一个循环条件，一旦不满足这个条件，算法会停止循环跳出。同理为了避免递归算法一直递归成无限循环，它也需要设置一定的停止条件。像找钥匙这个例子，如果没找到钥匙，但打开了所有的盒子，没有未打开的盒子，就是停止条件。

递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。

栈

栈是一种数据结构，它主要的特点是只能从一端插入和弹出，存储进栈的操作具有一定的顺序，先进后出，后进先出。

先介绍一下栈的调用，以下面这段程序为例：

当调用主函数greet（name）时，计算机将首先为该函数调用分配一块内存。

假设name="maggie",这需要存储到计算机中

当调用greet2（name）时，同样为greet2分配内存，第二个内存块位于第一个内存块上面

当执行输出“how are you, maggie?”时，然后从greet2函数调用返回。此时，栈顶的内存块被弹出。

这时，栈顶是greet函数，说明又回到了greet函数内，接着执行print，再执行bye(),进入bye()函数，将bye函数存储进栈顶。

执行bye函数，打印ok bye!，并从这个函数返回，再将bye函数弹出栈，返回到greet函数，

这时，greet函数内已经没有需要执行的操作，所以将greet弹出，释放栈，栈控制这这里面的运行顺序。

递归调用栈

递归也需要调用栈，对于下面这个函数

对于fact(3)的栈调用顺序如下:

栈的优点：

功能清晰，实现简单

栈的缺点：

存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下可能需要重新编写代码，转而使用循环，或者使用尾递归。

这是书籍《算法图解》第三章的内容的学习笔记，前面两章内容见前面几篇笔记，《算法图解》可以帮助了解简单的算法知识，如需深入学习可以看看《算法导论》欢迎一起学习~