遞歸的基本概念:程序調(diào)用自身的編程技巧稱為遞歸,是函數(shù)自己調(diào)用自己.
一個函數(shù)在其定義中直接或間接調(diào)用自身的一種方法,它通常把一個大型的復雜的問題轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來解決,可以極大的減少代碼量.遞歸的能力在于用有限的語句來定義對象的無限集合.
使用遞歸要注意的有兩點:
1)遞歸就是在過程或函數(shù)里面調(diào)用自身;
2)在使用遞歸時,必須有一個明確的遞歸結(jié)束條件,稱為遞歸出口.
遞歸分為兩個階段:
1)遞推:把復雜的問題的求解推到比原問題簡單一些的問題的求解;
2)回歸:當獲得最簡單的情況后,逐步返回,依次得到復雜的解.
利用遞歸可以解決很多問題:如背包問題,漢諾塔問題,...等.
斐波那契數(shù)列為:0,1,1,2,3,5...
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2);
上面就是一個簡單的遞歸調(diào)用了.由于遞歸引起一系列的函數(shù)調(diào)用,并且有可能會有一系列的重復計算,遞歸算法的執(zhí)行效率相對較低.
迭代:利用變量的原值推算出變量的一個新值.如果遞歸是自己調(diào)用自己的話,迭代就是A不停的調(diào)用B.
遞歸中一定有迭代,但是迭代中不一定有遞歸,大部分可以相互轉(zhuǎn)換.能用迭代的不用遞歸,遞歸調(diào)用函數(shù),浪費空間,并且遞歸太深容易造成堆棧的溢出.
