1.1 什么是递归

在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。也就是说,递归算法是一种直接或者间接调用自身函数或者方法的算法。通俗来说,递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。

 

1.2 递归的三大要素

1、 这个函数的功能;
他要完成什么样的一件事,而这个,是完全由你自己来定义的。也就是说,我们先不管函数里面的代码什么,而是要先明白,你这个函数是要用来干什么。

private static int fun(int number) {
     
       
        // to do something
}

2、 寻找递归结束条件;
递归在函数内部代码中,调用这个函数本身,所以,我们必须要找出递归的结束条件,否则进入死循环无法退出。因此,我们需要找出当参数满足条件时,递归结束,之后直接把结果返回。请注意,这个时候我们必须能根据这个参数的值,能够直接知道函数的结果是什么。
例如:当number =1时,满足条件,退出递归函数。

// 计算 number 的阶乘(假设number不为0)
private static int fun(int number) {
     
       
    if(number == 1){
     
       
        return 1;
    }
}

3、 找出函数的等价关系式;
要不断缩小参数的范围,缩小之后,我们可以通过一些辅助的变量或者操作,使原函数的结果不变。
只要if语句为true,每个fun()调用都将执行statement1,然后再调用fun(),而不会执行statements2 。当前调用结束后,程序控制权将返回给调用它的fun(),而该fun()将执行其statements2部分,然后结束,并将控制权返回给前一个调用,依次类推。

// 计算 number 的阶乘(假设number不为0)
private static int fun(int number) {
     
       
    // statements1
    if (number == 1) {
     
       
        return 1;
    }
    // statements2
    return number * fun(number - 1);
}

  • 动态图解
     

1.3 剖析递归

剖析「递归」,先有「递」再有「归」,「递」的意思是将问题拆解成子问题来解决, 子问题再拆解成子子问题,…,直到被拆解的子问题无需再拆分成更细的子问题(即可以求解),「归」是说最小的子问题解决了,那么它的上一层子问题也就解决了,上一层的子问题解决了,上上层子问题自然也就解决了,…,直到最开始的问题解决,文字说可能有点抽象,那我们就以阶层 f(6) 为例来看下它的「递」和「归」。
 

1.4 递归案例

  • 一只青蛙可以一次跳 1 级台阶或者一次跳 2 级台阶。问要跳上第 n 级台阶有多少种跳法?

  • 条件1:跳上第 1 级台阶只有一种跳法:直接跳 1 级即可。

  • 条件2:或者一次跳 2 级。

如果要跳到 n 级台阶只能从 从 n-1 或 n-2 级跳, 所以问题就转化为跳上 n-1 和 n-2 级台阶的跳法了,如果 f(n) 代表跳到 n 级台阶的跳法,那么从以上分析可得 f(n) = f(n-1) + f(n-2),显然这就是我们要找的问题与子问题的关系,而显然当 n = 1, n = 2, 即跳一二级台阶是问题的最终解,于是递推公式系为:
 

  • 将递推公式用代码实现:
    /**
     * 跳 n 极台阶的跳法
     */
    public static int jump(int n) {
   
     
        if (n == 1) {
   
     
            return 1;
        }
        if (n == 2) {
   
     
            return 2;
        }
        return jump(n - 1) + jump(n - 2);
    }

1.3 总结

1、 总结的解递归的三个步骤可以比较顺利的解开递归题,一些比较复杂的递归题我们需要勤动手,画画图,观察规律,这样能帮助我们快速发现规律,得出递归公式,一旦知道了递归公式,将其转成递归代码就容易多了;
2、 递归代码要警惕堆栈溢出:;
函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时,才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。可以用一个变量设置做多递归多少次,超过一定次数自己抛出异常。