from https://zhidao.baidu.com/question/1638784639202969220.html
递归和迭代都是循环的一种。
简单地说,递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环,而迭代与普通循环的区别是:循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。
递归循环中,遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。当然很多情况都是多种循环混合采用,这要根据具体需求。
递归的例子,比如给定一个整数数组,采用折半查询返回指定值在数组中的索引,假设数组已排序,为方便描述,假设元素都为正数,数组长度为2的整数倍。
折半查询是查询的一种,比遍历所有元素要快很多。
1 int Find(int *ary,int index,int len,int value) 2 { 3 if(len==1)//最后一个元素 4 { 5 if (ary[index]==value)return index;//成功查询返回索引 6 return -1;//失败,返回-1 7 } 8 //如果长度大于1,进行折半递归查询 9 int half=len/2; 10 //检查被查值是否大于上半部分最后一个值,如果是则递归查询后半部分 11 if(value>ary[index+half-1]) 12 return Find(ary,index+half,half,value); 13 //否则递归查询上半部分 14 return Find(ary,index,half,value); 15 }
迭代经典例子就是实数的累加,比如计算1-100所有实数的和。
1 int v=1; 2 for(i=2;i<=100;i++) 3 { 4 v=v+i;
递归与迭代都是基于控制结构:迭代用重复结构,而递归用选择结构。
递归与迭代都涉及重复:迭代显式使用重复结构,而递归通过重复函数调用实现重复。
递归与迭代都涉及终止测试:迭代在循环条件失败时终止,递归在遇到基本情况时终止。
使用计数器控制重复的迭代和递归都逐渐到达终止点:迭代一直修改计数器,直到计数器值使循环条件失败;递归不断产生最初问题的简化副本,直到达到基本情况。迭代和递归过程都可以无限进行:如果循环条件测试永远不变成false,则迭代发生无限循环;
如果递归永远无法回推到基本情况,则发生无穷递归。
递归函数是通过调用函数自身来完成任务,而且在每次调用自身时减少任务量。而迭代是循环的一种形式,这种循环不是由用户输入而控制,每次迭代步骤都必须将剩余的任务减少;也就是说,循环的每一步都必须执行一个有限的过程,并留下较少的步骤。