递归算法

递归算法的描述：

递归算法是一种直接活着间接调用自身的算法，是把问题转化为规模缩小的同类问题的子问题。与斐波那契数列异曲同工。

在历史长河之中它解决了什么：

(1) 斐波那契数列: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……

(2) 阶乘 : n! = n * (n-1) * (n-2) * ...* 1(n>0)

(3) 河内塔问题 :

(4) 生兔子问题:

第一个月小兔子没有繁殖能力，所以还是一对；

两个月后，生下一对小兔子，总数共有两对；

　　　三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，总数共是三对；

　　　 ……　

递归算法解决问题的特点：

(1) 递归就是在程序执行的过程中或者函数里调用自身.

(2) 在使用递归策略时，必须有一个明确的递归结束条件，也就是递归的出口。如果没有出口会怎么样，就会出现死循环，好比我们从小听到的一个故事一样：

从前有座山，山里有个庙，庙里有个老和尚正在讲故事：从前有座山，山里有个庙，庙里有个老和尚正在讲故事：

　　　从前有座山，山里有个庙，庙里有个老和尚正在讲故事...

(3) 递归算法解决问题简洁明了，但解决问题的运行效率较低。

当看到这个特点的时候不妨想想为什么说它效率低？我能想到的是这样子的，递归算法的自我调用都会走一遍这个方法，那么这个方法里面会干什么，怎么干，如果说在调用这个函数之前需要准备许多pre的工作，for example：准备变量（需要消耗空间咯），各种判断（一次调用可以不在乎，N次呢），每次调用这个method都会走一遍这样的流程，自然会开销大一些，这也就显示出来了第(4)点咯。

(4) 在递归调用的过程中系统为每一层的返回点，局部变量等开辟了栈来存储，递归次数过多容易造成栈溢出等。

函数在被调用还没有结束时再次调用该函数，当前的状态会被保存到栈里面去，依此类推，在最后一个函数执行完之后，倒数第二个函数才开始出栈，

递归算法的分类：

分两种：直接递归和间接递归

直接递归：method A call itself

间接递归：method A call method B, mehod B call method C, metod C call method A

实现：

在JAVA中的实现

public class Test {

    private static int number;

    public static void main(String[] args) {
        int result = recursion(5);
        System.out.println(result);
    }

    public static int recursion(int i) {

        number++;
        System.out.println("In--" + number + "--i = " + i);

        if (i == 0) {
            return 0;
        } else if (i == 1) {
            return 1;
        } else {
            return recursion(i - 1) + recursion(i - 2);
        }
    }

}

结果：

In--1--i = 5
In--2--i = 4
In--3--i = 3
In--4--i = 2
In--5--i = 1
In--6--i = 0
In--7--i = 1
In--8--i = 2
In--9--i = 1
In--10--i = 0
In--11--i = 3
In--12--i = 2
In--13--i = 1
In--14--i = 0
In--15--i = 1

看到如下结果，是否想一想程序是怎么走的呢？请看如下图：

河内塔问题

    public static void hanoi(int n, int p1, int p2, int p3) {
        if (1 == n) {
            System.out.println("盘子" + n + "从" + p1 + "移到" + p3);
        } else {
            hanoi(n-1, p1, p3, p2);
            System.out.println("盘子" + n + "从" + p1 + "移到" + p3);
            hanoi(n-1, p2, p1, p3);
        }
    }

结果：

盘子1从1移到3
盘子2从1移到2
盘子1从3移到2
盘子3从1移到3
盘子1从2移到1
盘子2从2移到3
盘子1从1移到3

如何优化这类问题，请看我的另一篇博客：

对费波纳契数列的几种算法实现对比分析

引用：

1. 汉诺塔

2. https://www.zhihu.com

3. http://www.cnblogs.com/joinclear/archive/2013/02/06/2908247.html