函数中无限递归的问题
函数中无限递归的问题
提问于 2011-03-18 05:59:58
我从昨天开始就一直在努力让这个函数工作，但它就是不能工作。我什么都试过了。我使用的是一个有深度递归的函数。我得到的输出非常奇怪：
Im going in with depth: 8
Depth in builder: 8
Depth in builder: 7
Depth in builder: 6
Depth in builder: 5
Depth in builder: 4
Depth in builder: 3
Depth in builder: 2
Depth in builder: 1
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 1
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 0
Depth in builder: 1
.....然后它永远在1和0之间交替。这怎么可能呢？如果深度为0，这条线甚至不会显示。为什么这个一直在继续呢？
如果您想知道，节点的构造函数不会再次调用构建器。构造器没有调用任何外部函数，所以现在它是从那里来的。
回答 4
Stack Overflow用户
发布于 2011-03-18 06:09:17
它不是无限递归，但它将执行87381次，初始深度为8。
试着将它简化为递归部分，这样您就可以看到发生了什么：
//
// builder.cpp
//
#include <iostream>
using namespace std;
void builder(int depth) {
cout << "Depth in builder: " << depth << endl;
if (depth <= 0) {
return;
}
if (depth > 0) {
builder(depth - 1);
builder(depth - 1);
builder(depth - 1);
builder(depth - 1);
}
}
int main(void)
{
builder(8);
return 0;
}$ g++ -Wall builder.cpp -o builder
$ ./builder | wc -l
87381Stack Overflow用户
发布于 2011-03-18 06:11:48
如果你以最简单的形式来看你的代码(实际上没有做任何事情，只是为了跟踪)：
void f(int depth)
{
// print depth
cout << depth << endl;
if(depth <= 0)
return
else
{
// **FOUR** more calls to the recursive function.
f(depth - 1);
f(depth - 1);
f(depth - 1);
f(depth - 1);
}
}现在考虑深度为1的跟踪，您的输出是1 - 0 - 0 - 0，因为每次对f(1)的调用都会生成四个对f(0)的调用。现在考虑一下f(2)的输出--你会得到2 - <output of f(1) four times>。此模式可以扩展，因此您的预期输出是
Output(f(n)) =
n
Output( f(n-1) )
Output( f(n-1) )
Output( f(n-1) )Stack Overflow用户
发布于 2011-03-18 06:09:40
这类似于预订单遍历。打印根节点的深度，然后递归地调用它的子节点(这里是4.)。给定深度为8，分支因子为4。在级别1，我们有4^1个节点。在第二层，我们有4^2at，深度为8，底部有4^8个节点。因此，您可以期望看到打印4^80和打印4^7 1，等等。它不会是无限的。我认为你应该尝试小的深度，比如3或4，你会看到它终止了。我看不出为什么它是无限递归。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5345807
复制相关文章
相似问题
腾讯云开发者
