递归算法

转自http://www.ibm.com/developerworks/cn/linux/l-recurs.html#N10046
DW上的东西还是很有营养的。。

递归程序的基本步骤
每一个递归程序都遵循相同的基本步骤：

1 初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数， 这个函数是非递归的，但可以为递归计算设置种子值。
2 检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。
3 使用更小的或更简单的子问题（或多个子问题）来重新定义答案。
4 对子问题运行算法。
5 将结果合并入答案的表达式。
6 返回结果。

简单的:
(1)分析问题,得出递归关系.
(2)设置边界条件,控制递归.
(3)设计函数,确定参数.

从大到小法！

递归的经典示例
计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。例如，factorial(5) 等价于 5*4*3*2*1，而 factorial(3) 等价于 3*2*1。
阶乘的一个有趣特性是，某个数的阶乘等于起始数（starting number）乘以比它小一的数的阶乘。例如，factorial(5) 与 5 * factorial(4) 相同。

int factorial(int n)
{
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n - 1);
   }
}