我一直在閱讀排序算法。我遇到了合并排序的這段代碼：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?函數(shù) mergeSort() 是從自身內(nèi)部調(diào)用的，這是一個(gè)好的做法嗎？我的印象是它可能會(huì)導(dǎo)致錯(cuò)誤。
2 回答
汪汪一只貓
TA貢獻(xiàn)1898條經(jīng)驗(yàn) 獲得超8個(gè)贊
TL;DR 通常沒問題，但對(duì)于某些輸入可能非常危險(xiǎn)。
給定的mergeSort函數(shù)調(diào)用自身 - 這種現(xiàn)象稱為遞歸。
什么是遞歸
解決問題的常見方法，其中解決方案取決于同一問題的較小實(shí)例的解決方案；比如遍歷二叉樹。
每次遞歸調(diào)用都會(huì)將函數(shù)參數(shù)壓入調(diào)用堆棧，并且每次調(diào)用都有自己的局部變量。
遞歸可能會(huì)導(dǎo)致漏洞，例如DNS 開放遞歸。
如果通過不定義停止條件或處理導(dǎo)致大量遞歸調(diào)用的輸入而誤用，則會(huì)發(fā)生堆棧溢出（這意味著調(diào)用堆棧已被使用到最大）。
任何遞歸解決方案都可以轉(zhuǎn)換為迭代解決方案（使用循環(huán)的解決方案）
總結(jié)
當(dāng)函數(shù)調(diào)用時(shí)間合理時(shí)，遞歸是安全的。
Python默認(rèn)的遞歸限制是
1000，所以函數(shù)調(diào)用自身不能超過1000次數(shù)。
您可以使用以下方法驗(yàn)證它getrecursionlimit：
import?sys print(sys.getrecursionlimit())
并將其更改為setrecursionlimit：
new_recursion_limit?=?1500 sys.setrecursionlimit(new_recursion_limit)
遞歸可能并且將會(huì)導(dǎo)致漏洞，并且最好在處理用戶輸入時(shí)避免 - 有利于迭代解決方案。
聚苯乙烯
現(xiàn)在您也知道我們的網(wǎng)站是以什么命名的了吧！
喵喵時(shí)光機(jī)
TA貢獻(xiàn)1846條經(jīng)驗(yàn) 獲得超7個(gè)贊
在函數(shù)內(nèi)部調(diào)用函數(shù)沒有問題，但您必須格外小心進(jìn)入無限循環(huán)。這樣做的一般良好做法是僅在函數(shù)末尾調(diào)用函數(shù)（這樣可以減少混淆變量值的機(jī)會(huì)）并使用某種if語句或某種意義上的語句來提供出路。
添加回答
舉報(bào)
0/150
提交
取消