算法系列：理解递归算法并精通递归程序设计

递归在我们的程序中存在普遍的使用。今天在csdn里面看到一个朋友写了一篇递归的文章http://blog.csdn.net/codyguo/article/details/51009768，我告诉他，这不叫文章，这叫草稿，或者说笔记。没见过就这样赤裸裸的直接上代码的。

一些人认为递归完全没必要，用循环就可以实现，其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环，大家都知道递归分两步，递和归，那么可以知道递归对于空间

递归的经典示例

计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。例如，factorial(5) 等价于 5*4*3*2*1，而 factorial(3) 等价于 3*2*1。

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

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

1.初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数， 这个函数是非递归的，但可以为递归计算设置种子值。

2.检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。

3.使用更小的或更简单的子问题（或多个子问题）来重新定义答案。

4.对子问题运行算法。

5.将结果合并入答案的表达式。

6.返回结果。

基线条件是递归程序的 最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且 必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。

递归是一门伟大的艺术，使得程序的正确性更容易确认，而不需要牺牲性能，但这需要程序员以一种新的眼光来研究程序设计。对新程序员 来说，命令式程序设计通常是一个更为自然和直观的起点，这就是为什么大部分程序设计说明都集中关注命令式语言和方法的原因。 不过，随着程序越来越复杂，递归程序设计能够让程序员以可维护且逻辑一致的方式更好地组织代码。

： » 算法系列：理解递归算法并精通递归程序设计