时间戳

首页 > 解决方案 > 了解递归函数的执行顺序

c++ - 了解递归函数的执行顺序

问题描述

template <typename T>
T sum(stack<T>& s){
    if (s.empty()){
        return 0;
    } else {
        T first = s.top();
        s.pop();
        T total = sum(s)+first;
        s.push(first);
        return total;
        }
}

上面的代码旨在递归地对任何给定类型 T 堆栈的元素求和，唯一的条件是堆栈的完整性必须在函数结束时恢复。意思是，我可以对堆栈进行更改以对元素求和，只要它处于与函数终止时传递它之前的状态相同的状态。

正如您将观察到的那样，给定的代码可以工作，但是我不理解递归调用和返回语句的控制流或执行顺序。当我看到这段代码时，我了解元素是如何求和的，但是我不明白对“s.push(first)”的调用如何将所有元素添加回堆栈。我很难理解为什么它不会只推送堆栈的最后一个元素然后返回总数。

我目前对其工作原理的理解是不完整的，并且可能存在缺陷，如下所示：因为每个 return 语句都返回到最近的调用者，所以当递归遇到基本情况并终止时，return 语句将以它们的方式支持递归调用堆栈直到它到达原始调用者，因此在每次移动时执行“s.push()”备份堆栈。

让我感到困惑的是堆栈为空后的执行顺序，我认为这是由于缺乏对函数递归备份调用堆栈的方式的理解。如果有人可以列出执行顺序并解释递归与递归调用下的操作的工作方式，我将不胜感激。谢谢！

标签： c++recursion

解决方案

Your overall understanding is correct. You're only missing connecting the final dots.

The key point to remember is when a function returns, it returns to wherever it was called from. Recursive functions are no different in that fundamental respect. Recursive function calls work exactly the same way.

It will help to understand if you label each recursive call. Let's call the initial invocation of the recursive function "A". When the recursive function calls itself, recursively, call that invocation of the recursive function "B". Then it calls again, and that's "C". Followed by "D", and so on.

The key point to understand is that when a function returns, it returns to wherever it was called from. So, "D" returns to "C", which returns to "B", and it returns to "A".

Now look at your recursive function. When the stack had one value left, let's call it "D", it removes the "D" value from the stack and makes the recursive call "E", which discovers that the stack is empty.

So it returns to "D", which pushes the "D" value back to the stack, which now has one value again. Then it returns to "C", which pushes the "C" value back to the stack, which now has the two original, last, values on the stack, in the same order.

In this fashion, the function calls unwind in reverse order from their original calling sequence, restoring the stack to exactly what it was, originally.

推荐阅读