递归为何无法自动处理变量状态？二叉树递归场景对比

场景一：收集根到叶的所有路径 #

class Node {
    constructor (val) {
        this.val   = val;
        this.left  = null;
        this.right = null; 
    }
}

const a = new Node('10');
const b = new Node('20');
const c = new Node('30');
const d = new Node('40');
const e = new Node('60');


a.left = b;
a.right = c;
b.left = d;
b.right = e;

function Paths(root){
        let paths = [];
        function traverse(node, path){
            if(!node){
                return;
            }
            path.push(node.val);
            if(node.left ==null && node.right ==null){
                paths.push(path.slice());
            }
            traverse(node.left,path);
            traverse(node.right,path);
            path.pop();
        }
        traverse(root,[]);
        console.log(paths);
        return paths;
    }
    Paths(a);

疑问解答：递归共享path时为何无法自动恢复状态？ #

因为path是引用类型（数组），递归调用时传递的是同一个数组的引用——所有递归栈中的函数操作的都是内存里的同一个数组实例。

比如遍历路径10→20→40时，path被push成['10','20','40']，处理完叶子节点40后递归返回至节点20，如果不执行path.pop()，数组会保持这个状态。接下来处理节点20的右子节点60时，就会把60push到同一个数组里，变成['10','20','40','60']，这显然不是我们要的10→20→60路径。

所以必须通过path.pop()手动回溯：在离开当前节点时，把节点值从数组中移除，让path恢复到进入该节点前的状态，这样后续处理其他分支时才不会被之前的操作污染。

场景二：判断是否存在和为目标值的根到叶路径 #

class Node {
    constructor (val) {
        this.val   = val;
        this.left  = null;
        this.right = null; 
    }
}

const a = new Node('1');
const b = new Node('2');
const c = new Node('3');
a.left = b;
a.right = c;


var hasPathSum = function(root, targetSum) {
    if(!root){
        return 0;
    }
    function dfs(node, currsum){
        if(!node){
            return false;
        }
        currsum+=Number(node.val);
        if(node.left ==null && node.right ==null){
            return currsum == targetSum;
        }

        return dfs(node.left,currsum) || 
        dfs(node.right,currsum);
    }
    return dfs(root, 0);
};

let targetSum =31;
console.log(hasPathSum(a, targetSum));

疑问解答：为何无需回溯操作？ #

因为currsum是基本类型（数字），在JavaScript中基本类型是按值传递的：每次递归调用时，会把currsum的当前值复制一份，作为新的变量传给下一层递归函数。

比如在节点1时currsum是1，调用左子节点2时，会创建一个新的currsum变量，值为1+2=3，这个新变量和上层的currsum=1完全独立；同理，处理右子节点3时，用的还是上层的currsum=1，计算后得到新的currsum=4。每个递归分支的currsum都是各自独立的副本，不会互相干扰，因此不需要手动回溯恢复状态。

内容的提问来源于stack exchange，提问作者amit