迭代和递归,在算法中很常用呢,算的上是算法中必不可少的实用技巧!让我们来了解一下吧。
递归:程序调用自身的编程技巧称为递归( recursion)。
迭代:迭代是重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值。
【递归VS迭代】
递归和迭代都是循环的一种。
递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环。
递归循环中,遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。很多情况都是多种循环混合采用。
例子:递归函数求n!
1. #include<stdio.h> 2. long f(int n) 3. { 4. if(n==0) return 1; 5. else return n*f(n-1); 6. } 7. main() 8. { 9. int m,n=3; 10. m=f(n); 11. printf("%d!=%d\n",n,m); 12. }
f(n)是递归函数,在它的函数体中用到了它本身。
【迭代VS普通循环】
迭代的循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。
下方的代码是迭代。
1. for(i=1;i<=n;i++) 2. { 3. temp=temp*i; /temp*=i;这样的形式更有明显,容易辨认。 4. s=s+temp; /s+=temp; 5. }
temp和s都参与运算,同时也保存运算结果,下一次循环继续参与运算。
【借用临时变量】
1、交换两个存在于数组中数的位置
例子:出自一维数组逆置算法之一。
1. for(i=0;i<n/2-1;i++) 2. { 3. temp=a[i]; 4. a[i]=a[n-1-i]; 5. a[n-1-i]=temp; 6. }
2、单链表插入操作
例子:出自单链表插入结点算法。
1. p-data=x; 2. p->next=head->next; 3. head->next=p;
算法的学习还在继续,总结将不断出新,敬请期待。