递归计算栈元素总和为何输出6而非预期的13？

嘿，我来帮你揪出这个问题的根源！你遇到的情况是递归调用时没有正确传递累加后的结果，导致最终返回的只是第一次弹出元素的数值。先来看下你的代码：

void testSum(){ 
    Stack<Integer> myStack = new Stack(); 
    myStack.add(3); 
    myStack.add(4); 
    myStack.add(6); 
    System.out.println(calculateSum(myStack, 0)); 
}

Integer calculateSum(Stack<Integer> myStack, int sum) { 
    if (!myStack.empty()) { 
        sum = sum + myStack.pop(); 
        calculateSum(myStack, sum); // 这里的递归结果完全被丢弃了！
    } 
    return sum; 
}

问题到底出在哪？ #

咱们一步步理清楚递归的执行过程：

• 第一次调用calculateSum：栈里是[3,4,6]，弹出6，sum变成0+6=6，然后发起递归调用（此时栈只剩[3,4]）
• 第二次递归调用：弹出4，sum变成6+4=10，再发起递归调用（此时栈只剩[3]）
• 第三次递归调用：弹出3，sum变成10+3=13，栈空了，返回13
• 重点来了：第二次递归调用根本没接收这个13，它直接返回自己的sum=10；第一次递归也没接收第二次的返回值，直接返回sum=6

说白了，你后面两次递归的累加结果都白费了，最后只返回了第一次弹出6后的sum值，自然就得到6而不是13了。

怎么修复这个问题？ #

只需要把递归调用的结果赋值给sum，让累加结果能逐层传递回来就行。这里给你两种写法：

写法一：显式接收递归返回值

Integer calculateSum(Stack<Integer> myStack, int sum) { 
    if (!myStack.empty()) { 
        sum = sum + myStack.pop(); 
        sum = calculateSum(myStack, sum); // 把递归的结果赋值给sum，传递回去
    } 
    return sum; 
}

写法二：更简洁的递归返回方式

Integer calculateSum(Stack<Integer> myStack, int sum) { 
    if (myStack.empty()) {
        return sum; // 栈空时返回当前累加的sum
    }
    // 直接把累加后的值传入递归，并返回递归结果
    return calculateSum(myStack, sum + myStack.pop());
}

这样修改后，递归的累加结果会一层层传递回来，最终返回的就是3+4+6=13啦！

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