有過程式學習經驗的人對於遞歸函數一定不陌生,我們經常使用遞歸的方式來解決一系列複雜的問題,遞歸演算法對於大多數問題都是很有效的,而且它也可以優化我們的程式碼,我們使用遞歸的時候有幾點要注意:
1)遞歸是在函數本身呼叫函數本身。
2)遞歸的效率比較低,如果有時間限制不建議使用。
3)遞歸過程中需要有一個明確的結束條件,即遞歸出口。
下面我們就來詳細的講解一下遞迴函數。
我們先透過例子來看一下遞歸的簡單使用:
m=int(input('輸入數字:'))deftest(x):x+=2ifx<100:test(x)else:print('最後的x為:',x)test(m)
輸出結果為:
輸入一個數字:20最後的x為:100
讓我們來分析這個例子,首先第一行程式碼我們輸入了一個整數,最後一行把m當作實際參數傳遞到test()方法,在test()方法中,會先把x加2處理,然後再進行一個判斷,如果x的值小於100,那麼就再次調用這個函數,調用的時候當前x的值作為實際參數參加調用,直到滿足x>=100的時候結束遞歸。
看下面示意圖:
即如果不滿足條件就回到了最外層來呼叫了這個函數。
談起遞歸演算法中經典的問題,總是離不開斐波那契數列和漢諾塔,我們在這裡來講解一下如果使用遞歸去解斐波那契數列。
首先我們要知道斐波那契數列的遞推公式為F(n)=F(n-1)+F(n-2),F(1)、和F(2)為1,我們可以透過遞歸來解斐波那契數列中的某一項的值為多少。
求解斐波那契數列問題的時候我們可以採用多種方式。
首先我們使用常用的遞歸方式來解決這個問題:
N=int(input(輸入需要得到的項數:))deffibonacci(n):ifn<=2:#如果小於等於2就把n置1return1else:returnfibonacci(n-1)+fibonacci(n-2)print ('對應值為',fibonacci(n))
輸出結果為:
輸入需要得到的項數:4對應值為3
對於這種遞歸的呼叫方式,當我們輸入的值4的時候,會在遞歸中執行下面的操作:
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2)
然後我們可以看出第四項的值為1+1+1=3。
其實這種方式的解算是比較浪費時間的,因為需要進行迭代的次數太多,我們還可以用空間替代時間的方式來解這個問題。
程式碼如下:
n=int(input(輸入需要得到的項數:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print('對應值為',fibonacci[n-1])
輸出結果為:
輸入需要得到的項數:4對應值為3
這種方式我們先給列表規定了前2項的值,然後對於我們要求解的項數n,我們直接透過公式把這個斐波那契數列的列表填入我們需要的那一項,最後根據索引值直接找到對應項輸出結果。
關於遞歸函數就講到這裡,上面所講到需要注意的幾點大家要特別注意遞歸出口和時間限制,出口是遞歸結束的關鍵,在很多時候,我們使用遞歸的方法會導致程序超出規定的時間,這時候我們就需要更換思路來求解問題,上面講的第二種方式可以幫助大家解決問題。