Begin If n=1 then FIB:=0 Else if n=2 then FIB:=1 Else FIB:=FIB(n-1)+FIB(n-2) End;
测试数据： 输入： 5 输出： 3
9
2．问题的求解方法是按递归算法来实现的。 例如；著名的Hanoi塔（汉诺塔）问题。
3．数据之间的结构关系按递归定义的 例如：大家将在后面的学习内容中遇到的树的 遍历、图的搜索等问题。
begin read(k,n); tentok(k,n); writeln; end.
测试数据： 输入：K和N的值 19 3 输出：转化后的N进制整数 201
8
递归的一般适合场合
1．数据的定义形式是按递归定义的. 如：裴波那契数列的定义为： Fn=Fn-1+Fn-2 F1=0 F2=1 begin program aa; read(n); var s:=fib(n); n:integer; writeln(s); s:longint; end. Function FIB(N:integer):integer;
递归的定义
所谓递归就是一个函数或过程可以直接或间接地调用自己。 我们大家都熟悉一个民间故事：从前有一座山，山上有一 座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说， 从前有一座山，山上有一座庙，庙里有一个老和尚正在给 小和尚讲故事，故事里的故事是说……。象这种形式，我 们就可以称之为递归的一种形象描述，老和尚什么时候不 向下讲了，故事才会往回返，最终才会结束。 再如：前面多次提到的求N!的问题。 我们知道：当N>0时，N!=N*(N-1)!，因此，求N!的问题化成 了求N*(N-1)!的问题，而求(N-1)!的问题又与求N!的解法相同， 只不过是求阶乘的对象的值减去了1，当N的值递减到0时， N!=1，从而结束以上过程，求得了N!的解。
6
程序如下： program aa; procedure reverse; var ch:char; begin read(ch); if ch<>'&' then reverse; write(ch); end; begin reverse; writeln; end.
测试数据： 输入： abcdefghijklmn& 输出： &nmlkjihgfedcba
20
递归过程或函数直接（或间接）调用自身，但如果 仅有这些操作，那么将会由于无休止地调用而引起死循 环。因此一个正确的递归程序虽然每次调用的是相同的 子程序，但它的参数、输入数据等均有所变化，并且在 正常的情况下，随着调用的深入，必定会出现调用到某 一层时，不再执行调用而是终止函数的执行。
递归思路是把一个不能或不好直接求解的“大问题” 转化成一个或几个“小问题”来解决，再把这些“小问 题”进一步分解成更小的“小问题”来解决，如此分解， 直至每个“小问题”都可以直接解决。
其Pascal程序如下：
18
program aa; var m,n,t:integer; function f(m,n:integer):integer; var r:integer; begin if (m mod n)=0 then f:=n else begin r:=m mod n; f:=f(n,r); end; end;
2
递归ห้องสมุดไป่ตู้调用
在Pascal程序中，子程序可以直接自己调用自己或间 接调用自己，则将这种调用形式称之为递归调用。 其中，我们将前者的调用方式称为简单递归，后者称为间 接递归。由于目前我们介绍、掌握的知识尚还无法实现间接 递归，只有留待在以后的内容中我们再作介绍。本节只介绍 直接递归。 递归调用时必须符合以下三个条件： （1）可将一个问题转化为一个新的问题，而新问题的 解决方法仍与原问题的解法相同，只不过所处理的对象有所 不同而已，即它们只是有规律的递增或递减。 （2）可以通过转化过程使问题回到对原问题的求解。 （3）必须要有一个明确的结束递归的条件，否则递归 会无止境地进行下去。 下面我们通过一些例子，来解释递归程序的设计。
3
例1：按照以上的分析，用递归的方法来求N！的解。 程序如下： begin program aa; write('input n='); var read(n); t:longint; if n<0 then n:integer; writeln('n<0,data errer') function fac(n:integer):longint; else begin begin if n=0 then fac:=1 t:=fac(n); else fac:=fac(n-1)*n; writeln(n,'! =',t) end; end end. 测试数据： 输入： input n=5 输出： 4 5! =120
13
程序设计
1.（文件名：d4.pas）利用递归过程，将一个十进 制整数K转化为7进制整数。 测试数据： 输入：十进制数K 19 输出：7进制整数 25
14
2.（文件名：d5.pas）楼梯有N阶台阶，上楼可以 一步上一阶，也可以一步上二阶，计算共有多少种 不同走法。 测试数据： 输入：输入N的值 6 输出：走法总数 13 提示： N=1 f(1)=1 N=2 f(2)=2 当N>=3时f(N)=f(N-1)+f(N-2)
12
3．program d3; var a,b,c,d:integer; procedure p(a:integer; var b:integer); var c:integer; begin a:=a+1;b:=b+1;c:=2;d:=d+1; writeln('m',a,b,c,d); if a<3 then p(a,b); writeln('n',a,b,c,d) end; begin a:=1; b:=1; c:=1; d:=1; writeln('x',a,b,c,d); p(a,b); writeln('y',a,b,c,d); end.
测试数据 输入： 34 输出： 125
17
例5:用辗转相除法求两个自然数m,n的最大公约数。
思路：辗转相除法规定：求两个正整数m,n （m>=n）的最大公约数，应先将m除以n；求得 余数r,如果等于零，除数n就是m,n的最大公约数； 如果r不等于零，就用n除以r，再看所得余数是否 为零。重复上面过程，直到余数r为零时，则上一 次的余数值即为m,n的最大公约数。用其数学方 式描述如下:
15
递归及其应用
例4:已知:ack(m,n)函数的计算公式如下:
请计算ack(m,n)的值。(m,n<=5)
16
program aa; var m,n:longint; a:longint; function ack(m,n:longint):longint; begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1) else ack:=ack(m-1,ack(m,n-1)) end; begin read(m,n); a:=ack(m,n); writeln(a); end.
begin readln(m,n); if m<n then begin t:=m; m:=n; n:=t; end; writeln('gd=',f(m,n)); end.
测试数据 输入： 20 18 输出： gd=2
19
爬楼梯时可以1次走1个台阶，也可以1次走2个台阶。 对于由n个台阶组成的楼梯，共有多少种不同的走法？
10
练习一
判断运行结果
1.program d1; var s,n:integer; function f(n:integer):integer; begin if n=1 then f:=1 else f:=n*n+f(n-1); end; begin write('input n:');readln(n); s:=f(n); writeln('f(',n,')=',s) end.
1个台阶：只有1种走法； 2个台阶：有两种走法；(1+1；2) n个台阶(n>2)，记走法为f(n)： 第1次走1个台阶，还剩(n-1)个台阶，走法为f(n-1)； 第1次走2个台阶，还剩(n-2)个台阶，走法为f(n-2)。 所以，f(n)=f(n-1)+f(n-2)。 定义f(0)=1，则有： function fib(n:integer):longint; n 0 begin 1 f (n) 1 n 1 if(n=0)or(n=1)then fib:=1 f (n 1) f (n 2) n 1 else fib:=fib(n-1)+fib(n-2); end;
如图展示了程序的执行过程： 在这里，因为函数FAC的形 参是值形参，因此每调用一次 该函数，系统就为本次调用的 值形参N开辟了一个存储单元， 以便存放它的实参的值。也就 是说，对于递归函数或递归过 程，每当对它调用一次时，系 统都要为它的形式参数与局部 变量（在函数或过程中说明的 变量）分配存储单元（这是一 个独立的单元，虽然名字相同， 但实际上是互不相干的，只在 本层内有效），并记下返回的 地点，以便返回后程序从此处 开始执行。
算法2：设f(i,j)为a[i]..a[j]中的最小值。将a[0]..a[n]看作一 个线性表，它可以分解成a[0]..a[i]和a[i+1]..a[n]两个子表， 分别求得各自的最小值x和y，较小者就是a[0]..a[n]中的最 小值。而求解子表中的最小值方法与总表相同，即再分 别把它们分成两个更小的子表，如此不断分解，直到表 中只有一个元素为止(该元素就是该表中的最小值)。