面试题：JavaScript递归函数在树结构遍历中的应用

Question

假设有一个用JavaScript对象表示的树结构，如下： ```javascript const tree = { value: 1, children: [ { value: 2, children: [ { value: 4, children: [] }, { value: 5, children: [] } ] }, { value: 3, children: [ { value: 6, children: [] } ] } ] }; ``` 编写一个递归函数，实现对这棵树的深度优先遍历（DFS），并返回一个包含所有节点值的数组。同时阐述在这种场景下递归函数相较于迭代方法的优势和劣势。

Answer 1

代码实现

function dfsTraversal(node) {
    const result = [];
    result.push(node.value);
    for (const child of node.children) {
        result.push(...dfsTraversal(child));
    }
    return result;
}

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

const result = dfsTraversal(tree);
console.log(result); 

递归函数相较于迭代方法的优势

1. 代码简洁：递归的实现通常更加简洁直观，它遵循树的自然递归结构，对于复杂的嵌套结构，代码逻辑更为清晰，更容易理解和编写。比如在上述代码中，仅通过简单的几行代码就实现了深度优先遍历。
2. 易于调试：由于递归函数遵循树形结构，在调试时可以较为容易地理解函数调用栈的顺序，方便定位问题。

递归函数相较于迭代方法的劣势

1. 栈溢出风险：JavaScript的调用栈是有一定限制的。对于非常深的树结构，递归调用会不断压入栈中，可能导致栈溢出错误（RangeError: Maximum call stack size exceeded）。而迭代方法可以通过合理的数据结构（如栈）来手动管理调用过程，避免栈溢出问题。
2. 性能开销：递归函数每一次调用都会在栈中创建新的执行上下文，这会带来一定的空间和时间开销。相比之下，迭代方法在循环中复用相同的上下文，性能上会更优，尤其是对于大规模数据的处理。