了解递归函数的执行顺序 [英] Understanding the Order of Execution of Recursive Functions
问题描述
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的给定堆栈的元素，唯一的条件是必须在函数末尾恢复堆栈的完整性.意思是，只要函数与函数终止时通过之前的状态相同，我就可以对堆栈进行更改以对元素求和.
The code above is designed to recursively sum the elements of any given stack of type T with the only condition being that the integrity of the stack must be restored at the end of the function. Meaning, I am allowed to make changes to the stack to sum the elements as long as it is in the same state as it was before it was passed when the function terminates.
您将看到给定的代码，但是我不理解递归调用和return语句的控制流或执行顺序.当我看到这段代码时，我了解了元素的求和方式，但是我不理解对"s.push(first)"的调用如何将元素的 all 添加回堆栈中.我很难理解为什么它不会只推栈的最后一个元素然后返回总数.
As you will observe the given code works however I do not understand the control flow or execution sequence of the recursive calls and return statements. When I see this code I understand how the elements are summed, however I do not understand how the call to "s.push(first)" adds all of the elements back on to the stack. I'm having a hard time wrapping my head around why it wouldn't solely push the last element of the stack and then return the total.
我目前对此工作原理的理解还不完整，并且可能存在缺陷，原因如下:因为每个return语句都返回到最新的调用方，所以当递归命中基本情况并终止时，return语句将以自己的方式进行备份递归调用堆栈，直到到达原始调用者为止，并因此在每次移动时都执行"s.push()"将堆栈向上备份.
My current understanding of why this works is incomplete and likely flawed and is as follows: because each return statement returns to the most recent caller, when the recursion hits the base case and terminates, the return statements will work their way back up the recursive call stack until it gets to the original caller and therefore executing "s.push()" at each movement back up the stack.
给我造成混乱的是一旦堆栈为空后的执行顺序，我认为这是由于缺乏对函数递归返回调用堆栈的方式的了解所致.如果有人可以安排执行顺序并解释递归与递归调用下的操作一起工作的方式，我将不胜感激.谢谢！
What is causing confusion for me is the execution sequence once the stack is empty and I think it is due to a lack of understanding the way the function recurses back up the call stack. If someone could lay out the execution sequence and explain the way recursion works with operations underneath the recursive call that would me much appreciated. Thanks!
推荐答案
您的总体理解是正确的.您只缺少连接最后的点.
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.
这将有助于您了解是否标记每个递归调用.让我们将递归函数的初始调用称为" A ".当递归函数以递归方式调用自身时，调用递归函数的调用" B ".然后它再次调用，即为" C ".后跟" D "，依此类推.
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.
要理解的关键点是，当函数返回时，它会返回到调用它的位置.因此，" D "返回到" C "，然后返回到" B "，然后返回到" A ".
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".
现在看一下您的递归函数.当堆栈剩下一个值时，我们将其称为" D "，它从堆栈中删除" D "值，并进行递归调用" E "，发现堆栈为空.
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.
因此它返回到" D "，这会将" D "的值推回到堆栈中，该堆栈现在又具有一个值.然后返回" C "，将" C "的值推回到堆栈中，该堆栈现在在堆栈中有两个原始的最后一个值.相同的顺序.
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.
以这种方式，该函数以与原始调用顺序相反的顺序调用unwind，将堆栈恢复到原来的状态.
In this fashion, the function calls unwind in reverse order from their original calling sequence, restoring the stack to exactly what it was, originally.
这篇关于了解递归函数的执行顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
