递归及练习

ljp1997 2019-09-01 原文

10.递归

先传递，后回归。必须有跳出才有结果。自己调用自己。

找规律
eg:
用递归算阶乘   5的阶乘   1 * 2 * 3 * 4 * 5
分析：
5！  ==     5    *     4！

4！  ==     4    *     3！

3！  ==     3    *     2！

2！  ==     2    *     1!


fn(5);
return 5 * fn(4);

fn(4)
return 4 * fn(3)

fn(3)
return 3 * fn(2)

fn(2)
return 2 * fn(1)

......

//实现
function fn(n){
    if(n == 1) return 1;
    return n * fn(n-1);
}
console.log(fn(5));

11.递归案例

1.利用递归求1-100的和
//分析
// 100 + fn(99);
// 99 + fn(98);

//实现
function sum(n){
if(n <= 1) return 1;
return n + sum(n-1);
}
console.log(sum(5));
2.兔子 3个月成年  ——>  繁殖
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987
//分析：
fn(n) = fn(n-1) + fn(n-2);

fn(10) = fn(9) + fn(8);
fn(9) = fn(8) + fn(7);
fn(8) = fn(7) + fn(6);
....

function fn(n){
    if(n == 1 || n == 2){
        return 1;
    }
    return fn(n-1) + fn(n-2);
}
console.log(fn(8));
3.求最大公约数(辗转相除法（计算过程为：两个数相除得到余数，余数不为0时，让两个数中的最小数与余数在相除，直到余数为0时，那个最小数就为它们的最大公约数）)
function fn(m,n){
    var r = m % n;
    m = n;
    n = r;
    if(r == 0){
        return m;
    }else{
        return fn(m,n);
    }
}
console.log(fn(16,8));
4.编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,当输入n为奇数时，调用函数求/1+1/3+...+1/n