1、遞歸與迭代: 遞歸和迭代都是迴圈的一種。簡單地說,遞歸是重覆調用函數自身實現迴圈。迭代是函數內某段代碼實現迴圈,而迭代與普通迴圈的區別是:迴圈代碼中參與運算的變數同時是保存結果的變數,當前保存的結果作為下一次迴圈計算的初始值。 遞歸迴圈中,遇到滿足終止條件的情況時逐層返回來結束。迭代則使用計數器 ...
1、遞歸與迭代:
遞歸和迭代都是迴圈的一種。簡單地說,遞歸是重覆調用函數自身實現迴圈。迭代是函數內某段代碼實現迴圈,而迭代與普通迴圈的區別是:迴圈代碼中參與運算的變數同時是保存結果的變數,當前保存的結果作為下一次迴圈計算的初始值。
遞歸迴圈中,遇到滿足終止條件的情況時逐層返回來結束。迭代則使用計數器結束迴圈。當然很多情況都是多種迴圈混合採用,這要根據具體需求。
具體來講:
遞歸的基本概念:程式調用自身的編程技巧稱為遞歸,是函數自己調用自己. 一個函數在其定義中直接或間接調用自身的一種方法,它通常把一個大型的複雜的問題轉化為一個與原問題相似的規模較小的問題來解決,可以極大的減少代碼量.遞歸的能力在於用有限的語句來定義對象的無限集合.
使用遞歸要註意的有兩點:
1)遞歸就是在過程或函數裡面調用自身;
2)在使用遞歸時,必須有一個明確的遞歸結束條件,稱為遞歸出口.
遞歸分為兩個階段:
1)遞推:把複雜的問題的求解推到比原問題簡單一些的問題的求解;
2)回歸:當獲得最簡單的情況後,逐步返回,依次得到複雜的解.
利用遞歸可以解決很多問題:如背包問題,漢諾塔問題,斐波那契數列為:1,1,2,3,5...
迭代:利用變數的原值推算出變數的一個新值.如果遞歸是自己調用自己的話,迭代就是A不停的調用B.
遞歸中一定有迭代,但是迭代中不一定有遞歸,大部分可以相互轉換.能用迭代的不用遞歸,遞歸調用函數,浪費空間,並且遞歸太深容易造成堆棧的溢出.
例如對於裴波那契數列的實現:
1)迭代:
2)遞歸:
2、遞歸的應用舉例:
1)使用遞歸編寫一個十進位轉換為二進位的函數(要求採用“取2取餘”的方式,結果與調用bin()一樣返回字元串形式)。
代碼:
def b(n):
if n//2==0:
n=str(n)
return n
else:
x=n%2
n=n//2
s=str(x)
return b(n)+s
print(b(6))
2)寫一個函數x(n),將參數n分解出每個位的數字並按順序存放到列表中。舉例:x(12345) ==> [1, 2, 3, 4, 5]
代碼:
def x(n):
if n<10:
list1=[]
list1.append(n)
return list1
else:
s=n%10
n=n//10
list1=list(x(n))
list1.append(s)
return list1
print(x(12345))
3)求1到n的階乘
def jie(n):
if n<1:
print("輸入有誤")
elif n==1:
return 1
else:
return jie(n-1)*n
n=input("請輸入n:")
x=int(n)
result=jie(x)
print("n的階乘大小為:",result)