递归

  • 电影院
  • 求阶乘
  • 斐波那契数
  • 数字反转
  • 求台阶走法数

当然，很多递归都是可以优化的，比如f(n)=f(n-1)+f(n-2),这里f(n-2)就会计算两次，可以用散列表存储已经计算的数据，但是这里主要演示递归思想，不再进行优化。

电影院

周末你带着女朋友去电影院，女朋友问你，咱们现在坐在第几排啊，电影院太黑没法数怎么办，于是你问前一排的人他是第几排，你只需要在他的数字上加一就知道自己是第几排，但是前面的人也看不清啊。所以他也问前面的人，就这样一排一排的问直到问到第一排的人

  • 这是一个非常标准的递归求解问题的分解过程，去的过程叫递，回来的过程叫归。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来是这样的：

f(n) = f(n-1) +1 其中，f(1) = 1

  • f(n)代表你想知道自己在哪一排，f(n-1)表示前面一排所在的排树。核心代码如下：
public static int cinemas(int n){
        if (n == 1)
            return 1;
        return cinemas(n-1)+1;
    }

求阶乘

求阶乘思路跟上面差不多，其递推式为：

f(n) = f(n-1) * n

  • 核心代码如下：
    public static  int recursion(int n){
        if (n == 1) return 1;
        return recursion(n-1)*n;
    }

斐波那契数

斐波那契数的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……。依次类推下去，你会发现，它后一个数等于前面两个数之和，在这个数列中的数字，就被称为斐波那契数

  • 很容易得到斐波那契数的递推式为：

    f(n) = f(n-1) + f(n-2),其中f(0) = 0，f(1) = 1

  • 核心代码如下：

public static int recursion(int n){
        if (n <= 1) return n;
        return recursion(n-1) +recursion(n-2);
    }

数字反转

反转数字

  • 反转一个数字，可以用递归方法，直接上代码
public static void recursion(int n){
        System.out.println(n % 10);

        if (n >= 10){
            recursion(n / 10);
        }
    }

求台阶数

假设这里有n个台阶，每次你可以跨1个台阶或者两个台阶，请问走这n个台阶有多少种走法。

  • 每一次有两种走法，结束的条件是n = 1的时候只有一种走法，n = 2的时候有两种走法
    ，递归式如下：

    f(n) = f(n-1) + f(n-2)

  • 核心代码如下：
public static int recursion(int n){

        if (n == 1) return 1;
        if (n == 2) return 2;
        return recursion(n-1)+recursion(n-2);

    }

总结：

递归需要满足三个条件

  • 一个问题的解可以分为几个子问题的解
  • 这个问题与分解后的子问题，除了数据规模不同，求解方式相同
  • 存在递归终止条件

递归代码要警惕堆栈溢出

函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。可以用一个变量设置做多递归多少次，超过一定次数自己抛出异常

递归代码要警惕重复计算