函数的递归说明

一个函数在函数体内又调用了本身，称之为递归调用

递归执行流程

递归总结说明

1、执行一个函数（一次递归调用）时，就创建一个新的受保护的独立空间（新函数栈）

2、函数内的变量时独立的、局部度，不会相互影响

3、递归必须向退出递归的条件逼近，否则就是无限递归（死递归）

4、当函数执行完毕或提前遇到return，就会返回对应的值，这个过程遵守谁调用就将结果返回给谁的原则，同时函数本身也会被系统销毁

递归案例

案例一：斐波那契数列

案例二：已知 f(1)=3; f(n) = 2*f(n-1)+1; 请使用递归的思想编程，求出 f(n)的值?

上面代码的执行流程

案例三：猴子吃桃

有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。到第十天想再吃时，发现只剩 1 个桃子。问：最初共多少个桃子？

思路分析：

要点：切记谁调用返回给谁的原则，虽然传入的是天数，但函数return的是桃子数量（天数=>桃子数量，不要混淆）

1、第10天剩1个，根据规则推导出第9天的数量：(1+1)*2

2、要求最初共多少个桃子，也就是第一天，所以传入参数1

3、明知最后一天剩1个，所以先判断当前是否为最后一天，如果不是，递归调用自己，直到最后一天return 1

4、按照 (前一天数量+1)*2 的规律递归，依次求出前一天的数量

5、如此即可得到最终规律：假设n表示求数量的那天，将 n 通过 peach(n+1) 递归到最后一天，按照函数栈先进后出的原则，再依次返回前一天的数据，(peach(n+1)+1)*2，最终：peach(n) = (peach(n+1)+1)*2