递推和递归

我眼中的递归和递推，通过对Fibonacci数列的两种代码实现展示。

Fibonacci:0（第0项） 1（第1项） 1（第2项） 2（第3项） 3（第4项） 5（第5项） 8（第6项） 13（第7项）......

首先递推：从第2项开始的以后的每一项都由其前面两项加和得。

Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  if(n==0){
   System.out.println(0);
  }
  else if(n==1){
   System.out.println(1);
  }
  else{
   int x1=0,x2=1;
   int x3 = 0;
   for (int i = 2; i <=n; i++) {
    x3 = x1+x2;
    x1 = x2;
    x2 = x3;
   }
   System.out.println(x3);
  }

递归的思想：将现有问题拆分成和该问题有相同解法的子问题，直到拆分到最小的问题有一个确定值。

f(n)=f(n-1)+f(n-2)(n>=2)

　　　f(n)=0(n=0)

　　　f(n)=1(n=1)

代码：

public static int f(int n){
  if(n==0)return 0;//确定值
  if(n==1)return 1;//确定值
  return f(n-1)+f(n-2);
 }

递归的代码看着是不是很简洁很少。但是在有些问题上递归是不可行，因为递归每次调用的都是其自身的方法，每调一层在其方法体内变量就会在内存中产生开销

在本次问题中我测试的当输入40时，就会产生延时感，随着数的增加，耗时会越来越长，直到产生栈溢出。

尽管递归有着诸如此类的问题，但是当规模较小时递归的使用能够更有效的解决问题，接下来几天会和大家一起使用递归，解决一些题目。

递推和递归

原文：http://www.cnblogs.com/suizhibo/p/6697004.html