首頁猿問通過遞歸查找最大值的Python代碼

通過遞歸查找最大值的Python代碼

Python

慕工程0101907 2023-06-20 16:50:23

我對我的 Python 代碼有疑問，該代碼用于查找列表中的最大值。功能代碼如下：def large(x): if len(x) == 1: return x.pop(0) else: temp = x.pop(0) previous = large(x) if previous >= temp: return previous else: return temp但在那之前，我嘗試過：def large(x): if len(x) == 1: return x.pop(0) else: temp = x.pop(0) if large(x) >= temp: return large(x) else: return temp它將返回錯誤消息：<ipython-input-74-dd8676a7c4e6> in large(x) 3 return x.pop(0) 4 else:----> 5 temp = x.pop(0) 6 if large(x) >= temp: 7 return large(x)IndexError: pop from empty list玩具數據將是：inputlist = [6,1,3,2,3,4,5,6]large(inputlist)提前謝謝你的幫助。我找不到導致此錯誤的主要原因。至于我，這兩個代碼是完全相同的。

查看完整描述

4 回答

泛舟湖上清波郎朗

TA貢獻1818條經驗獲得超3個贊

的問題

if large(x) >= temp:

return large(x)

是你最終不止一次調用large(x)（因此pop），這是從列表中刪除元素。

就個人而言，我更喜歡這種風格，而不是使用像pop.

def large(x):

if len(x) == 1:

return x[0]

remainder = large(x[1:])

return x[0] if x[0] > remainder else remainder

反對回復 2023-06-20

慕桂英546537

TA貢獻1848條經驗獲得超10個贊

與 OneCricketeer 的解決方案相同，但無需在每次遞歸調用時都不必要地創建列表切片。它還處理一個空列表。

def large(x):

def rec(y):

try:

v = next(y)

except StopIteration:

return None

r = rec(y)

if r is None:

return v

return v if v > r else r

return rec(iter(x))

inputlist = [6,1,3,2,3,4,5,6]

print(large(inputlist))

print(large([]))

產生

None

反對回復 2023-06-20

有只小跳蛙

TA貢獻1824條經驗獲得超8個贊

因為這是一個遞歸練習，而不是我們在系統代碼中做的事情，所以我會使用描述性代碼而不是高效代碼，并做類似的事情：

def largest(array):

if array:

head, *tail = array

if tail and head < (result := largest(tail)):

return result

return head

return None

if __name__ == "__main__":

from random import choices

array = choices(range(100), k=10)

print(array, '->', largest(array))

輸出

> python3 test.py

[46, 67, 0, 22, 23, 20, 30, 7, 87, 50] -> 87

> python3 test.py

[83, 77, 61, 53, 7, 65, 68, 43, 44, 47] -> 83

> python3 test.py

[36, 99, 47, 93, 60, 43, 56, 90, 53, 44] -> 99

如果您真的需要提高效率，我建議您安全地這樣做。具體來說，不公開帶有調用者不應該使用的特殊參數的 API ，例如：

def my_max(lst, m=None, i=0):

因為他們可以為這些額外的參數提供值，這些參數會使您的代碼失敗，并最終將其歸咎于您。同上公開調用者可能調用的內部函數而不是預期的函數：

def my_max(lst, m=None, i=0):

def my_max_helper(lst, i):

不小心調用了my_max_helper()命名不當的參數的虛假值i。相反，我會考慮嵌套您的函數以避免此類調用錯誤：

def largest(array):

def largest_recursive(array, index):

a = array[index]

if len(array) - index != 1:

if (b := largest_recursive(array, index + 1)) > a:

return b

return a

if array:

return largest_recursive(array, 0)

return None

反對回復 2023-06-20

慕森王

TA貢獻1777條經驗獲得超3個贊

這并沒有回答為什么原文不正確。相反，它制定了一個“標準模式”，可用于實現許多遞歸問題。

我想知道我應該如何用索引而不是彈出來消除每一輪中的元素數量？

不要“消除”元素 :-)

許多遞歸友好的問題通過縮小每一步的范圍來運行。這包括尋找最大值（或任何可以表示為折疊的操作）、二分搜索、自上而下的歸并排序等。其中許多問題本身都是使用數組和子問題減少的偽代碼表示的通過調整每個遞歸調用的范圍。在最大/二進制搜索的情況下，這也避免了對原始對象的任何突變。

因此，遞歸 max 函數可以寫成如下形式。請注意，這種傳遞工作狀態的形式是 Tail-Call Friendly。雖然我發現這種形式更容易表達某些問題，但它在 Python 中并不重要，因為[C]Python 不支持尾調用優化^{^}。

def my_max(lst, m=None, i=0):

? # base-case: return result of work

? if len(lst) == i:

? ? return m

? # Compute max through here

? c = lst[i]

? m = c if m is None or c > m else m

? # Call recursive function increasing the index by 1.

? # This is how the problem advances.

? return my_max(lst, m, i + 1)

上面的示例還使用默認參數而不是輔助方法。這是一個使用遞歸結果的替代方法——這通常是遞歸函數的引入方式——以及一個離散的輔助方法。

def my_max(lst):

? # Wrapper can ensure helper pre-conditions.

? # In this case that is a non-Empty list per the base case check.

? if not lst:

? ? return None

? return my_max_helper(lst, 0)

def my_max_helper(lst, i):

? # base case: last item in list returns itself

? if len(lst) - 1 == i:

? ? return lst[i]

? c = lst[i]

? m = my_max_helper(lst, i + 1)

? return c if c > m else m

在這兩種情況下，都使用臨時變量來避免重復表達式；雖然有時只是一種風格選擇，但由于避免了額外彈出突變的意外副作用，這種一致性會減輕原始問題。

應list使用支持 O(1) 索引查找的a 或其他序列調用上述方法。特別是，“索引”方法不適合，也不會與生成器對象一起使用。還有其他的答案涵蓋了這一點——只是要注意避免潛在的列表切片，比如h,*t=lor l[1:]，這可能會導致性能不佳。

^ Python 中有一些模塊可以通過 spring-boarding模擬TCO。

反對回復 2023-06-20

4 回答
0 關注
219 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

通過遞歸查找最大值的Python代碼

通過遞歸查找最大值的Python代碼

4 回答

添加回答