递归方法的执行次数，腾讯招聘2008面试题

Question

int x(int n)
{
if(n <=3) return 1;
else return x(n-2)+x(n-4)+1;
} 
请问计算x(x(8))时需要计算_次x方法啊？
在c++版抓看的题，发现自己对递归还是没掌握，很郁闷...

Answer 1

public class Test {
static int count = 0;
  public static void main(String args[]) {    
x(x(8));
System.out.println(Test.count);
  }
  public static int x(int n) { 
  count++;
if(n <=3) return 1;
    else return x(n-2)+x(n-4)+1;
  } 
}

Answer 2

1 x(6) + x(4) + 1
2 x(4) + x(2) + 1 + x(4) + 1  以后+1全部去掉
3 x(2) + x(0) + x(2) + x(4)
4.x(0) + x(2) + x(4)
5 x(2) + x(4)
6 x(4)
7 x(2) + x(0)
8 x(0)
9 计算出来 
然后再重复一次 
代码测试：
public class Test10 {
public static void main(String[] args) {
//int i = 0;
Aoo a = new Aoo();
a.x(a.x(8));
System.out.println(a.i);
}
}

class Aoo {
 int i = 0;
 int x(int n) {
{


if(n <=3) {
i++;

return 1;
}
else {
i++;

return x(n-2)+x(n-4)+1;
}
} 

}
}

Answer 3

x(8)
x(6)
x(4)
x(2)
x(0)
x(2)
x(4)
x(2)
x(0)
x(9)
x(7)
x(5)
x(3)
x(1)
x(3)
x(5)
x(3)
x(1)
18

Answer 4

---------
public static void main(String[] args) {
System.out.println(x(x(8))); }

public static int x(int n)
{
System.out.println("**********");
if(n <=3) return 1;
return x(n-2)+x(n-4)+1;
} 
-----------------
会打印出18行 "**********"

Answer 5

9次
return 1为止            x(8)
           /     \
        x(6)      x(4)
       /   \      /  \
    x(4)    x(2) x(2) x(0)
    / \    
 x(2) x(0)