昨天在群里看到有群友在討論迭代與遞歸的區(qū)別，仔細檢索了下大腦，好像真的記不清了台妆，有些慚愧...。有空搜索下了胖翰，終于知道了它們的區(qū)別频丘。以下概念內容參考于銘毅天下的博文
遞歸的基本概念：程序調用自身的編程技巧稱為遞歸，是函數(shù)自己調用自己泡态。
一個函數(shù)在其定義中直接或間接調用自身的一種方法。它通常把一個大型的復雜的問題轉化為一個與原問題相似的規(guī)模較小的問題來解決迂卢，可以極大的減少代碼量某弦。遞歸的能力在于用有限的語句來定義對象的無限集合桐汤。
使用遞歸時需要注意的兩點：
1.遞歸就是在過程或函數(shù)里面調用自身;
2.在使用遞歸時，必須有一個明確的遞歸結束條件靶壮，稱為遞歸出口怔毛，從而避免方法出現(xiàn)死循環(huán)。
使用遞歸能解決一些經典問題腾降，例如拣度，斐波那契數(shù)列為:0,1,1,2,3,5...，從n到m的階乘等螃壤。
迭代:利用變量的原值推算出變量的一個新值抗果，通過重復一定的算法，達到想要的目的奸晴。迭代就是A不停的調用B冤馏，得到結果。
迭代一般的代碼形式是循環(huán)結構寄啼，for循環(huán)逮光，while循環(huán)等。而遞歸的代碼結構是選擇結構墩划。
遞歸的優(yōu)點是：代碼量極小涕刚，簡潔，可讀性好乙帮；缺點是：遞歸調用函數(shù)杜漠，浪費函數(shù)棧空間蚣旱，并且遞歸太深容易造成堆棧的溢出碑幅。
迭代的優(yōu)點有：迭代效率高，沒有額外的空間消耗塞绿；缺點是：代碼不簡潔沟涨，編寫復雜問題時代碼臃腫。
代碼技術不能只看理論异吻，光說不練假把式裹赴。所以我寫了幾段代碼來驗證下，紙上說的與實際代碼效果是否相符诀浪。
先來看看迭代的方式
- (void)test1 {
//使用迭代的方法棋返，也就是使用for循環(huán)
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
NSUIntegersum = 0;
for(int i = 0; i <= count; i++) {
sum = sum + i;
}
CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent();
NSLog(@"sum=%ld, time cost:%f ms", sum, (endTime - startTime)*1000);
}
這里的count我依次設置了三次值10000，100000雷猪，1000000睛竣，每次也連續(xù)執(zhí)行3次，看其平均值求摇。
當count為10000時射沟，代碼連續(xù)執(zhí)行3次殊者，打印如下
2018-03-08 15:11:24.833246+0800 Test[947:45941] sum=50005000, time cost:0.038028 ms
2018-03-08 15:11:25.945530+0800 Test[947:45941] sum=50005000, time cost:0.036001 ms
2018-03-08 15:11:26.962520+0800 Test[947:45941] sum=50005000, time cost:0.036001 ms
我們再來看看遞歸的實現(xiàn)方式
- (void)test2 {
//使用遞歸的方法
CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
NSUInteger sum = [self addNumberToN:count];
CFAbsoluteTime endTime = CFAbsoluteTimeGetCurrent();
NSLog(@"sum=%ld, time cost:%f ms", sum, (endTime - startTime)*1000);
}
- (NSUInteger )addNumberToN:(NSUInteger )n {
if (n == 0) {
return 0;
}
else {
return n + [self addNumberToN:(n-1)];
}
}
當count為10000時，代碼連續(xù)執(zhí)行3次验夯，打印如下
2018-03-08 15:16:20.969425+0800 Test[963:47741] sum=50005000, time cost:0.447035 ms
2018-03-08 15:16:21.898042+0800 Test[963:47741] sum=50005000, time cost:0.156045 ms
2018-03-08 15:16:23.362979+0800 Test[963:47741] sum=50005000, time cost:0.183940 ms
從上面可以看出猖吴，計算從1到10000的累加之和，循環(huán)迭代的時間消耗比方法遞歸調用要快一個數(shù)量級挥转，并且循環(huán)迭代多次調用的時間消耗相對比較平均海蔽，穩(wěn)定性高。方法遞歸的情況下绑谣，多次調用党窜，第一次耗時最長，之后趨于平均域仇。
之后刑然，我繼續(xù)嘗試了count的值為100000，1000000的情況暇务。
循環(huán)迭代的打印如下
count=100000
2018-03-08 15:27:27.733217+0800 Test[989:51140] sum=5000050000, time cost:0.359058 ms
2018-03-08 15:27:28.909848+0800 Test[989:51140] sum=5000050000, time cost:0.359058 ms
2018-03-08 15:27:30.006191+0800 Test[989:51140] sum=5000050000, time cost:0.316978 ms
count=1000000
2018-03-08 15:28:48.569061+0800 Test[1006:51953] sum=500000500000, time cost:3.015041 ms
2018-03-08 15:28:49.553860+0800 Test[1006:51953] sum=500000500000, time cost:3.122926 ms
2018-03-08 15:28:50.474250+0800 Test[1006:51953] sum=500000500000, time cost:3.030062 ms
方法遞歸的打印如下
count=100000
2018-03-08 15:30:46.876513+0800 Test[1028:53026] sum=5000050000, time cost:4.575968 ms
2018-03-08 15:30:48.066177+0800 Test[1028:53026] sum=5000050000, time cost:1.581073 ms
2018-03-08 15:30:49.620131+0800 Test[1028:53026] sum=5000050000, time cost:2.056003 ms
count=1000000
運行崩潰泼掠，如下圖
可以看到，app的方法棧堆積到了13萬多次垦细，應該是達到iOS系統(tǒng)允許app方法棧數(shù)量的極限择镇，app崩潰。
以上可以看出括改，雖然遞歸代碼簡潔腻豌、可讀性好，但是迭代效率高嘱能，空間消耗小吝梅，時間消耗也比遞歸快一個數(shù)量級。因此惹骂，在我們的日常開發(fā)中還是能用迭代就不用遞歸苏携。
