面试题9：斐波那契数列

递归是在一个函数内部调用这个函数自身，而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。

递归的代码通常会比较简洁，但由于递归是函数调用自身，而函数调用是有时间和空间的消耗，每次调用都需要在内存栈中分配空间以保存参数、返回地址及临时变量，因此递归实现往往效率不如循环。

同时，递归中有可能有很多重复计算。还可能引发调用栈溢出。

 

面试题9：斐波那契数列

常用方法

1、递归方法

2、o（n）方法，循环方法

3、o（logn）方法，由数学归纳法可得出

矩阵或数值的整数次方的求解可以达到o（logn）

//题目描述 //大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列 //的第n项。 class Solution{ public: int Fibonacci(int n){ int a=0,b=1; if(n==0)return 0; if(n==1)return 1; for(int i=2;i<=n;i++){ int tmp=a+b; a=b; b=tmp; } return b; } };

f(n)=f(n-1)+f(n-2)，与斐波那契类似

//题目描述 //一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n级的台阶总共有多少 //中跳法。 class Solution{ public: int jumpFloor(int number){ int a=1,b=2; if(number<=2)return number; for(int i=3;i<=number;i++){ int tmp=a+b; a=b; b=tmp; } return b; } };

变形

//题目描述 //一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶...它也可以跳上n级。求 //该青蛙跳上一个n级的台阶总共有多少种跳法。 class Solution{ public: int jumpFloorII(int number){ return 2<<(number-1); } };