文档介绍：递归的定义
一、定义
一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)。
如:
procedure a;
  begin
    ...
    a;
    ...
  end;
这种方式是直接调用;
又如:
procedure b;
  begin
    ...
    c;
    ...
  end;
procedure c;
  begin
    ...
    b;
    ...
  end;
这种方式是间接调用;而它们都属于递归调用。
二、举例
例1 计算n!
分析:可用递归公式如下:
1 当 n=0 时 
fac(n)= n*fac(n-1) 当n>0时
可编写程序如下:
program fac2;
var
  n:integer;
function fac(n:integer):real;
  begin
    if n=0 then fac:=1 else fac:=n*fac(n-1)
  end;
begin
  write('n=');readln(n);
  writeln('fac(',n,')=',fac(n):6:0);
end.
例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法。
分析:设n阶台阶的走法数为f(n),显然有:
1 n=1 
f(n)= 2 n=2
f(n-1)+f(n-2) n>2
可编程序如下:
program louti;
var n:integer;
function f(x:integer):integer;
  begin
    if x=1 then f:=1 else
    if x=2 then f:=2 else f:=f(x-1)+f(x-2);
  end;
begin
  write('n=');read(n);
  writeln('f(',n,')=',f(n))
end.
如何设计递归算法
设计递归算法,主要有两步
(终了)条件
要注意学会把具体问题分解为几个子问题,如果你分解的这些子问题的形式和算法与原问题相似,那么,你的递归算法就能很快完成。
练习:
试用递归的方法完成下列问题
+2+3+...+n
,?
:数列1,1,2,4,7,13,24,44,...求数列的第 n项
典型例题与习题
例1 梵塔问题
已知有三根针分别用1,2,3表示,在1号针中从下到上放着由大到小的n个盘子,现要求把所有的盘子从1号针全部移到3号针,移动规则是:使用2号针作为过度针,每次只移动一个盘子,且每根针上不能出现大盘压小盘。试找出移动次数最小的方案。
程序如下:
program fanta;
var
  n:integer;
procedure move(n,a,b,c:integer);
  begin