遞迴的思想主要是能夠重複某些動作,比如簡單的階乘,次方,回溯中的八皇后,數獨,還有漢諾塔,分形。
由於堆疊的機制,一般的遞迴可以保留某些變數在歷史狀態中,比如你提到的return x * power..., 但是某些或許龐大的問題或者是深度過大的問題就需要儘量避免遞迴,因為可能會棧溢位。還有一個
問題是~python不支援尾遞迴最佳化!!!!所以~還是儘量避免遞迴的出現。
def power(x, n)
if n < 0:
return 1
return x * power(x, n - 1)
power(3, 3)
3 * power(3, 2)
3 * (3 * power(3, 1))
3 * (3 * (3 * power(3, 0)))
3 * (3 * (3 * 1)) 這裡n = 0, return 1
3 * (3 * 3)
3 * 9
27
當函式形參n=0的時候,開始回退~直到第一次呼叫power結束。
遞迴的思想主要是能夠重複某些動作,比如簡單的階乘,次方,回溯中的八皇后,數獨,還有漢諾塔,分形。
由於堆疊的機制,一般的遞迴可以保留某些變數在歷史狀態中,比如你提到的return x * power..., 但是某些或許龐大的問題或者是深度過大的問題就需要儘量避免遞迴,因為可能會棧溢位。還有一個
問題是~python不支援尾遞迴最佳化!!!!所以~還是儘量避免遞迴的出現。
def power(x, n)
if n < 0:
return 1
return x * power(x, n - 1)
power(3, 3)
3 * power(3, 2)
3 * (3 * power(3, 1))
3 * (3 * (3 * power(3, 0)))
3 * (3 * (3 * 1)) 這裡n = 0, return 1
3 * (3 * 3)
3 * 9
27
當函式形參n=0的時候,開始回退~直到第一次呼叫power結束。