一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
一、简单的递归调用
1. 例1：用递归策略求N!的解。
N! = 1 * 2 * 3 * .. . * N
分析：
(1) 不运用递归的解法
program ppro1;
var
n, i: integer;
npi: longint;
begin
write('Enter a number(>0):'); readln(n);
npi := 1;
for i := 1 to n do
npi := npi * i;
writeln('N!=', npi);
end.
(2) 运用递归策略
N! = 1 * 2 * 3 * .. . * N
= [1 * 2 * 3 * .. . * (N - 1)] * N
(N - 1) ! = 1 * 2 * 3 * .. . * (N - 1)
设 f(N) = N!
那么 f(N - 1) = (N - 1) !
则 f(N) = f(N - 1) * N
这就是递归式子，由于式子中有N - 1，所以N >= 1，递归出口的条件是N = 1时。
函数模式：
|
function f(n: integer) : longint;
var
.. .
begin
if 递归出口的时候 then
f := 1
else
f := f(n - 1) * n;
end;
|
2.例2：用递归策略求斐波那契数。
1 1 2 3 5 8 13 21 34 .. .
分析：
将上述的数存于数组A中，可知A[n]=A[n-1]+A[n-2]
由此有：
A(n)=A(n-1)+A(n-2)
由于上式中出现了n-1和n-2，所以n>=2，
则递归出口的条件是N=1或N=2
|
|
|
|
