• 递归的几种方式，以及递归的优化

拿斐波那契数列 的三种写法来举例：

递归

function fib(n) {
    if( n === 0){
        return 0
    }
    if(n === 1 || n === 2){
        return 1
    }

    return fib(n-1) + fib(n-2)
}

console.log(fib(3))     // 2
console.log(fib(5))     // 5
console.log(fib(10))    // 55

迭代

function fib2(n) {
    let arr = [0, 1, 1]
    for (let i = 3; i <= n; i++){
        arr[i] = arr[i-1] + arr[i-2]
    }
    return arr[n]
}
console.log(fib2(3))     // 2
console.log(fib2(5))     // 5
console.log(fib2(10))    // 55

尾递归

• 优化递归，减少栈的消耗，效率与迭代差不多

function fib3(n, pre = 0, next = 1) {
    if(n === 0){
        return pre
    }
    if(n === 1){
        return next
    }
    return fib3(n - 1, next, pre + next)
}
console.log(fib3(2))   // 1
console.log(fib3(3))     // 2
console.log(fib3(5))     // 5
console.log(fib3(10))    // 55

递归扩展

function hanoi(n, x, y, z) {
    if(n === 0){
        return
    }
    hanoi(n - 1, x, z, y)
    console.log(`${++num}: 把第${n}个盘子从${x}移动到${z}`)
    hanoi(n - 1, y, x, z)
}

let hanioNum = 4, num = 0;
// hanoi(hanioNum, 'A', 'B', 'C')