通过栈来了解递归的原理和实现

作为一个很基础的东西递归在面试中是作为最基础的东西，既然是最基础的东西今天就巩固一下：

首先去网上大致找了一下 包括一些知乎大神到最后也没怎么把这个原理很透彻很清晰的说清楚，我觉得通过栈的执行很容易把这个过程说清楚了.

wiki上定义是：

Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be recursive.

翻译过来就是大致意思就是：递归是一个程序自身调用自身的一个过程

递归原理很简单 就是通过栈机制来把递归过程中的函数 以及它的符号入栈 和出栈 并在出栈过程中对这些符号和函数返回值等进行运算。

懂得原理的话其实实现递归很就很简单了

第一步： 写一个函数

第二步 ：在这个函数里面写终止条件

第三步： 通过一个符号来连接这些返回的函数

用一个很简单的计算前n个数的和的递归实现来举例：

int func(int n) { if (n <= 1 ) //可以返回了 { return n; } else { n += func(n - 1); } }

由于函数的执行就是一个入栈和出栈的执行过程 ，所以 下面用最直观的 入栈和出栈来解释一下：

入栈执行：

func（n）入栈 n 入栈 "+" 入栈

func（n -1）入栈 n-1 入栈 "+" 入栈

func（n -2）入栈 n-2 入栈 "+" 入栈 ... func（1）入栈 1入栈 递归结束开始执行出栈

出栈执行：

1 出栈 现在栈顶是1

func（2）出栈 2 出栈 "+" 出栈 ：执行计算 栈顶值 + 2 1 + 2 得出 3 现在栈顶是 3

func（3）出栈 3 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 6

func（4）出栈 4 出栈 "+" 出栈 ：执行计算 栈顶值 + 4 3 + 3 得出 10 现在栈顶是 10

func（5）出栈 5 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 15

func（6）出栈 6 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 21

func（7）出栈 7 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 28

func（8）出栈 8 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 36

func（9）出栈 8 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 45

func（10）出栈 8 出栈 "+" 出栈 ：执行计算 栈顶值 + 3 3 + 3 得出 6 现在栈顶是 55 --现在栈里面只剩下 55 了 弹出结束函数执行

执行的最终结果是 栈里面只剩下 55，出栈结束函数执行

看到这里递归的执行过程一目了然了。