我一直在閱讀排序算法。我遇到了合并排序的這段代碼：def mergeSort(arr):? ? if len(arr) > 1:? ? ? ? mid = len(arr)//2? ? ? ? L = arr[:mid]? ? ? ? R = arr[mid:]? ? ? ? #function calls itself here<<<<<<<<<<<<<<<<<<<<<<<<<? ? ? ? mergeSort(L)# Sorting the first half? ? ? ? mergeSort(R)# Sorting the second half? ? ? ? i = j = k = 0? ??? ? ? ? # Copy data to temp arrays L[] and R[]?? ? ? ? while i < len(L) and j < len(R):? ? ? ? ? ? if L[i] < R[j]:? ? ? ? ? ? ? ? arr[k] = L[i]?? ? ? ? ? ? ? ? i+= 1? ? ? ? ? ? else:?? ? ? ? ? ? ? ? arr[k] = R[j]?? ? ? ? ? ? ? ? j+= 1? ? ? ? ? ? ? ? k+= 1? ??? ? ? ? # Checking if any element was left?? ? ? ? while i < len(L):?? ? ? ? ? ? arr[k] = L[i]?? ? ? ? ? ? i+= 1? ? ? ? ? ? k+= 1? ??? ? ? ? while j < len(R):?? ? ? ? ? ? arr[k] = R[j]?? ? ? ? ? ? j+= 1? ? ? ? ? ? k+= 1# Code to print the list?def printList(arr):? ? for i in range(len(arr)):? ? ? ? print(arr[i], end =" ")? ? print()?# driver code to test the above code?if __name__ == '__main__':?? ? #arr = [12, 11, 13, 5, 6, 7]? ? arr = [38, 27, 43, 3, 9, 82, 10]? ? print ("Given array is", end ="\n")?? ? printList(arr)?? ? mergeSort(arr)?? ? print("Sorted array is: ", end ="\n")?? ? printList(arr)?# This code is contributed by Mayank Khanna?函數 mergeSort() 是從自身內部調用的，這是一個好的做法嗎？我的印象是它可能會導致錯誤。
2 回答
汪汪一只貓
TA貢獻1898條經驗 獲得超8個贊
TL;DR 通常沒問題，但對于某些輸入可能非常危險。
給定的mergeSort函數調用自身 - 這種現象稱為遞歸。
什么是遞歸
解決問題的常見方法，其中解決方案取決于同一問題的較小實例的解決方案；比如遍歷二叉樹。
每次遞歸調用都會將函數參數壓入調用堆棧，并且每次調用都有自己的局部變量。
遞歸可能會導致漏洞，例如DNS 開放遞歸。
如果通過不定義停止條件或處理導致大量遞歸調用的輸入而誤用，則會發生堆棧溢出（這意味著調用堆棧已被使用到最大）。
任何遞歸解決方案都可以轉換為迭代解決方案（使用循環的解決方案）
總結
當函數調用時間合理時，遞歸是安全的。
Python默認的遞歸限制是
1000，所以函數調用自身不能超過1000次數。
您可以使用以下方法驗證它getrecursionlimit：
import?sys print(sys.getrecursionlimit())
并將其更改為setrecursionlimit：
new_recursion_limit?=?1500 sys.setrecursionlimit(new_recursion_limit)
遞歸可能并且將會導致漏洞，并且最好在處理用戶輸入時避免 - 有利于迭代解決方案。
聚苯乙烯
現在您也知道我們的網站是以什么命名的了吧！
喵喵時光機
TA貢獻1846條經驗 獲得超7個贊
在函數內部調用函數沒有問題，但您必須格外小心進入無限循環。這樣做的一般良好做法是僅在函數末尾調用函數（這樣可以減少混淆變量值的機會）并使用某種if語句或某種意義上的語句來提供出路。
添加回答
舉報
0/150
提交
取消