递　　归

一、递归的基本概念。

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

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

……

又必须用到它的上一状态

这种用自己来定义自己的方法，称之为递归或递归定义。在

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

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

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

单，于是人们想出另一种办法来描述这种数列：通过初值及与前面临近几项之间的关系。

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

间各项的关系。

比如阶乘数列
1、2、6、24、120、720……
如果用上面的方式来描述它，应该是：

如果需要写一个函数来求的值，那么可以很容易地写成这样：

int f(int n)
{

if(n==1)

return 1;

  return n*f(n-1);
}

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

——

——

理一些特殊情况

这也是递归函数的第一个出口，再处理递归关系

这形成递归函

数的第二个出口。

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

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

n

a







>

=

=

−

1

,

1

,

1

1

n

na

n

a

n

n

n

a

1

1

的执行过程

（特殊值判断：）

（

，继续向下。

（递归关系处理：）

求，需要先计算，

调用

……

，且本身挂起

……
……

得到，由正常出口

返回

返

的执行过程

（特殊值判断：）

（

，继续向下。

（递归关系处理：）

求，需要先计算，

调用

……

，且本身挂起

……
……

得到，由正常出口

返回

返

的执行过程

（特殊值判断：）

（

，由特殊情况出

口直接返回 1 。