递推与递归
在进行计算的时候，经常会用到递推的概念。递推是一种用若干步可重复的简运算来描述复杂问题的方法。通常是通过计算前面的一些项来得出序列中的当前项的值。
程序调用自身称为Recursive递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
比如对斐波那契数列，我们看这个函数的定义，fib(n)的返回值是fib(n-1)+fib(n-2)。这个概念上很清晰，但是似乎陷入了死循环中无法出来了，所以一定要有一个出口，当n为1和2的时候，我们要给他规定一个值。这就是递归的写法。
你心里肯定会问：那么程序究竟是怎么执行这个递归的呢？自己调用自己总是感觉奇奇怪怪的。
我们要再次打入计算机内部，来看一个普通函数是如何执行的。
一个函数，定义的时候，有一个名字，有输入的参数，有返回的值，内部还要用到很多临时的变量和指令。
计算机在调用一个函数的时候，会在一个叫做“栈”的内存空间为这一次调用划出一片空间来，存放本次函数调用用到的参数及内部变量。假如在执行函数体内部的时候，又碰到别的函数，同样的办法，在栈里面再开辟一片新的空间，存放新函数用到的参数及内部变量。当这个新韩淑执行完毕后返回，计算机就把新开辟的这一片栈空间释放，带着返回值回到前个函数中断的地方，前个函数的栈空间仍然存在，相当于程序执行返回到了以前的现场。
如果是递归的情况，自己调用自己，原理是一样的，计算机为第二次函数调用也是一样地开辟一片新空间。跟调用别的函数没有区别。
有一幅图表达这个原理：
上图演示了一个函数自己调用自己调了四遍。计算机内部开辟了四个空间，每个空间都是独立保存了一份函数的现场（也叫执行上下文，包括参数变量等）。最后一次递归遇到终结条件就会返回上一级，这样一级一级返回，直到初始调用处。
有了这幅图景，我们可以看到，递归内部的实现跟普通函数没有什么区别。