一，十进制转二进制
计算十进制（12）转二进制
递归函数的设计：双层
外层getBinary()抓异常
内层getBin递归计算
public static String getBin (int n){
if (n <= 1)
return Integer.toString (n);
return getBin (n / 2) + Integer.toString (n % 2);
}
递归调用的次数是n被2除直到最后结果为1所需要的次数，这个值为floor(log2(n))
floor(x）小于或等于x的最小整数
二，斐波那契数列
1，1，2，3，5，8，13……
n>3时，f(n)=f (n - 1) + f (n - 2)
直接用这个公式递归，会导致最坏情况远行时间很高
假设计算f(n)需要c(n)次运算
则c(1)=c(2)=1
n>3时，c(n)=1+c(n-1)+c(n-2)
可用数学归纳法证明c(n)=2*f(n)-1
∴worstTime(n) ~ c (n) = 2*f(n) - 1
∴worstTime(n)=Θ(f (n))
f (n) = (1 /√5)(((1 +√5) / 2)n - ((1 -√5) / 2)n)
n->无穷大时，(1 - √5) / 2)n ->0
∴f (n), and worstTime (n), isΘ (((1 + √5) / 2)n)，太大
所以对斐波那契数列用for循环里迭代法比较好
public static long fibonacci(int n){
if(n==0)
return 0;
if(n==1)
return 1;
long fibN1=0,fibN2=1,fibN=0;
for(int i=2;i<=n;i++){
fibN=fibN1+fibN2;
fibN1=fibN2;
fibN2=fibN;
}
return fibN;
}
斐波那契题目变形：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，
此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1);
另一种选择是第一次跳2级，此时跳法数目等于后面剩下n-2级台阶的跳法数目，即为f(n-2)。
因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。斐波那契数列。
三，汉诺塔
三个塔座：Origin（初始地点），Destination（目的地点），Temporary（临时地点，用来中转）
要将n个圆盘从Origin移动到Destination
如果n=1，则直接将它从Origin移动到Destination
如果n>1
1，首先将n-1个圆盘从塔座Origin移动到Temporary
2，然后把第n个圆盘从从Origin移动到Destination
3，接着将n-1个圆盘从Temporary移动到Destination
1和3两个步骤都是在递归
代码：仍然是分两层：moveDisks抛出异常，move做具体的递归操作
public static String moveDisks (int n, char orig, char dest, char temp)
{
// throw new UnsupportedOperationException();
if (n <= 0)
throw new IllegalArgumentException( );
return move (n, orig, dest, temp);
} // method moveDisks
public static String move (int n, char orig, char dest, char temp)
{
final String DIRECT_MOVE =
"Move disk " + n + " from " + orig + " to " + dest + "\n";
if (n == 1)
return DIRECT_MOVE;
String result = move (n - 1, orig, temp, dest);
result += DIRECT_MOVE;
result += move (n - 1, temp, dest, orig) ;
return result;
} // method move
四，间接递归
活动：一个方法如果正在执行，或者由一个活动的方法调用，称这个方法是活动的
递归：一个方法如果在活动时能被调用，则称这个方法是递归的
B、C、D均为递归方法，间接递归
活动记录：关于当前活动方法的执行状态的信息。编译器实现保存和获取活动记录的机制是堆栈，将在第七章讨论。