JavaScript 递归上

发表于 | 分类于

参考资料：
翻译连载 | 第 9 章：递归（上）－《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇

JavaScript 递归上

定义

所谓递归，是当一个函数调用自身，并且该调用做了同样的事情，这个循环持续到基本条件满足时，调用循环返回。

⚠️ 警告： 如果你不能确保基本条件是递归的 终结者，递归将会一直执行下去，并且会把你的项目损坏或锁死；恰当的基本条件十分重要！

直接递归

当一个函数调用自身时，很明显，这叫作直接递归

简单的函数递归

1
2
3
4
5
6
function foo(x) {
    if (x < 5) return x;
    return foo(x / 2);
}

console.log(foo(16));

求质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 
 * 判断一个数是否是质数：
 * 从2到 num 的平方根之间的每个整数，看是否存在某一整数可以整除 num (% 求余结果为 0)。
 * 如果存在这样的整数，那么 num 不是质数。反之，是质数。
 * 
 * @param {number}  num  被判断是否是质数
 * @param {number} divisor 
 */

function isPrime(num, divisor = 2) {
    // 出口，非质数
    if (num < 2 || (num > 2 && num % divisor == 0)) {
        return false;
    }

    // 入口，递归的条件
    if (divisor <= Math.sqrt(num)) {
        return isPrime(num, divisor + 1);
    }

    // 出口，质数
    return true;
}

console.log(isPrime(40));

斐波那契数

1
2
3
4
fib( 0 ): 0
fib( 1 ): 1
fib( n ):
    fib( n - 2 ) + fib( n - 1 )
1
2
3
4
5
6
7
function fib(n) {
    // 出口，当n小于等于1时，结束递归
    if (n <= 1) return n;

    // 不满足，出口条件 ，持续递归
    return fib(n - 2) + fib(n - 1);
}

相互递归

如果在一个递归循环中，出现两个及以上的函数相互调用，则称之为相互递归。

求奇数偶数

1
2
3
4
5
6
7
8
9
10
11
function isOdd(v) {
    if (v === 0) return false;
    return isEven(Math.abs(v) - 1);
}

function isEven(v) {
    if (v === 0) return true;
    return isOdd(Math.abs(v) - 1);
}

console.log(isEven(31));

简单迭代改为递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * 循环求和
 * @param {number} total 求和
 * @param {array} nums 参数数组
 */
function sum(total, ...nums) {
    for (let i = 0; i < nums.length; i++) {
        total = total + nums[i]
    }

    return total;

}


/**
 * 递归求和
 * @param {number} total 求和
 * @param {array} nums 参数数组
 */
function _sum(num1, ...nums) {
	// 每次取到传入的第一个参数，参数列表数量每次少一个
    if (nums.length == 0) return num1;
    return num1 + _sum(...nums);
}


console.log(_sum(0, 1, 2, 3, 4, 10))

找出入参最大偶数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 找出入参最大偶数值
 * @param {*} nums 
 */
function maxEven(...nums) {
    var num = -Infinity;

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 == 0 && nums[i] > num) {
            num = nums[i]
        }
    }
    if (num !== -Infinity) {
        return num;
    }
}

/**
 * 
 * 递归法，找出入参最大偶数值
 * @param {any} num1 
 * @param {any} restNums 
 * @returns 
 */
function _maxEven(num1, ...restNums) {
    var maxRest = restNums.length > 0 ? _maxEven(...restNums) : undefined;
    return (num1 % 2 != 0 || num1 < maxRest) ? maxRest : num1;
}


console.log(_maxEven(9878, 45, 65, 98, 65))