許多大小為N的問題的遞回解決方案都遵循這樣的模式：
步驟1：解決最小輸入的問題（例如n=1）
步驟2：解決最小輸入的問題。
第1步：解決最小輸入的問題（比如，n = 1）
第 2 步：給定大小為 n = k-1（k <= N）的同一問題的解決方案，對 n = k 進行解決。我們可以看到其中的歸納性質，這就是為什么我們通常使用歸納法來證明遞回演算法。對于一些問題，如遞回斐波那契，這種模式以明顯的方式出現。我的問題是，比如說，二叉樹遍歷是否也可以被看作是遵循這種模式？
以深度優先搜索為例：
def DFS(root):
if root == None:
回傳
print(root.value)
DFS(root.left)
DFS(root.right)
我理解代碼和呼叫堆疊，但我很難確切地闡明DFS的步驟1和2是什么（與上面概述的遞回解決方案的結構保持一致）。這不可能是唯一的基本情況是當當前節點是None時，因為遍歷一個節點也應該是一個基本情況。
如果我說第4行，也就是包含print陳述句的那一行是一個基本情況，那就沒有什么意義了，因為它對每個子樹都要運行。
uj5u.com熱心網友回復：
它遵循同樣的模式。
要解決的 "問題 "是以正確的順序列印樹。你的代碼實作了預排序。
你的代碼實作了預排序。
第1步：解決最小輸入的問題（例如，n = 1）
第2步：解決最小輸入的問題。
這里最小的問題是列印一個空樹（root is None）。在這種情況下，解決方案是不列印任何東西（只列印return）。
第2步：給定大小為n=k-1（k<=N）的同一問題的解決方案，解決它的n=k。
我們可以認為k代表了當前樹中的節點數，而n是這個樹的直接子樹中的節點數。列印左或右子樹是一個較小的問題，其中n <= k-1（注意<=）。
列印樹（按順序），包括列印根節點，然后解決左、右子樹的 "問題"。
一個區別是，樹的輸出是這個函式的 "副作用" -- 它不回傳結果，而是輸出它。這意味著進行遞回呼叫的人不需要拿回一個結果來作業。一個更純粹的函式將回傳樹的字串表示，而呼叫者將使用該字串與它正在構建的字串進行連接，并將其回傳給自己的呼叫者。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/319331.html
標籤：
上一篇：事件在遞回中執行了幾次函式