昨天在群里看到有群友在讨论迭代与递归的区别，仔细检索了下大脑，好像真的记不清了，有些惭愧...。有空搜索下了，终于知道了它们的区别。以下概念内容参考于铭毅天下的博文
递归的基本概念：程序调用自身的编程技巧称为递归，是函数自己调用自己。
一个函数在其定义中直接或间接调用自身的一种方法。它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决，可以极大的减少代码量。递归的能力在于用有限的语句来定义对象的无限集合。
使用递归时需要注意的两点：
1.递归就是在过程或函数里面调用自身;
2.在使用递归时，必须有一个明确的递归结束条件，称为递归出口，从而避免方法出现死循环。
使用递归能解决一些经典问题，例如，斐波那契数列为:0,1,1,2,3,5...，从n到m的阶乘等。
迭代:利用变量的原值推算出变量的一个新值，通过重复一定的算法，达到想要的目的。迭代就是A不停的调用B，得到结果。
迭代一般的代码形式是循环结构，for循环，while循环等。而递归的代码结构是选择结构。
递归的优点是：代码量极小，简洁，可读性好；缺点是：递归调用函数，浪费函数栈空间，并且递归太深容易造成堆栈的溢出。
迭代的优点有：迭代效率高，没有额外的空间消耗；缺点是：代码不简洁，编写复杂问题时代码臃肿。
代码技术不能只看理论，光说不练假把式。所以我写了几段代码来验证下，纸上说的与实际代码效果是否相符。
先来看看迭代的方式
- (void)test1 {
//使用迭代的方法，也就是使用for循环
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，每次也连续执行3次，看其平均值。
当count为10000时，代码连续执行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
我们再来看看递归的实现方式
- (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时，代码连续执行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的累加之和，循环迭代的时间消耗比方法递归调用要快一个数量级，并且循环迭代多次调用的时间消耗相对比较平均，稳定性高。方法递归的情况下，多次调用，第一次耗时最长，之后趋于平均。
之后，我继续尝试了count的值为100000，1000000的情况。
循环迭代的打印如下
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
运行崩溃，如下图
屏幕快照 2018-03-07 下午5.18.45.png
可以看到，app的方法栈堆积到了13万多次，应该是达到iOS系统允许app方法栈数量的极限，app崩溃。
以上可以看出，虽然递归代码简洁、可读性好，但是迭代效率高，空间消耗小，时间消耗也比递归快一个数量级。因此，在我们的日常开发中还是能用迭代就不用递归。
网友评论