如果我们需要重复多次计算相同问题，则通常可以选择用，递归或者循环两种不同方法。递归实在一个函数内部调用这个函数自身。而循环是通过设置计算的初始值以及终止条件，在一个范围内重复运算。比如求1+……+n，我们可以同递归或者循环两种方式求出结果，对应代码如下
public class addFrom1ToN_Recursive {
static int addFrom1ToN_Recursive(int n){//递归
return n<=0?0:n+addFrom1ToN_Recursive(n-1);
}
static int addFrom1ToN_Iterative(int n){//循环
int result=0;
for(int i=1;i<=n;i++){
result+=i;
}
return result;
}
public static void main(String[] args){
System.out.println(addFrom1ToN_Recursive(100));
System.out.println(addFrom1ToN_Iterative(100));
}
}
通常递归代码更加简洁。但由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址和临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。
另外，递归中有很多计算都是重复的，对性能有负面影响。
通常应用动态规划解决问题我们都是用递归的思路分析问题，但由于递归分解的子问题中存在大量的重复，因此我们总用自下而上的循环来实现代码。
递归还可能引起更严重的问题：调用栈溢出。需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量有限。当递归调用的层级太多，就会超出栈的容量。从而导致调用栈溢出。
面试题10.斐波那契数列
题目：求斐波那契数列的第n项
效率很低的递归
public class fibonacci {
static long Fib(long n){
if(n<=0){
return 0;
}
else if(n==1){
return 1;
}
else{
return Fib(n-1)+Fib(n-2);
}
}
}
计算量会随着n的增大而急剧增大，因为需要重复计算的实在太多了，要想办法避免重复计算
简洁方法是从下往上计算，根据f(0)和f(1)计算f(2),再根据f(1)和f(2)计算f(3)……,时间复杂度O(n)
static long Fib2(int n){
int[] result = {0,1};
if(n<2){
return result[n];
}
long fibOne=0;
long fibTwo=1;
long fibN=0;
for(int i=2;i<=n;i++){
fibN = fibOne+fibTwo;
fibOne = fibTwo;
fibTwo = fibN;
}
return fibN;
}
时间复杂度O(logn)但不够实用的解法
需要用到快速幂公式
类似的问题
题目二：青蛙跳台阶
一次可以跳上1级或者2级，求该青蛙跳上n级台阶有多少种跳法
1级台阶：1种
2级台阶：2种
n级台阶：（跳一下+在n-1级台阶时）+ （跳两下+在n-2级台阶时）
f(n)=f(n-1)+f(n-2)，同斐波那契数列
变式：如果把条件改成，一只青蛙一次跳上1级……n级，此时青蛙跳上一个n级台阶总共有多少解法:2^(n-1)种
相关题目：
用2*1的小矩形横着或竖着去覆盖更大的矩形。请问用8个2*1的小矩形无重叠的覆盖一个2*8的大矩形，总共有多少种方法
思路：先把2*8的覆盖方法记为f(8)，用第一个2*1的小举行去覆盖大矩形的最左边时有两种选择：竖着或横着放。当竖着放的时候，右边还剩2*7的区域，这种情况下的覆盖方法几位f(7)，接下来考虑横着放，当2*1的小矩形横着放在左上角，左下角必须也横着放一个2*1的小矩形，而右边还剩下2*6的区域，这种情形下的覆盖方法几位f(6)，因此f(8)=f(7)+f(6),仍然是斐波那契数列
public class RectangularCover {
public static int rectangularCover(int n){
if(n<=0){
return 0;
}
if(n<=2&&n>0){
return n;
}
else{
return rectangularCover(n-1)+rectangularCover(n-2);
}
}
public static int rectangularCover2(int n){
if(n<3){
return n;
}
int fib1=1;
int fib2=2;
int fibN=0;
for(int i=3;i<=n;i++){
fibN=fib1+fib2;
fib1=fib2;
fib2=fibN;
}
return fibN;
}
public static void main(String[] args){
System.out.println(rectangularCover(8));
System.out.println(rectangularCover2(8));
}
}