栈在递归中的应用

函数调用的特点：

函数调用的过程：
那么该过程其实和元素进栈是相类似的：

如下图所示：

函数调用时，需要用一个栈存储：

1：调用返回地址

2：实参

3：局部变量

当所有可调用的函数都被调用完之后，下面执行未执行完成的语句：
此时的函数调用栈，相当于进行出栈的操作：

接着将func1所占用的内存进行释放。

最后被调用的函数最先被调用的函数最先被执行结束（LIFO）

适合用“递归”算法解决：可以把原始问题转换成属性相同，但规模较小的问题。
举例：
我们将问题规模从n转换到了比n更小的n-1.

但如何设计一个递归算法并不是这里要探讨的主要问题，这里，我们重点学习栈在递归中的应用。

递归调用时，函数调用栈可称为“递归工作栈”

递归算法实现n的阶乘：

每进入一层递归，就将递归调用所需信息压入栈顶

如下图所示：
每退出一层递归，就从栈顶弹出相应的信息

下面也是如此调用返回，直到第一层。

这种算法虽然可以一定程度上减小问题规模，但是，当太多层递归可能会导致栈溢出，设想，上述实例，假如传入的参数为10000，按摩相当于该栈需要压入10000层，但我们的内存资源是有限的，这样一来会增加空间复杂度。

递归算法实现斐波那契数列：

每进入一层递归，就将递归调用所需信息压入栈顶

如下图所示：

每退出一层递归，就从栈顶弹出相应的信息

如下图所示：

通过上图的递归调用过程，我们不难发现，其实有很多项都是重复计算的，例如：Fib(1)/FIb(2),因此，递归的调用可能包含重复计算，这也是它的缺点。