JS 递归函数详解|极客笔记

JS 递归函数详解

在编程中，递归是一种解决问题的方法，通过调用自身函数来解决问题。在JavaScript中，递归就是函数调用自身的技术。递归函数通常用于处理具有递归结构的数据或任务，如树结构、图结构等。本文将详细介绍JS中递归函数的原理、用法和示例。

递归函数原理

递归函数的原理非常简单，就是函数在执行过程中调用了自身。在递归函数中，有两个关键要素：

基本情况（Base Case）：递归函数必须有一个能够结束递归的条件，称为基本情况。当递归函数执行到基本情况时，递归调用将停止，避免无限循环。
递归调用：在递归函数内部，通过调用自身来解决更小规模的同类问题，直到达到基本情况为止。

递归函数的执行过程可以用下面的示例来说明：

function factorial(n) {
    if (n === 0) {
        return 1; // 基本情况
    } else {
        return n * factorial(n - 1); // 递归调用
    }
}

console.log(factorial(5)); // 输出 120

在上面的示例中，factorial函数计算了n的阶乘（n!）。当n为0时，函数返回1作为基本情况；否则，函数返回n与factorial(n-1)的乘积，实现了递归调用。

递归函数用法

递归函数在实际编程中有很多应用场景，包括但不限于：

遍历树结构：递归函数可以方便地遍历树形结构，如DOM树、文件目录树等。
解决复杂问题：某些问题本身就具有递归结构，递归函数可以简洁地解决这类问题，如斐波那契数列、汉诺塔问题等。
迭代器模式：通过递归函数实现迭代器模式，处理集合中的每个元素。

下面我们通过几个示例来展示递归函数的用法。

遍历树结构

假设有一个简单的树结构如下：

const tree = {
    value: 1,
    children: [
        {
            value: 2,
            children: [
                { value: 4, children: [] },
                { value: 5, children: [] }
            ]
        },
        {
            value: 3,
            children: [
                { value: 6, children: [] }
            ]
        }
    ]
};

我们可以使用递归函数来遍历这棵树，并输出每个节点的值：

function traverseTree(node) {
    console.log(node.value);
    node.children.forEach(child => traverseTree(child));
}

traverseTree(tree);

运行上面的代码，会输出以下结果：

求斐波那契数列

斐波那契数列是一个经典的递归问题，定义如下：

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

我们可以使用递归函数来求解斐波那契数列：

function fibonacci(n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

console.log(fibonacci(5)); // 输出 5

汉诺塔问题

汉诺塔问题是一个著名的递归问题，其规则如下：

每次只能移动一个圆盘
大圆盘不能放在小圆盘上面

我们可以使用递归函数来解决汉诺塔问题：

function hanoi(n, start, temp, end) {
    if (n === 1) {
        console.log(`Move disk 1 from  ${start} to$ {end}`);
    } else {
        hanoi(n-1, start, end, temp);
        console.log(`Move disk  ${n} from$ {start} to ${end}`);
        hanoi(n-1, temp, start, end);
    }
}

hanoi(3, 'A', 'B', 'C');

运行上述代码，会输出移动圆盘的步骤：

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C