递归和循环.md

递归和循环

递归是函数内部调用这个函数自身。循环是一个范围内的重复运算。

特征

1. 递归优点代码较简洁，缺点由于调用函数本身，每次调用都要在栈中分配空间用于保存参数、返回地址及临时变量。因为分配给线程的栈空间是有限的，容易调用栈溢出。
2. 递归中间有可能存在重复计算。
3. 循环语句较多些，但是在空间上比递归好。

《剑指Offer》涉及的算法

面试题10.1 - 斐波那契数列

面试题10.2 - 青蛙跳台阶问题

其中青蛙跳台问题的拓展

青蛙可以一次跳1.2....n个台阶

此时跳上n个台阶有多少种跳法。

数据归纳可以证明$$ f(n)=2^{n-1} $$