這個例程使用多少堆棧空間？

假設樹是平衡的，那麼例行程序將爲多少個1,000,000個元素的樹使用多少堆棧空間？這個例程使用多少堆棧空間？

void printTree(const Node *node) { 
    char buffer[1000]; 
    if(node) { 
    printTree(node->left); 
    getNodeAsString(node, buffer); 
    puts(buffer); 
    printTree(node->right); 
    } 
}

這是在「程序員修煉」的算法中的問題之一，得到的答覆是需要21個緩衝區（LG（1M）〜= 20，與另外1在最頂部）

但我我認爲它需要多於一個低於頂層的緩衝區，這是由於對於左右節點的2次調用。有什麼我錯過了嗎？

*對不起，但這真的不是作業。請勿在本站的勘誤表上看到這一點。

來源

2011-09-27 Ming Tsai

主要部分是'char buffer [1000];'和它的堆棧大小非常依賴於語言。 –

首先進行左側節點調用，然後該調用返回（並且堆棧可用於重新使用），然後進行一些工作，然後調用正確的節點。

所以確實在下一級有兩個緩衝區，但這兩個緩衝區是連續的，不是同時需要的。因此，您只需要在高水位標記堆棧使用中計算一個緩衝區。重要的是函數遞歸的深度，而不是調用函數總共多少次。

這當然假設代碼是用類似於C的語言編寫的，並且C實現爲自動變量使用了一個堆棧（我還沒有看到一個沒有），等等等等。

來源

2011-09-27 22:08:24

啊！知道了，TNX！ :) –

第一次調用將一直遞歸到葉節點，然後返回。然後第二個電話將開始 - 但是在第二個電話發生時，第一個電話的所有激活記錄將被清除。 IOW，在任何給定的時間只有來自堆棧中的一個人的數據。

來源

2011-09-27 22:10:25

這個例程使用多少堆棧空間？

回答

相關問題