递归

递归是一种编程技巧,当一个函数在运行过程中调用自身,便被称为递归。

当我们计算一个数的阶乘时,第一反应是用循环,那么写法如下:

$$jsdemo$$
$$edit$$
function factorial(n) {
    let result = 1

    for (let i = 1; i <= n; i++) {
        result *= i
    }
    return result
}

alert(factorial(5)) // 120

如果我们改用递归的思路,那么写法如下:

$$jsdemo$$
$$edit$$
function factorial(n) {
    // 阶乘
    if (n === 1) {
        return 1
    }
    return n * factorial(n - 1)
}

alert(factorial(5)) // 120

$$tip 递归函数有一个特征,至少有两个 return 分支,一个是非递归调用的返回值(通常称为出口),另一个是递归调用的返回值。 $$

递归遍历

以下例子中,使用递归对一个多维数组进行了遍历,对所有的数字求和。

$$jsdemo$$
$$edit$$
const numbers = [
    5,
    100,
    31,
    [66, 77, 20],
    55,
    [4, 5, 6, [9, [11, 22, 33], 8, 7]],
]

function sum(x) {
    if (Array.isArray(x)) {
        // 数组,递归求和
        let total = 0
        x.forEach(function (item) {
            total += sum(item)
        })
        return total
    } else {
        // 数字,直接返回
        return x
    }
}

alert(sum(numbers)) // 459

练习

  1. 用递归实现一个函数,接收 nx 两个正整数,随机返回小于 n 且能被 x 整除的正整数。
function randInt(n, x) {
    // 补充完成
}

// 小于 100 的随机数,且能被 3 整除。
alert(randInt(100, 3)) // 27
alert(randInt(100, 3)) // 75
alert(randInt(100, 3)) // 60

$$answer


$$jsdemo$$
$$edit$$
function randInt(n, x) {
    console.assert(n > x, "n 必须大于 x")

    const result = Math.floor(Math.random() * n)

    if (result != 0 && result % x === 0) {
        return result
    }

    return randInt(n, x)
}

// 小于 100 的随机数,且能被 3 整除。
alert(randInt(100, 3)) // 27
alert(randInt(100, 3)) // 75
alert(randInt(100, 3)) // 60

$$

  1. 存在如下的公司员工数据,用递归求出总的薪水( 所有 salary 的和)。
const company = {
    sale: [
        {
            name: "小青",
            salary: 750,
        },
        {
            name: "小紫",
            salary: 950,
        },
    ],
    development: {
        app: {
            android: [
                {
                    name: "小明",
                    salary: 1000,
                },
            ],
            ios: [
                {
                    name: "小红",
                    salary: 800,
                },
            ],
        },
        web: [
            {
                name: "小蓝",
                salary: 1200,
            },
            {
                name: "小绿",
                salary: 900,
            },
        ],
    },
}

function sumSalary(department) {
    // 补充完成
}

// 总薪水
alert(sumSalary(company)) // 5600

$$answer

$$jsdemo$$
$$edit$$
const company = {
    sale: [
        {
            name: "小青",
            salary: 750,
        },
        {
            name: "小紫",
            salary: 950,
        },
    ],
    development: {
        app: {
            android: [
                {
                    name: "小明",
                    salary: 1000,
                },
            ],
            ios: [
                {
                    name: "小红",
                    salary: 800,
                },
            ],
        },
        web: [
            {
                name: "小蓝",
                salary: 1200,
            },
            {
                name: "小绿",
                salary: 900,
            },
        ],
    },
}

function sumSalary(department) {
    if (Array.isArray(department)) {
        return department.reduce(
            (prev, current) => prev + current.salary,
            0
        ) // 数组薪资的和
    } else {
        let sum = 0
        for (let item of Object.values(department)) {
            sum += sumSalary(item)
        }
        return sum
    }
}

// 总薪水
alert(sumSalary(company)) // 5600

$$