2024年5月21日发(作者：)

递

一、递归的基本概念。

归

冯文科

一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引

用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须

用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计

中，函数直接或间接调用自己，就被称为递归调用。

二、递归的最简单应用：通过各项关系及初值求数列的某一项。

在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，

于是人们想出另一种办法来描述这种数列：通过初值及

a

n

与前面临近几项之间的关系。

要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各

项的关系。

比如阶乘数列

1、2、6、24、120、720……

如果用上面的方式来描述它，应该是：

⎧

1,

n

=1

a

n

=

⎨

⎩

na

n

−1

,

n

>1

如果需要写一个函数来求

a

n

的值，那么可以很容易地写成这样：

intf(intn)

{

if(n==1)

return1;

returnn*f(n-1);

}

这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一

些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二

个出口。

递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为

特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问

题的解。

以上面求阶乘数列的函数

f

(

n

)

为例。如在求

f

(3)

时，由于3不是特殊值，因此需要计

算

3*

f

(2)

，但

f

(2)

是对它自己的调用，于是再计算

f

(2)

，2也不是特殊值，需要计算

2*

f

(1)

，需要知道

f

(1)

的值，再计算

f

(1)

，1是特殊值，于是直接得出

f

(1)=1

，返回上

1

一步，得

f

(2)=2*

f

(1)=2

，再返回上一步，得

f

(3)=3*

f

(2)=3*2=6

，从而得最

终解。

用图解来说明，就是

f

(3)

的执行过程

（特殊值判断：）

f

(2)

的执行过程

（特殊值判断：）

f

(1)

的执行过程

（特殊值判断：）

3≠1

，继续向下。

（递归关系处理：）

求

3*

f

(2)

，需要先

计算

f

(2)

，调用

f

(2)

，

且本身挂起……

……

……

得到

f

(2)=2

，由正

常出口返回

3*2

2≠1

，继续向下。

（递归关系处理：）

求

2*

f

(1)

，需要先

计算

f

(1)

，调用

f

(1)

，

且本身挂起……

……

……

得到

f

(1)=1

，由正

常出口返回

2*1

1=1

，由特殊情

况出口直接返回1。

下面再看一个稍复杂点的例子。

【例1】数列

{

a

n

}

的前几项为

1、

1

、

1+1

1

1

1+

1+1

、

1

1+

1+

1

1

1+1

、……

输入

n

，编程求

a

n

的精确分数解。

分析：

这个题目较易，发现

a

1

=1

，其它情况下有

a

n

=

1

。如要求实数解的话，这基本

1+

a

n

−1

已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设

a

n

−1

=

q

，

p

则由递归关系，有

a

n

=

1

=

1+

a

n

−1

1

1+

q

p

=

p

，再约分化简，即得

a

n

。但发现一个问题：

p

+

q

2