Recursion是编程思想中最令人兴奋的部分.

一、Recursion递归的第一原则Base-Case

Base-Case又名Terminating-Case,比如倒数到N:

function countToN(n) {
    if (n < 0) {
        return;
    }
    else {
        console.log(n);
        countToN(n - 1);
    }
}

countToN(11);

二、Recursion的第二原则Divide-and-Conquer

最著名的案例就是fibonacci数列:

function fib(n) {
    if (n < 1) {
        return n;
    }
    let b = 1;
    let a = 0;
    for (let i = 1; i < n; i++) {
        sum = a + b;
        a = b;
        b = sum;
    }
    return sum;
}

console.log(fib(11));

将其改写为Recursion 的写法:

function betterFib(b, a, n) {
    if (n == 0) {
        return a;
    }
    else if (n == 1) {
        return b;
    }
    else {
        return betterFib(b + a, b, n - 1);
    }
}

console.log(betterFib(1, 0, 11));

三、再来实现一个帕斯卡三角:

应用上面的 base-case 与pide-and-conqure 的思路实现帕斯卡三角:

function pascalTriangle(row, col) {
  if (col == 0) {
    return 1;
  } else if (row == 0) {
    return 0;
  } else {
    return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
  }
}
console.log(pascalTriangle(11, 9)); /// 55
  

四、总结

Recursion就是base-case(terminating-case)加上pide-and-conqure.