最近，我一直在處理 Python 中的一些遞回問題，我必須使用遞回生成可能配置的串列（即給定字串的排列串列、子字串串列等）。我很難找到最佳實踐，也很難理解如何在遞回中管理這種變數。
我將給出生成二叉樹問題的示例。我或多或少知道我必須在遞回中實作什么：
- 如果 n=1，則只回傳一個節點。
- 如果 n=3，則回傳唯一可能的二叉樹。
- 對于 n>3，創建一個節點，然后探索可能性：左節點無子節點，右節點無子節點，任一節點都無子節點。遞回地探索這些可能性。
現在，我最難以想象的是我將如何到達樹木串列。目前我所做的做法是在函式呼叫中傳遞一個串列（作為引數），該函式將回傳此串列，但問題是在呼叫遞回函式以探索節點的可能性時的情況 3回傳一個串列而不是將節點附加到我正在構建的樹中。當我在腦海中想象遞回樹時，我想象了一個“樹”變數，它對每個樹葉都是唯一的，并且這些樹被添加到由“根”（即第一個）呼叫回傳的串列中。但我不知道這是否可能。
在這些情況下，如何在遞回中處理生成組合和回傳配置串列？雖然我舉了一個例子，但答案越籠統越好。我還想知道在這方面是否有“最佳實踐”。
uj5u.com熱心網友回復：
目前我做的做法是在函式呼叫中傳遞一個串列（作為引數），函式將回傳這個串列
這不是解決遞回問題的最純粹的方法。如果您可以使遞回函式解決子問題而無需必須使用的額外引數變數，那就更好了。所以遞回函式應該只回傳一個結果，就好像它是唯一一次呼叫過（由測驗框架）。所以在這個例子中，遞回呼叫應該回傳一個包含樹的串列。
或者，遞回函式可以是一個不回傳串列但產生單個值的子函式（在這種情況下：樹）。然后呼叫者可以決定是否將其打包到串列中。這更像pythonic。
對于示例問題，確定一些不變數也很重要。例如，很明顯當n是偶數時沒有解。至于遞回方面：一旦你決定創建一個根，那么它的左右子樹都將有奇數個節點。當然，這是針對此問題的特定觀察，但尋找此類問題的屬性很重要。
最后，查看相同的子問題是否可以多次重復出現也同樣重要。在示例問題中肯定就是這種情況：例如，左子樹有時可能與右子樹具有相同數量的節點。在這種情況下，記憶將提高效率（動態規劃）。
當遞回函式回傳一個串列時，呼叫者可以迭代該串列以檢索其元素（示例中的樹），并使用它們來構建滿足呼叫者任務的擴展結果。在示例情況下，這意味著從遞回檢索串列中取出的樹作為子項附加到新根。然后這棵新樹被附加到一個新串列（與從遞回呼叫回傳的串列無關）。在許多情況下，這個新串列會更長，盡管這取決于問題的型別。
為了進一步說明解決這些問題的方法，這里是示例問題的解決方案：使用 main 函式進行遞回呼叫，并使用記憶化：
class Solution:
memo = { 1: [TreeNode()] }
def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
# If we didn't solve this problem before...
if n not in self.memo:
# Create a list for storing the results (the trees)
results = []
# Before creating any root node,
# decide the size of the left subtree.
# It must be odd
for num_left in range(1, n, 2):
# Make the recursive call to get all shapes of the
# left subtree
left_shapes = self.allPossibleFBT(num_left)
# The remainder of the nodes must be in the right subtree
num_right = n - 1 - num_left # The root also counts as 1
right_shapes = self.allPossibleFBT(num_right)
# Now iterate the results we got from recursion and
# combine them in all possible ways to create new trees
for left in left_shapes:
for right in right_shapes:
# We have a combination. Now create a new tree from it
# by putting a root node on top of the two subtrees:
tree = TreeNode(0, left, right)
# Append this possible shape to our results
results.append(tree)
# All done. Save this for later re-use
self.memo[n] = results
return self.memo[n]
使用串列推導可以使此代碼更加緊湊，但它可能會使代碼的可讀性降低。
uj5u.com熱心網友回復：
不要將資訊傳遞到遞回呼叫中，除非他們需要該資訊來計算其本地結果。當您在沒有副作用的情況下撰寫時，更容易推理遞回。因此，不要讓遞回呼叫將其自己的結果放入串列中，而是撰寫代碼以便使用遞回呼叫的結果來創建回傳值。
讓我們舉一個簡單的例子，將一個簡單的回圈轉換為遞回，并用它來累加一個遞增的整數序列。
def recursive_range(n):
if n == 0:
return []
return recursive_range(n - 1) [n]
我們以自然的方式使用函式：我們將資訊與引數一起放入，并使用回傳值（而不是引數的變異）獲取資訊。
在你的情況下：
現在，我最難以想象的是我將如何到達樹木串列。
所以你知道你想在程序結束時回傳一個樹串列。因此，繼續進行的自然方式是您希望每個遞回呼叫也這樣做。
在這些情況下，如何在遞回中處理生成組合和回傳配置串列？雖然我舉了一個例子，但答案越籠統越好。
遞回呼叫回傳子問題的結果串列。您可以使用這些結果為當前問題創建結果串列。
您無需考慮如何實作遞回即可撰寫遞回演算法。您無需考慮呼叫堆疊。你確實需要考慮兩件事：
- 什么是基本情況？
- 問題如何遞回分解？（或者：為什么遞回適合這個問題？）
問題是，遞回并不特殊。進行遞回呼叫就像呼叫任何其他函式一樣，它恰好可以為您提供子問題的正確答案。因此，您需要做的就是了解解決子問題如何幫助您解決當前問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/403058.html
標籤：