递归算法是一些基本数据结构实现的基础，不掌握递归那很多数据结构没法说了。我们在这里总结一下递归的用法。
递归简论：
我们熟悉的大多数数学函数都是由一个简单的公式来描述的，例如我们可以用C=5(F-32)/9来将华氏温度转成摄氏温度。这种公式在java程序中实现实在是太简单的，而实现这种公式有一种统一的名称，称为迭代。
但是还有一种比较复杂的函数没法直接使用，如下：
f（x)=2f(x-1)+x²，f(0)=0。
我们可以从条件推出f(1)=1,f(2)=6,f(3)=21,f(4)=58。
但是这种公式在程序种该如何表达？
引入
当一个函数用它自己来定义时就称之为递归，java是允许递归的。但重要的一点是：java提供的仅仅是遵守递归思想的一种尝试。不是所有的递归函数都能由java的递归来模拟实现。
对于上面的递归函数，我们可以由如下代码实现
package 递归简论;
/**
* 递归（recursive）
*
* 我们这里实现一个简单的递归函数：f（x)=2f(x-1)+x²，f(0)=0。
*
* @author xuxiao
*
*/
public class Recursive {
public static int f(int x) {
if(x==0)
return 0;
else
return 2*f(x-1)+x*x;
}
}
程序结构
程序中的if(x==0)
return 0;
称之为基准情况（base case），即此时函数的值可以直接算出而不用求助于递归，正如f（0）=0一样。若没有函数这个基准线，递归函数是没有任何意义的，而程序中没有基准线，则会陷入无限循环的递归深渊。
实际上递归调用在处理上和调用普通方法没什么区别，举个例子，我以参数4调用函数f，那么程序就会计算2f（3）+44。这样就会执行一个f（3）的调用，又因此要去调用f（2），f（1），f（0），最后f（0）直接得到，从而返回上一层，f（1）也计算出来了，f（2），f（3），f（4）也依次得到了返回值。
递归调用的核心就是反复调用自身，直到基准线的出现。因此上面的程序是有漏洞的，即如果我参数的值是-1，那么我的递归永远达不到基准线。
上面对递归的讨论可以将递归函数总结为两个法则：
1.基准线：必须要有基准，否则递归不能求解
2.不断推进，对于那些要求递归的情景，递归总是朝着一个基准情景推进。（也就是说如果我的函数是f（x)=2f(x)+x²，那这个函数也是无解的）
递归程序设计法则
1.基准情形（在实际的编程中，基准线可能会不止一条，找到正确且合适的基准线是我们努力的目标）
2.不断推进
3.设计法则。假设所有递归调用都能运行
4.合成效益法则。在求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作。
ps：合成效益法则表明，我们在递归计算如斐波那契数列的简单数学函数时使用递归是不明智的。
