数据结构与算法之递归 yinshibanxian

17 May 2020 1107字 4分 次
BY-SA 4.0（除特别声明或转载文章外）

什么是递归

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。

递归通常涉及函数调用自身。

递归函数是像下面这样能够直接调用自身的方法或者函数:

function recursiveFunction(someParams) {
    recursiveFunction(someParams);
}

递归函数必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归。

递归的一般形式:

function understandRecursion(doIunderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if(recursionAnswer) {
        return true
    }
    understandRecursion(recursionAnswer)
}

递归的经典应用

1.计算一个数的阶乘
  1. 迭代法
function factorial(num) {
    if(num < 0) {
        return undefined;
    }
    let total = 1;
    for(let i = num;i > 1;i --) {
        total *= i;
    }
    return total;
}
  1. 递归法

可以发现, factorial(5) = 5 * factorial(4); factorial(4) = 4 * factorail(3); factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1); factorial(1) = 1 factorial(0) = 0; 可以发现，求阶乘的过程其实就是递归的过程，且基线条件为 num === 0 || num === 1

function factorial(num) {
    if(num === 1 || num === 0) {
        return 1;
    }
    return num * factorial(num - 1);
}
2.斐波那契数列

  1. 迭代法

  2. 递归法

function fibonacci(n) {
    if(n < 1) return 0;
    if(n <= 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
  1. 记忆法

可以看到，在求fibonacci(5)时，fibonacci(3)被计算了两次，因此，可以把结果先存储起来

function fibonacciMemo(n) {
    const memo = [0,1]
    const fibonacci = (n) => {
        if(memo[n] != null) {
            return memo[n];
        }
        return memo[n] = fibonacci( n - 1) + fibonacci( n -2) ;
    }
    return fibonacci(n);
}