一、引论之递归

摘出本章比较感兴趣的一部分，首先是关于递归的简述。
  递归有两个基本法则：
1.基准情形：不用递归就能求解
2.不断推进：对于需要用递归求解的情形，递归调用必须朝着基准情形推进。
  下面列举一些例子。
例1 无终止的递归

public static int bad(int n){
     if(n==0)
        return 0;
     else
        return bad(n/3+1)+n-1;
}

  在这个例子中，bad(1)会反复求bad(1)，同样bad(2)也是。将陷入死循环，知道jvm奔溃。
例2 打印输出正整数
  设有一个正整数n并希望将其打印。而仅有的IO只允许处理单个数字并输出（printDigit）。分析：要打印76321，首先打印出7632，再打出1。而打印出1只需printDigit(n%10)就可以。打印7632可以用print(76321/10)。

public static void print(long n){
	if(n>=10)
		print(n/10);
	printDigit(n%10);
}

  不过这个例子并不是很高效，因为mod是非常耗时的，n%10=n-(n/10)*10。
  因此引出递归的第三个法则：
3.设计法则：假设所有的递归调用都能运行。
  当编写递归程序时，要牢记其第四条基本法则：
4.合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性工作。
  因此，使用递归来计算斐波那契之类的简单数学函数值并不合适。