功能無限遞歸的麻煩

我一直在工作，因爲昨天才得到這個函數的工作，但它不是。我已經嘗試了一切。我正在使用具有深度遞歸的函數。我得到的輸出是很奇怪：功能無限遞歸的麻煩

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.爲什麼這只是繼續前進？

如果你想知道，該節點的構造函數不會再次致電建設者。構造函數不會調用任何外部函數，現在它的方法就是從那裏來的。

來源

2011-03-17 Snowman

的可能重複[爲什麼我的方法進入無限遞歸？（http://stackoverflow.com/questions/5332811/why-is-my-method進入無限遞歸） – interjay 2011-03-17 22:10:52

我不知道，它實際上顯示他們永遠;它可能會持續一段時間。

你的遞歸函數，使在每個級別4遞歸調用和從深度8運行到深度0。這意味着總共有在底部4 = 65536遞歸調用是，4 = 16384呼叫在深度1等，總共有87381個調用正在進行，如果每個調用都打印出一行文本並執行內存分配，那麼如果長時間繼續執行，它並不會讓我感到驚訝。此外，由於您按價值購買了BMP，因此您在每次迭代時都會複製圖像（除非它在內部做了一些奇特的事情），這會使整個過程更加緩慢。

至於你爲什麼看到1 0 0 0 1 0 0 0，我想這是因爲每當你在深度d展開一個節點時，在你回到d-1級別之前，你將完全展開所有的孩子。這意味着當你第一次嘗試在第二層展開一個節點時，你將在第一層擴展出四個節點，每一個節點打印出1 0 0 0，然後你將在第二層展開該節點並繼續其在深度2處的兄弟將再次打印出1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0。

總之，我不知道，這真的是在你的代碼錯誤，還是一個只是一個非常大的數量的遞歸調用。

來源

2011-03-17 22:05:41 templatetypedef

這是我第一次想到 – hirschhornsalz 2011-03-17 22:08:08

嗯，我想我想要這麼多的電話。從來沒有這樣想過。我使用四叉樹來表示256x256圖像。葉節點將保存每個像素，這意味着我將有65,536個葉節點以及像素。我的功能是爲我做的嗎？ – Snowman 2011-03-17 22:09:46

@ bitmoe-使用四叉樹的部分原因是如果圖像的某些區域具有相同的內容，則您**不需要全部65,536個節點，因爲您可以合併對應於相同像素顏色的節點。所以是的，我認爲你的工作方式和你的方法都有適當數量的遞歸調用，但我建議考慮從下而上而不是從上到下構建四叉樹，或者至少一些邏輯來合併相同的節點並在可能時修剪樹。 – templatetypedef 2011-03-17 22:14:09

這不是一個無限遞歸，但它將執行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 
    87381

來源

2011-03-17 22:09:16

我得到了4^8的不同數字。你的號碼是從哪裏來的？ – templatetypedef 2011-03-17 22:14:26

@templatetypedef：我的編號是經驗派生的 - 我簡化了代碼，編譯並運行它 - 參見上文。它看起來像是1 + 4 + 16 + 64 + 256 + 1024 + 4096 + 16384 + 65536 = 87381. – 2011-03-17 22:15:35

啊，我看到了我的錯誤。我沒有把所有的關卡都加在一起。 – templatetypedef 2011-03-17 22:18:06

這類似於前序遍歷。在根節點打印深度，然後遞歸調用其子元素（這裏是4.）。假設深度爲8，分支因子爲4.在1級，我們有4^1個節點。在2級我們有4^2在深度8我們有4^8節點在底部。因此你可以期望看到4^8 0被打印，4^7 1被打印等等......它不會是無限的。我認爲你應該嘗試用3或4的小小的深度嘗試，你會發現它會終止。我看不出爲什麼它是無限遞歸。

來源

2011-03-17 22:09:40 Srikanth

對我來說似乎很好。這實際上並不是無限的。再往下看你的輸出，最終你會看到像210000，310000等等的東西。你在深度大於0的每一遍都調用這個函數4次。

來源

2011-03-17 22:10:30 Rob

如果你看一下它的代碼是（實際上沒有做任何事情，只是爲了跟蹤）最簡單的形式：

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))

來源

2011-03-17 22:11:48 spbots

功能無限遞歸的麻煩

回答

相關問題