|
引言
在调用一个函数的过程中有出现直接或间接地调用该函数本身,称为函数的递归调用.对于初学者来说,递归函数是比较难以理解的.现在的程序设计的教材对于递归都比较简单,例子从一开始较难理解.加之不了解函数调用在计算机中的实现过程就更难理解递归调用了.这篇文章从初学者的角度对递归给予了一定的解释.
从一个简单的数学题开始
有一个等差数列,首项是3,公差是2,求第5项a5.我想这是所有高中生都会的题.再简单不过,只要知道通项公式an=a1+(n-1)k (这里k是公差) 代入即可. 大家都知道通项是由递推公式推导来的,递推公式直接用数学语言反映了等差数列的性质,an=a(n-1)+k.如果大家不知道通项公式,那么在这道题中,计算的方法是:a2=a1+2;a3=a2+2;a4=a3+2;a5=a4+2.知道a5=11,经过5次计算便可以得到a5的值.如果计算机也不知道通项公式,在如果我们要计算第一百项,亦或是第一万项,我们难道要a2=a1+2;a3=a2+2......a10000=a9999+2 这样来计算吗.当然不是,我们可以用递归函数实现,而a2=a1+2;a3=a2+2......a10000=a9999+2 的过程便是递归的回推过程,可是计算机确实没有我们广大高中生聪明,它不知道直接这样求解,呵呵.
在计算机中的实现
要说清楚递归函数的实现就要了解程序里函数嵌套调用在计算机中的实现过程.我们来看下面一个函数的调用,这里我们用类似C语言的函数形式:
f()
{ .... //其他代码
g(a); //调用函数g(),参数是a
return ... //函数的返回值
}
//-----------------------------------------------------------
main() //主函数
{ ..... //其他代码
f(b); //调用函数f(),参数是b
}
主函数在执行的过程中调用了函数f(),而f()其自身又调用了另一个函数g().那么这种嵌套调用在计算机中又是怎么实现的呢?在函数的执行过程中,系统用到了栈内存.栈是一种数据结构,就是有特定数据存取方式的容器.栈使用的存取方式称为后进先出LIFO(late in first out),也就是后面放入的数据先离开栈,最先放入的数据最后离开.大家可以把栈看成一个和盘子一样大小放的水槽,放入其中的盘子只能从最上面依次取走,不下面的盘子只能等它上面的取走之后才能取出.栈是一种在计算机中非常重要的数据结构,它后进先出的性质也直接关系到了函数嵌套调用在计算机中的实现.
当一个函数的执行过程中需要调用另一个函数时,需要保留现场,意思是系统保存现有的所有数据,把他们放入栈内存,称为压入栈.之后就转到要调用的那个函数处执行了,并把参数传给它.等到调用的那个函数执行完了,系统就把刚才压入栈内存的数据都取出,称为弹出栈.并且把他调用的函数的返回值给原函数.如果被调用的函数中还要调用其他函数,系统也按照上述的方法保存和取回数据.栈的性质能很好得适用于这一过程.
在来看递归函数,按引言里的意思,在上述的过程中被调用的函数就是调用函数自己.其实现的过程是一样的.是不是很简单?
再看一些例子
文章开始等差数列的例子写成函数就是(方便起见,值都设为整数):
int getan(int n, int a1) // 要求第n项,a1为已知的首项
{
if(n==1)
return a1; //如果n=1,返回a1的值,这是递归得以结束的关键
else
return getan(n-1,a1)+2 ; //不等于1,则再次调用自身求出第n-1项,返回结果加上公差2
}
//-------------------------------------------------------
main() //主函数
{
int a1=3; //设首项
int a5=getan(5,3); //递归求解第5项a5
printf(d%,a5); //输出
}
递归函数调用自身是一个不断循环过程,就像循环语句需要有条件让它停止循环,否则就陷入了无限循环之中,那后果......天啊!所以if(n=1) return a1;就是停止递归的条件.
我们来仔细地看一下a5是如何求出的,不要嫌罗嗦,来:
首先当主函数执行到int a5=getan(5,3); 开始求 a5的值.
n=5>1 所以gatan()函数又调用自身,并把参数5-1=4和3传给下一个函数,所以执行getan(4,3);
n=4>1 gatan()函数再次调用自身,并把参数3和3传给下一个函数,所以执行getan(3,3);
n=3>1 执行getan(2,3);
n=2>1 执行getan(1,3);
终于,n=1了,现在getan(1,3)的返回值是3.
getan(2,3); 返回值是3+2=5.
getan(3,3);返回7.
getan(4,3);返回9.
最后getan(5,3);返回11,变量a5=11,结果也就出来了.
从理论上我们把函数反复调用自身的过程称为递推的过程,而每个函数的返回称之为回推.递推的过程把复杂的问题一步步分解开,直到出现最简单的情况,就像已知a1=3.得到了最简单情况的解,就可以回推回去得出原来复杂问题的答案了.要说明的一点是,在这里我们认为函数的使用者总是正确的,不会把诸如-1,0,5.2等之类不合理项数作为参数输入,所以没有做出错检查.
另外,刚才的函数中我们在其内部设了公差2,其实可以有更一般的情况,将公差k由参数传入:
getan(int n, int a1, int k)
{
if(n==1) return a1;
else getan(n-1,a1,k);
}
结束这个例子前还是不得不说一句,我们是在假设不知道通项公式的情况下,为了说明问题才抛出这个例子,其实可以这样:
getan(int n, int a1, int k)
{
return a1+(n-1)*k; //使用通项公式求解
}
喔,计算机这下聪明了.
在来看一个典型的求阶乘的例子n! 数学上,阶乘公式是:
n!=1 (当n=1,0)
n!=n(n-1)! (当n>1)
写成递归函数可以是:
float fac(int n)
{
if(n<0) print("错误!");
else if(n==0 || n==1) return 1;
else return fac(n-1)*n;
}
然后可以在主函数里这样调用:
main()
{
int a;
a=fac(99); //求99的阶乘
printf(f%,a); //输出
}
小结
这两个例子是递归的最简单的情况.像汉诺塔,八皇后也是十分经典的递归问题,大家有兴趣可以参考程序设计的书籍.但是和上述的例子的实质是一样的.要注意几个问题:1.递归函数一定要有停止递归的语句,程序不要出现逻辑上的错误. 2.参数的传递体现了递推和问题简化的过程,一般来说内层函数和外层函数的参数是直接有联系的.函数的返回值体现了回推的过程.
|
