首先先提出一個(gè)問(wèn)題,如何用遞歸去求解5的階乘,這是一個(gè)經(jīng)典的遞歸問(wèn)題.我們都知道5的階乘求法是5×4×3×2×1.但是用編程的方式應(yīng)該怎么寫(xiě)呢?
遞歸需要滿足的三個(gè)條件
1,一個(gè)問(wèn)題可以分解為幾個(gè)子問(wèn)題的解
例如求階乘問(wèn)題,每一步都可以分為n * f(n - 1).
2,子問(wèn)題除了數(shù)據(jù)規(guī)模不同之外,求解思路完全一樣
3,存在遞歸終止條件
遞歸是把問(wèn)題一層層的分解,不能無(wú)限循環(huán)下去,這就需要一個(gè)終止條件,比如階乘問(wèn)題的終止條件就是n = 1;因?yàn)?的階乘就是1.
求一個(gè)數(shù)階乘的遞歸公式
- (NSInteger)factorial:(NSInteger)num
{
if (num == 1) {
return 1;
} else {
NSInteger tmp = num * [self factorial:num - 1];
return tmp;
}
}
由此我們可以看出遞歸的基本寫(xiě)法就是將問(wèn)題分解為無(wú)數(shù)個(gè)相同的小問(wèn)題,然后找到終止條件.
思維誤區(qū)
就是用自己的腦袋去模擬算法的遞歸過(guò)程,繞來(lái)繞去就把自己繞暈了,人腦并不擅長(zhǎng)做重復(fù)的事情,將這些交給計(jì)算機(jī)吧.我們只需要將問(wèn)題分解找到規(guī)律即可.
練習(xí)
例:
假如這里有 n 個(gè)臺(tái)階押框，每次你可以跨 1 個(gè)臺(tái)階或者 2 個(gè)臺(tái)階垒拢，請(qǐng)問(wèn)走這 n 個(gè)臺(tái)階有多少種走法厌蔽？如果有 7 個(gè)臺(tái)階，你可以 2，2流妻，2痘拆，1 這樣子上去卷拘，也可以 1喊废，2，1栗弟，1污筷，2 這樣子上去，總之走法有很多乍赫，那如何用編程求得總共有多少種走法呢瓣蛀？
我們仔細(xì)想下，實(shí)際上耿焊，可以根據(jù)第一步的走法把所有走法分為兩類揪惦，第一類是第一步走了 1 個(gè)臺(tái)階，另一類是第一步走了 2 個(gè)臺(tái)階罗侯。所以 n 個(gè)臺(tái)階的走法就等于先走 1 階后器腋，n-1 個(gè)臺(tái)階的走法 加上先走 2 階后，n-2 個(gè)臺(tái)階的走法钩杰。用公式表示就是：
f(n) = f(n-1) + f(n-2)
好了規(guī)律找到了,現(xiàn)在我們來(lái)找終止條件.當(dāng)只有一個(gè)臺(tái)階的時(shí)候只有一種走法,所以f(1)= 1.但是當(dāng)有2個(gè)臺(tái)階的時(shí)候,我們一步走兩個(gè)臺(tái)階,這個(gè)時(shí)候臺(tái)階被走完了,可以沒(méi)有觸發(fā)f(1) = 1的終止條件,所以我們應(yīng)該再加一個(gè)終止條件f(2) = 2,就是當(dāng)有2個(gè)臺(tái)階的時(shí)候有兩種走法一步一個(gè)臺(tái)階或者一步兩個(gè)臺(tái)階.
那么終止條件就是f(1) = 1 和 f(2) = 2,現(xiàn)在規(guī)律和終止條件都有了,可以開(kāi)始寫(xiě)代碼了:
- (NSInteger)tj:(NSInteger)num
{
if (num == 1) {
return 1;
}
if (num == 2) {
return 2;
}
NSInteger tmp = [self tj:(num - 1)] + [self tj:(num - 2)];
return tmp;
}
遞歸代碼雖然簡(jiǎn)潔高效纫塌，但是，遞歸代碼也有很多弊端讲弄。比如措左，堆棧溢出、重復(fù)計(jì)算避除、函數(shù)調(diào)用耗時(shí)多怎披、空間復(fù)雜度高等.
練習(xí):遞歸
ps:內(nèi)容整理自極客時(shí)間--數(shù)據(jù)結(jié)構(gòu)與算法之美
