理解递归算法的原理

递归算法的概念

递归（Recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

关于递归算法

在日常开发中，我们使用循环语句远远大于递归，但这不能说明递归就没有用武之地，实际上递归算法的解决问题的步骤更符合人类解决问题的思路，这是递归算法的优点，同时也是它的缺点。递归算法是比较好用，但是理解起来可能不太好理解，所以在递归算法和循环算法对比中，流行一句话：人理解循环，神理解递归。当然这只是一个段子，不过也从侧面反映出递归算法不容易理解的事实。这个我自己也深有体会，就拿排序算法里面的快排和归并排序来说吧，这两种算法采用的都是分治思想来处理排序问题，所以递归在这里就出现了，如果你不理解递归算法，就去学习这两种排序算法，可能理解起来就非常费事，尽管你知道这两种排序的算法原理和它的时间及空间复杂度，但就是不知道它是如何使用递归完成的，所以学习和理解递归算法是非常有必要的。

实际上递归算法的使用场景，远不止上面说的排序算法，在链表，树，图及其他只要符合分治思想的问题中，其实都可以采用递归来处理。

递归算法的使用

我们先来看一个Java里面，如何写一个最简单的递归方法：

public void recursiveTest(){
    recursiveTest();  //自己调用自己，就叫递归
}

上面就是最简单的递归算法，但不是正确的递归算法，一旦运行起来就会抛出栈内存溢出的异常，因为没有退出条件，所以就会进入死循环中，一直都在重复调用自己，递归调用在底层其实是对线程栈的压栈和出栈操作，每调用一次都会压栈一次，并记录相关的局部变量信息，线程栈的内存是非常有限的，而递归调用如果是无限的，那么很快就会消耗完所有的内存资源，最终导致内存溢出，这一点与空的while死循环是不一样的，单纯的死循环会大量的消耗cpu资源，但不会占用内存资源，所以不会导致程序异常。从这一点能看到递归算法其实是更加消耗系统的性能和资源的，尽管有些编程语言可以做尾递归的优化，降低递归对资源的占用程度，但并不大多数语言都可以支持的或者说很完美的支持，Java就是其中之一，并不支持尾递归的调用。

递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此，在计算机科学中，递归可以被用来描述无限步的运算，尽管描述运算的程序是有限的。 这一点是循环不太容易做到的。

编写正确的递归算法，一定要有 ”归“ 的步骤，也就是说递归算法，在分解问题到不能再分解的步骤时，要让递归有退出的条件，否则就会陷入死循环，最终导致内存不足引发栈溢出异常。

下面，我们通过两个例子来学习一下，递归的使用：

例子一：求阶乘

public static int factrial(int n){
        if(n<1){
            return 1;
        }
        return  n*factrial(n-1);

    }

上面是网上大多数代码的例子，但是对于初学者来言，是不太友好的，因为看不到太多的细节，所以 我改造了一下，实现的是同样的功能，但有详细的步骤，如下：

public static int factrialDetail(int n){
        if(n<1){
            System.out.println("拆解问题完毕，开始分而治之");
            return 1;
        }
        System.out.println("f("+n+")="+n+" * f("+(n-1)+")");
        int z= n*factrialDetail(n-1);

        System.out.println("f("+n+")="+z);

        return  z;

    }

例如，求5的阶乘，结果输出如下：

f(5)=5 * f(4)
f(4)=4 * f(3)
f(3)=3 * f(2)
f(2)=2 * f(1)
f(1)=1 * f(0)
拆解问题完毕，开始分而治之
f(1)=1
f(2)=2
f(3)=6
f(4)=24
f(5)=120

从上面的步骤我们可以清晰的看到递归算法的第一步是分治，把复杂的大的问题，给拆分成一个一个小问题，直到不能再拆解，通过退出条件retrun，然后再从最小的问题开始解决，只到所有的子问题解决完毕，那么最终的大问题就迎刃而解。上面的打印信息，符合栈数据结构的定义，先进后出，通过把所有的子问题压栈之后，然后再一个个出栈，从最简单的步骤计算，最终解决大问题，非常形象。

如下图：

一阶段，递推分解任务：

二阶段：回归分治任务：

例子二：斐波那契数列

斐波那契数列是一个经典的数列，其数列符合黄金分割比的规律，数列越大，其前一项与后一项的比值，越接近黄金比例。

用文字来说，就是费波那契数列由0和1开始，之后的费波那契系数就是由之前的两数相加而得出。首几个费波那契系数是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233....

下面看下代码：

public static int fibonacci(int n){
        if(n<0){
            throw new IllegalArgumentException("传入参数不合法");
        }
        if(n<=2) {
            return 1;
        };
        //先计算第一个递归函数.
        int plusItem1=fibonacci(n-1);
        int plusItem2=fibonacci(n-2);
        int sum=plusItem1+plusItem2;

        return sum;

    }

注意上面的代码，是我特意改造过的，并没有直接在返回处相加两个递归函数，而是通过存储到变量之后，在最终返回，这样做的目的，是帮助大家更容易理解递归的运行特点：上面这段代码相比阶乘的例子，稍微复杂了点，因为方法体里面出现了两个递归调用函数，而阶乘的只有一个。

int sum=plusItem1+plusItem2;

注意这段代码，一定是在分解任务不能再分解的时候，才开始执行，在不能再分解的时候，就意味着该出栈了，这样一来sum的值，会由两个递归函数的结果汇总，然后向上不断的回报并出栈，直到解决顶层的大问题。

如果不理解的同学，可以传入小一点的参数，然后自己可以试着在纸上划一划，关于递归算法的使用，网上还有比较经典的汉诺塔游戏的解法，此外，如果想练手的同学，可以尝试编写一个十进制转其他进制的递归算法。

总结：

本文主要介绍了递归算法的概念和思想原理及使用例子，递归算法在解决特定场景下的问题非常强大，递归算法的使用，关键在于如何把大问题给分解成相同类型的子问题，然后对一个一个子问题各自击破，当所有的子问题都解决了，那么大的问题也就解决了。最后，使用递归算法需要记住，一定要有让递归回归的约束条件，这才是正确编写递归的前提。