定义

英文定义:Recursion is the process of repeating items in a self-similar way.

具体到计算机中去：

递归：又称为递回,在数学和计算机科学中,是指在函数的定义中使用函数自身的方法.

[以上定义来源为wiki].

英文的Recursion表达的是重复发生,再次重现的意思.而对应的中文翻译”递归”确表达了两个意思:” 递”+”归”.这两个意思,正是递归思想的精髓.

递归思想

递归的基本思想是：把规模大的问题转化为规模小的相似的子问题来解决.这种思想与数学中的归纳法十分相近。

递归在程序中的表现：在函数实现递归时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况.需要注意的是,递归函数必须有明显的结束条件(base case),避免产生无限递归的情况.

经典示例：N的阶乘问题

    我们知道5!=5*4*3*2*1;4!=4*3*2*1;…

            5!=5*4!...

    从上面我们可以归纳出N!=N*(N-1)!,由此函数的代码如下：

public static long factorial(int n){      if(n==1) // base case         return 1;      else  // reduction step         return n*factorial(n-1);   }

Base case:基线条件,递归的终止条件

Reduction step:递归操作,对问题的定义.

递归vs循环

         从大多数情况来看,递归和循环是可以相互转换的.例如上面的阶乘问题,如果计算的阶乘的方法是n!=n*(n-1)*….*2*1,就明显是一个循环的过程,如果计算阶乘的方法是n=n*(n-1)!,这就归纳出了一个递归定义。循环要求思考一个问题怎么做,而递归要求思考一个问题的定义（某Lisp开发者说的）.

         实际开发中,循环更加常见,但有些情况下,可能需要将循环转为递归(面试).递归与循环其实想通的地方挺多,它们都需要初始条件和终止条件.用递归解决循环问题,需要明确基线条件和定义递归问题(每一步递归操作的算法),本人在面试过程中遇到过一个这样问题：求两个数的最大公约数,不使用循环.其实,从后面那句”不使用循环”就明显是考递归的。Java代码如下:

// 辗转相除法求两个数的最大公约数   public static int gcd(int num1,int num2){      // check args      if(num1==0 || num2==0){         return 0;      }      // num1>num2      int tmp = num1;      num1 = Math.max(num1,num2);      num2 = Math.min(tmp, num2);      int p = num1%num2;      /*while(p!=0){         num1 = num2;         num2 = p ;         p = num1%num2;      }*/      if(p!=0)         return gcd(num2,p);      return num2;   }

从上面可以看到,循环转递归时要把握两个点：

• 循环的终止条件与递归中的基线条件
• 循环中的算法与递归的算法

应用

当问题的定义本身就是递归形式的时候,可以考虑使用递归.数据结构里面的“树”就是典型的递归定义。还有如上面说的阶乘,汉诺塔问题,斐波拉契数列等.都可以使用来递归解决问题.

使用递归可以使用紧凑和优雅的代码来解决看起来很”吓人”的问题.但实际中,递归并不十分常见.首先,函数执行过程中,栈空间的分配是有限的,如果递归的深度过大,就会造成栈空间的溢出.其次,递归提高了程序的书写效率,但并不意味着执行效率的提高.一般来说,递归的执行效率未必比循环高,因为在栈上开辟新空间、分配局部变量都是需要时间开销的,特别是递归深度很大的时候。所以,学习递归主要是学习其思想—把规模大的问题转化为规模小的相似子问题来解决。

借鉴知乎上某资深码农的一句话,个人觉得说的很好：

         当你的问题分析透彻，何时使用递归就会自然明了。递归只是一种函数调用的技巧，不是解决问题的公式。一个问题可以用递归做，也可以不用递归做，递归不是必须的。所以，理解你需要解决的问题，想清楚解决问题的步骤方法，你会突然发现，原来可以用递归来简化问题。不要一开始就想着如何用递归。

参考资料：

   http://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92

   http://www.zhihu.com/question/20507130

   http://www.zhihu.com/question/20096035

   http://www.ibm.com/developerworks/cn/linux/l-recurs.html