递归算法题.md

递归的关键

1. 将一个复杂问题分解为子问题
2. 数学归纳法，本质是寻找重复性
3. 拒绝人肉递归

1. 斐波那契数列

[1,1,3,5,8,13,21...]

除去第一项和第二项外，后续项都是前两项之和

最粗暴的实现：容易栈溢出

const fibonacci = function(count){
    if(count <= 2) return 1
    return fibonacci(count-2) + fibonacci(count-1)
}

动态规划：

const fibonacci = function(count){
    const cache = [1,1]
    for (let index = 2; index < count; index++) {
        cache[index] = cache[index-2] + cache[index-1]
    }
    return cache[count-1]
}

将每一次递归需要的值传入

const fibonacci = function(count){
    function fn(count, curr = 1, next = 1){
        if(count === 0) return curr
        return fn(count-1, next, curr + next)
    }
    return fn(count)
}

2. 输入一个正整数n，输出所有和为n的连续正数序列

const fn = function(count, start, res){
    const mid = Math.ceil(count / 2)
    let index = start
    let arrCount = 0
    let tempArr = []
    while(index <= mid && arrCount < count){
        tempArr.push(index)
        arrCount += index
        if(arrCount === count){
            res.push(tempArr)
            break
        }
        ++index
    }
    if(start <= mid) return fn(count, start+1, res)
}

const func = function(count){
    let res = []
    fn(count, 1, res) 
    return res
}
console.log(func(4))  // []
console.log(func(5))  // [ [ 2, 3 ] ]
console.log(func(10)) // [ [ 1, 2, 3, 4 ] ]
console.log(func(15)) // [ [ 1, 2, 3, 4, 5 ], [ 4, 5, 6 ], [ 7, 8 ] ]