最显然的情况是直接递归，即在函数中直接显式地调用它本身。我们来看一个简单的关于递归的例子:
f(int n)
{
...
f(n/2);
...
}
另外的情形是, 一个函数调用另一个函数, 它又返过来调用第一个函数。这种情形称为间接递归。例如:
a(int n)
{
...
b(n/3);
...
} |
b(int n)
{
...
a(n/2);
...
} |
对于不熟悉递归的用户, 它看起来似乎是错误定义的和危险的循环。有人认为这种程序可能在永不终止的函数调用序列中循环。当然, 这是可能的, 但这只是在函数定义不正确时才会发生。
对程序而言, 递归函数的目的是执行一系列调用, 一直到达某一点, 序列终止。
为了保证递归函数是正常执行的, 你应该遵守下面的规则:
1. 每次当一个递归函数被调用时, 程序首先应该检查其些基本的条件是否满足了, 例如某个参数的值等于零, 如果是这种情形, 函数应停止递归。
2. 每次当函数被递归调用时, 传递给函数一个或多个参数, 应该以某种方式变得"更简单"。即, 这些参数应该逐渐靠近上述基本条件。例如, 一个正整数在每次递归调用时会逐渐变小, 以至最终其值能到达零。
下面, 我们将用一个广为人知的例子----阶乘函数来说明这些规则。
阶乘函数是按照递推关系式来定义的:
f(0) = 1
f(n) = n * f(n-1) (n>0)
这个定义很快说明了如何用 C 语言来编写一个能满足这两个条件的阶乘函数。
int f(int n)
{
if (n==0)
return(1);
else
return(n * f(n-1));
}
注意这个程序是如何遵循上面两条规则的。
如果基本条件, 即参数等于零满足的话, 递归就终止了。
如果这个条件不满足, 函数每次递归传送一个比上一次更小的参数给被调用函数。最终参数值将为零, 正好满足终止条件。
让我们看一下 n=3 时阶乘函数执行的情况。
返回页首
