递归

不死神兔:斐波那契数列

该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

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

爬楼梯:力扣70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

function climb(n){
    if(n==1||n==2){
        return n
    }
    return climb(n-1) + climb(n-2);
}

递归优化

斐波那契数列的优化

function fib(n){
    if(n <= 1){
    return n
    }
    var p1 = 0;
    var p2 = 1;
    var cur;
    for(var i = 2;i <= n;i++){
        cur = p1 + p2;
        p1 = p2;
        p2 = cur;
    }
    return cur;
}
文档更新时间: 2022-04-27 17:40   作者:张老师