递归问题(面试题) 如何解答

Question

1,2,4,7,12,20.....
用递归算法，采用Java语言实现，如何实现。

Answer 1

public class Test {
public static int printdemo(int index){
  int i = 0;
  if(index <= 0){
  i =  0;
  }else{
  i = printdemo(index -1) + printdemo(index -2) + 1;
  }
       return i;
}
public static void main(String[] s){
 
for(int i = 1;i < 10;i++){
System.out.print(printdemo(i));
if(i != 9){
System.out.print(",");
}
}
}
}

Answer 2

最简单的方式是数学表达式：
f(n) = f(n-1) + f(n-2) + 1 (n>2)
f(1) = 1                   (n=1)
f(2) = 2                   (n=2)int f(int n){
   if(n<=0) throw new IllegalArgumentException("num<=0");
   return n<=2?n:f(n-1)+f(n-2)+1;
}不过明显效率太低求f(n-1) 的时候实际就求了f(n-2)的值。所以最好能推导成 f(n) =  af(n-1) + b n + c 的形式，不过没想出来。所以可以考虑缓存结果，在计算n前先计算n/2或者n/10的情况，然后再计算n，直接使用刚才计算的结果。可以大大提高速度，不过不是个通用的方法。另外还有中转换为矩阵进行计算的方式，是最佳答案，不过我知道的不清楚。
 

Answer 3

这个数列的a(n)-a(n-1)这些差构成了一个fibonacci数列public class Test2 {
public int fib(int n){
if(n==1){
return 1;
}
else if(n==2){
return 2;
}else{
return fib(n-1)+fib(n-2);
}


}
public  int shulie(int n){
if(n==1){
return 1;
}else{

return shulie(n-1)+fib(n-1);
}


}
public static void main(String[] args) {
// TODO Auto-generated method stub
Test2 t = new Test2();
for(int i=1;i<20;i++){
System.out.print(t.shulie(i)+"\t");
}
}
运行结果：1 2 4 7 12 20 33 54 88 143 232 376 609 986 1596 2583 4180 6764 10945

Answer 4

我认为做这种递归题首先应该把它们之间的关系写出来然后再根据数学表达式去写代码:
1>写它们之间的数学表达式(就像2楼所写的那样):
f(n) = f(n-1) + f(n-2) + 1 (n>2)
f(1) = 1                  (n=1)
f(2) = 2                  (n=2) 
2>根据数学表达式写代码: public static  int fun(int n){

if(1==n) return 1;
else if(2==n) return 2;
else 

return fun(n-1) + fun(n-2)+1;


}
例如:想知道它第5个数出什么,就应该调用:
       System.out.println(fun(5));  //答案为12