递归调用后的代码递归

本文介绍了递归调用后的代码递归的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图了解递归是如何工作的，还有一件事我不太明白:当递归函数本身内的递归调用之后有代码时，递归函数是如何工作的.请参阅下面的示例伪代码以帮助理解我的意思.我的确切问题是递归调用之后的代码将按什么顺序(意味着什么时候)执行. 机器会注意到递归调用，在调用之后执行剩余的代码位(打印完成")，然后返回并实际执行整个递归调用，或者机器会在到达该行后立即执行递归调用，并在递归结束后仅执行最后一位代码(打印完成")out? 什么时候done"会被打印多少次?

I am trying to understand how recursion works and there is just one more thing that I do not quite understand: how a recursive function works when there is code after the recursive call within the recursive function itself. Please see below at the example pseudocode to help see what I mean. My exact question is in what order (meaning when) the code after that recursive call will be executed. Will the machine note the recursive call, execute the remaining bit of code after the call (print "done"), then go back and actually execute the entire recursive call, or will the machine execute the recursive call as soon as it gets to that line and only execute that last bit of code (print "done") after that recursion bottoms out? When and how many times will "done" be printed?

void recurse() { print "hello world"; for i = 0 up to 2 recurse(); print "done"; }

推荐答案

可视化递归的一个好方法是使用堆栈的深度/高度.您可能知道，每当调用一个新函数时，它都会像煎饼一样被压入堆栈，将深度/高度增加 1.和结束"带有缩进的注释以可视化深度，应该很容易看到什么时候执行.如果不清楚，时间在 Y 轴上(上面打印的内容在下面的内容之前执行)，递归深度在 X 轴上.

A good way to visualize recursion is using the depth/height of the stack. As you may know, whenever a new function is called, it's pushed onto the stack like a pancake, increasing the depth/height by 1. If you code it up and print your "start" and "end" notes with an indentation to visualize the depth, it should be easy to see what is executed when. In case it isn't clear, time is on the Y-axis (things printed above have executed before things below) and recursion depth is on the X-axis.

Python 代码如下:

Here's the code in Python:

def recurse(depth=0): if depth < 4: print(" " * depth + f"starting at depth {depth}") for _ in range(2): recurse(depth + 1) print(" " * depth + f"ending at depth {depth}") recurse()

输出:

starting at depth 0 starting at depth 1 starting at depth 2 starting at depth 3 ending at depth 3 starting at depth 3 ending at depth 3 ending at depth 2 starting at depth 2 starting at depth 3 ending at depth 3 starting at depth 3 ending at depth 3 ending at depth 2 ending at depth 1 starting at depth 1 starting at depth 2 starting at depth 3 ending at depth 3 starting at depth 3 ending at depth 3 ending at depth 2 starting at depth 2 starting at depth 3 ending at depth 3 starting at depth 3 ending at depth 3 ending at depth 2 ending at depth 1 ending at depth 0

可以看出，循环中产生了两个相同的递归调用.第一次循环执行在第二次开始之前完成其整个递归执行.两个递归调用完成后，整个调用结束.

As can be seen, there are two identical recursive calls that are spawned in the loop. The first trip through the loop completes its entire recursive execution before the second one begins. After both recursive calls complete, then the entire call ends.

另请注意，深度表示一个base case 或终端/叶节点没有孩子.您的原始算法将无限递归并炸毁堆栈.

Also note that the depth represents a base case or terminal/leaf node that has no children. Your original algorithm will recurse infinitely and blow the stack.