如何在递归中使用return函数。 [英] How to use return function in recursion.

问题描述

我有以下代码用于inorder遍历树：

I am having this below code for inorder traversal of tree:

void inOrder(struct node* r)
{
if (r==NULL)
return;

else{
inOrder(r->left);
printf("%d ", r->value);
inOrder(r->right);
    }
}

我有这个愚蠢的怀疑：



当最左边的子项以root身份传递时，它不为null。

在下一次迭代中，root将为null（因为左下角子项的左子项将为null）并且它将遇到返回。



这个return语句不会将控件传递给main函数（或者调用它的任何地方）而不打印任何东西吗？





返回的行为是否有所不同在递归？



我尝试过：

I am having this silly doubt:

When the bottom most left child is passed as root, it is not null.
In the next iteration root will be null (as left child of bottom most left child will be null) and it will encounter return.

Wont this return statement pass the control to main function (or wherever it is called) without printing anything?


Does return behave differently in recursion?

What I have tried:

<pre>
void inOrder(struct node* r)
{
if (r==NULL)
return;

else{
inOrder(r->left);
printf("%d ", r->value);
inOrder(r->right);
    }
}

推荐答案

每次调用函数时，都会使用一个称为堆栈的内存区域保持上下文，以便当函数退出时，您可以从继续的位置继续。它被称为堆栈，因为它可以容纳许多不同的函数调用上下文，并且在调用函数时总是向顶部添加新上下文，并在退出时从顶部删除最后一个。



假设你有一棵树：

Every time you call a function, an area of memory called a stack is used to hold the context so that when the function exits you can continue from where you continued. It's called a stack, because it can hold many different function call contexts, and always adds a new context to the top when you call a function, and removes the last one from the top when you exit.

Suppose you have a tree:

    A
   / \
  B   C
 / \
D  E

您将A传递给您的函数。

是否为空？否 - 使用正确的节点递归调用它：C。这会叠加上下文。

这一次，检查C是否为空。它不是，所以你递归调用函数传递给它的C.Right节点是空的。这个上下文得到了堆栈（所以现在有两个上下文）

检查是否为null。它是，所以你立即从函数返回。删除顶部上下文，并将其恢复。

从最后一次调用之后的语句继续执行，您正在处理C节点。你打印值C并重复左节点的过程。



尝试使用调试器，你很快就会明白这个想法！

You pass A to your function.
Is it null? No - Call it recursively with the right node: C. This stacks the context.
This time, you check if C is null. It isn't, so you recursively call the function passing it the C.Right node which is empty. This context gets stacks (so there are two contexts there now)
Check that against null. It is, so you return from the function immediately. Remove the top context, and restore it.
Execution continues from the statement immediately after the last call, where you were processing the C node. You print the Value "C" and repeat the process for the Left nodes.

Try it using the debugger, you'll soon get the idea!

如果你返回，你回到调用函数，而不是直接在main。



调试调用栈以理解它。一些输出总是有帮助。

If you return you come back to the calling function, not directly in main.

Debug the call stack to understand it. Some output always helps.

void inOrder(struct node* r)
{
printf("inoder %d ",(int) r);//debug output
if (r==NULL)
return;
 else{
//do your recursion work
printf("l-call: %d ", l->value);
inOrder(r->left);
printf("r-call: %d ", r->value);
inOrder(r->right);
    }
}

没有。肯定会返回，但只返回一个级别，而不是一直返回原始调用者。构建一个简单的5或6个节点树，然后使用调试器逐步执行代码。观察嵌套调用并返回。

No. It will return, sure, but only one level, not all the way back to the original caller. Build a simple tree of say 5 or 6 nodes, then step through your code with a debugger. Watch the nested calls and returns.

这篇关于如何在递归中使用return函数。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！