算法渣-递归算法

前言

之前的排序算法 《快速排序》 与 《归并排序》 都使用了递归手法，如果不能理解递归，那分治思想类算法实现就难以理解

递归

To iterate is human,to recurse divine. — L. Peter Deutsch

迭代的是人，递归的是神

递归思想

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

递归中的“递”就是入栈，递进；“归”就是出栈，回归

规模大转化为规模小是核心思想，但递归并非是只做这步转化，而是把规模大的问题分解为规模小的子问题和可以在子问题解决的基础上剩余的可以自行解决的部分。而后者就是归的精髓所在，是在实际解决问题的过程

为什么我老是有递归没有真的在解决问题的感觉？ 因为递是描述问题，归是解决问题。而我的大脑容易被递占据，只往远方去了，连尽头都没走到，何谈回的来

递归就是有去（递去）有回（归来）

• 为什么可以”有去“？

这要求递归的问题需要是可以用同样的解题思路来回答除了规模大小不同其他完全一样的问题

• 为什么可以”有回“？

这要求这些问题不断从大到小，从近及远的过程中，会有一个终点，一个临界点，一个baseline，一个你到了那个点就不用再往更小，更远的地方走下去的点，然后从那个点开始，原路返回到原点

递归三要素

用程序表达出来，确定了三个要素：递 + 结束条件 + 归

function recursion(大规模){
    if (end_condition)    {
        end;     
    } else {     //先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题
        recursion(小规模);     //go;
        solve;                //back;
    }
}

另一种递归情况，比如递归遍历的二叉树的先序

function recursion(大规模){
    if (end_condition){
        end;     
    }else{     //在将问题转换为子问题描述的每一步，都解决该步中剩余部分的问题。
        solve;                //back;
        recursion(小规模);     //go;
    }
}

示例

阶乘

求一个数的阶乘是练习简单而典型的例子，阶乘的递推公式为：factorial(n)=n*factorial(n-1)，其中n为非负整数,且0!=1,1!=1

我们根据递推公式可以轻松的写出其递归函数：

public static long factorial(int n) throws Exception {
    if (n < 0)
        throw new Exception("参数不能为负！");
    else if (n == 1 || n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

在求解6的阶乘时，递归过程:

斐波那契数列

斐波那契数列的递推公式:Fib(n)=Fib(n-1)+Fib(n-2)，指的是如下所示的数列：

1、1、2、3、5、8、13、21.....

按照其递推公式写出的递归函数如下：

public static int fib(int n) throws Exception {
    if (n < 0)
        throw new Exception("参数不能为负！");
    else if (n == 0 || n == 1)
        return n;
    else
        return fib(n - 1) + fib(n - 2);
}

VS迭代

递归算法与迭代算法的设计思路区别在于：函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法

参考资料

怎么更好地终极理解递归算法