在计算机编程实践中常常使用两种方法:一曰递归(recursion),二曰迭代(iterate),文章简要介绍了递归和迭代的概念及区别:
一、递归
递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己。
一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量。递归的能力在于用有限的语句来定义对象的无限集合。
使用递归要注意的有两点:
1)递归就是在过程或函数里面调用自身;
2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口。
递归分为两个阶段:
1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
2)回归:当获得最简单的情况后,逐步返回,依次得到复杂的解。
利用递归可以解决很多问题:如背包问题,汉诺塔问题,...等。比如斐波那契数列为:0,1,1,2,3,5...
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2);
上面就是一个简单的递归调用了。由于递归引起一系列的函数调用,并且有可能会有一系列的重复计算,因此,递归算法的执行效率相对较低。
二、迭代
迭代:是利用变量的原值推算出变量的一个新值,每一次对过程的重复称为一次“迭代”,而每一次迭代得到的结果会作为下一次迭代的初始值。迭代是一个重复反馈过程的活动,其目的通常是为了逼近所需目标或结果。
换句话说,迭代就是重复执行一系列运算步骤的过程,从前面的量依次求出后面的量。此过程的每一次结果,都是由对前一次所得结果施行相同的运算步骤得到的。
在编程实践中,对计算机特定程序中需要反复执行的子程序(一组指令),进行多次重复执行,即重复执行程序中的循环部分,直到满足某条件为止,称为迭代,比如for 循环,while循环,do while循环。迭代则常常使用计数器结束循环。
注意:递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。
下面举一个简单的例子来说明:
//这是递归
int funcA(int n)
{
if(n > 1)
return n+funcA(n-1);
else
return 1;
}
//这是迭代
int funcB(int n)
{
int i,s=0;
for(i=1;i<n;i++)
s+=i;
return s;
}
下面再举一个例子来说明:
#include <iostream>
using namespace std;
//迭代实现斐波那契数列
long fab_iteration(int index)
{
if(index == 1 || index == 2)
{
return 1;
}
else
{
long f1 = 1L;
long f2 = 1L;
long f3 = 0;
for(int i = 0; i < index-2; i++)
{
f3 = f1 + f2; //利用变量的原值推算出变量的一个新值
f1 = f2;
f2 = f3;
}
return f3;
}
}
//递归实现斐波那契数列
long fab_recursion(int index)
{
if(index == 1 || index == 2)
{
return 1;
}
else
{
return fab_recursion(index-1)+fab_recursion(index-2); //递归求值
}
}
int main(int argc, char* argv[])
{
cout << fab_recursion(10) << endl;
cout << fab_iteration(10) << endl;
return 0;
}