1.遞歸
如這個(gè)階乘函數(shù)：n!=n*(n-1)*(n-2)*...*1
計(jì)算階乘的方法有很多绘盟。 一種方法是n!=n*(n-1)!。 因此該程序可以直接寫成：
int factorial (int n) {
if (n == 1) {
return 1;
} else {
return n*factorial(n-1);
}
}
為了運(yùn)行該程序诗宣，計(jì)算機(jī)需要建立一個(gè)乘法鏈：factorial（n）→factorial（n-1）→factorial（n-2）→...→factorial（1）膘怕。 因此，計(jì)算機(jī)必須跟蹤稍后要執(zhí)行的乘法召庞。 這種以操作鏈為特征的程序稱為遞歸岛心。 遞歸可以進(jìn)一步分為線性和樹狀遞歸来破。 當(dāng)跟蹤操作鏈所需的信息量隨著輸入線性增長(zhǎng)時(shí)，遞歸被稱為線性遞歸忘古。 n! 的計(jì)算就是這樣一種情況徘禁，因?yàn)樗钑r(shí)間與n成線性增長(zhǎng)。 當(dāng)信息量隨著輸入呈指數(shù)增長(zhǎng)時(shí)髓堪，會(huì)發(fā)生另一種遞歸送朱，即樹遞歸。
2. 迭代
計(jì)算階乘函數(shù)的不同觀點(diǎn)是先乘以1干旁，然后乘以3驶沼，然后乘以4，直到n争群。 更正式地說回怜，程序可以使用從1到n的計(jì)數(shù)器并同時(shí)計(jì)算product，直到計(jì)數(shù)器超過n换薄。 因此該程序可以寫為：
int factorial (int n) {
int product = 1;
for(int i=2; i<n; i++) {
product *= i;
}
return product;
}
與程序1相比玉雾，這個(gè)程序不構(gòu)建一個(gè)乘法鏈。 在每一步中轻要，計(jì)算機(jī)只需要跟蹤product和 i 的當(dāng)前值复旬。 這種類型的程序被稱作迭代，其狀態(tài)可以通過固定數(shù)量的變量伦腐，描述變量應(yīng)該如何更新一個(gè)固定的規(guī)則赢底，并結(jié)束測(cè)試指定在其過程中應(yīng)終止條件來概括。 與遞歸相同柏蘑，當(dāng)所需時(shí)間與輸入線性增長(zhǎng)時(shí)幸冻，我們稱迭代線性遞歸。
3. 遞歸 vs 迭代
比較這兩個(gè)過程咳焚，我們可以發(fā)現(xiàn)它們看起來幾乎相同洽损，特別是在數(shù)學(xué)函數(shù)方面。 它們都需要一些與n成比例的步驟來計(jì)算n !. 另一方面革半，當(dāng)我們考慮這兩個(gè)程序的運(yùn)行過程時(shí)碑定，它們的演變將大不相同。
在迭代的情況下又官，程序變量提供了狀態(tài)的完整描述延刘。 如果我們?cè)谥虚g停止計(jì)算，恢復(fù)它只需要向計(jì)算機(jī)提供所有變量六敬。 但是碘赖，在遞歸過程中，信息由計(jì)算機(jī)維護(hù)，因此對(duì)程序“隱藏”普泡。 這使得在停止程序后幾乎不可能恢復(fù)程序播掷。
4. 樹遞歸
如上所述，當(dāng)信息量隨輸入呈指數(shù)增長(zhǎng)時(shí)撼班，會(huì)發(fā)生樹遞歸歧匈。 例如，考慮斐波那契數(shù)列的定義如下：
根據(jù)定義砰嘁，F(xiàn)ibonacci數(shù)字具有以下順序件炉，其中每個(gè)數(shù)字是前兩個(gè)數(shù)字的總和：0,1,1,2,3,5,8,13,21，...
遞歸程序可以立即寫成：
int fib (int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
因此般码，要計(jì)算fib（5）妻率，程序?qū)⒂?jì)算fib（4）和fib（3）乱顾。 對(duì)于計(jì)算機(jī)fib（4）板祝，它計(jì)算fib（3）和fib（2）。 注意fib程序在最后一行調(diào)用了兩次走净。
另一方面券时，我們也可以用迭代的方式編寫程序來計(jì)算斐波那契數(shù)。 下面程序是一個(gè)線性迭代伏伯。 上面的程序和迭代方法寫的程序所需的時(shí)間差異很大橘洞，即使對(duì)于較小的輸入。
int fib (int n) {
int fib = 0;
int a = 1;
for(int i=0; i<n; i++) {
fib = fib + a;
a = fib;
}
return fib;
}
但是说搅，人們不應(yīng)該認(rèn)為樹遞歸程序是無用的炸枣。 當(dāng)我們考慮在分層數(shù)據(jù)結(jié)構(gòu)而不是數(shù)字上運(yùn)行的程序時(shí)，樹遞歸是一個(gè)自然且強(qiáng)大的工具弄唧。 它可以幫助我們理解和設(shè)計(jì)程序适肠。
