递归

递归


递归是非常广泛的计算机编程技巧,理解递归,只需要把这两个字拆解开就可以了,即 “递” 与 “归”,递就是把问题传递出去,或者叫把一个问题拆成下一个子问题求解。归就是把递出去的问题答案反向通知回来。

递归

举一个上学时候的例子,军训的时候若干个同学排成一排,其中中间的某个同学不知道自己在第几排,这时候,这个同学就会问前边一个同学是第几排,前一个同学也不知道,只好继续往前问,直到问到第一排的同学说自己是在第一排,于是第二排的同学知道了自己在第二排,这样以此类推,把排数向后传回去,最初那个问自己在第几排的同学也就知道了答案。

所以递归具有以下两个特点:

1:当前求解的问题,可以拆解为规模更小的相同问题,小规模的问题和原问题求解思路完全相同。
2:存在边界条件,到达这个边界条件后,问题由“递”变为“归”。

计算机编程中,递归通常表现为函数自己调用自己(每次调用,问题规模更小),直到达到边界后不再产生新的函数自调用,开始归的过程,最具代表性的递归求解的问题有以下几个:

  1. 数的阶乘:
int factorial (int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
  1. 斐波那契序列
// 斐波那契序列 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...
int fibonacci (int n) {
    if (n == 1) {
        return 0;
    }

    if (n == 2) {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

理论上递归都可以用循环来实现


递归其实就是循环的过程,只不过不是代码上的循环,而是函数调用栈的循环,所以理论上,递归问题都可以用循环迭代解决。

  1. 数的阶乘循环实现:
int factorial1 (int n) {
    int ret = 1;
    for (int i = 1; i <= n; i++) {
        ret = i * ret;
    }
    return ret;
}
  1. 斐波那契序列循环实现
int fibonacci1 (int n) {

    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 0;
    }

    if (n == 2) {
        return 1;
    }

    int pre = 1;
    int prepre = 0;
    int ret = 0;
    for (int i = 3; i<= n; i++) {
        ret = prepre + pre;
        prepre = pre;
        pre = ret;
    }

    return ret;
}

很明显的可以看出,用递归的方式实现,代码更加简洁美观,但我们知道函数调用,会不停的开辟栈空间,递归实现尤其需要注意栈溢出问题,所以递归不适合大规模的问题编程求解。部分语言的编译器或者解释器支持了尾调用优化,再某种程度就是解决栈溢出问题,节省内存。

不要去脑展开递归的全过程


理解递归的时候,人脑本能的想把递归的全过程展开,但是人脑的脑容量通常是有限的,当问题规模很大的时候,人脑是无法展开全部的递归过程的,强行闹展开失败后,只会让自己怀疑自己的智力问题,进入思维误区;如果非要脑展开全过程,可以用很小的规模数展开验证。

例如下列递归问题:

假如这里有 n 个台阶,每次你可以跨 1 个台阶或者 2 个…请问走这 n 个台阶有多少种走法?对于这个问题,当台阶只有 3 个的时候,我们很容易想到有,2、1 或者 1、2 或者 1、1、1 三种走法,但是如果是 7 个台阶的时候,人脑就不能立刻想清楚到底有几种走法,这时,我们可能需要笔和纸来记录一部分走法,释放一部分脑容量,才能思考清楚。

而如果我们不展开全过程,用递归的方式思考,应该是这个样子的:

  1. 对于当前 n 个台阶的走法,仅考虑下一步的话,只有两种方式,即走 1 阶台阶或者走 2 阶台阶,这两种走法就会对当前 n 个台阶产生两种完全不同的路线;如果走 1 个台阶,问题就变为 n -1 个台阶走法的问题,如果走 2 个台阶,问题就变为 n – 2 个台阶走法的问题,所以得出通用的归纳法: f(n) = f(n-1) + f(n-2);
  2. 存在边界,当最后只剩 1 个台阶时,只剩一种走法;如果剩余 2 个台阶,剩两种走法。

所以可以写出递归函数:

int ff (int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return ff(n - 1) + ff(n - 2);
}

递归中的重复计算


仔细看上边的 n 个台阶的走法的递归函数,其中会有重复的函数计算:

递归

包括之前的斐波那契数列,多次调用后都会有重复的计算,我们可以稍加修改代码,来避免重复计算

int ff (int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }

    // solvedList 可以理解成一个 Map
    if (solvedList.contain(n)) {
        return solvedLis.get(n);
    }

    int ret = ff(n - 1) + ff(n - 2);
    solvedLis.put(n, ret);
    return ret;
}

(完)

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注