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

科技信息　专题论述　

递归算法硇研夯及经典算法硇递归实坝　

常州工学院计算机信息工程学院　丁志云　

［摘要］递归思想是计算机科学的一个重要思想，递归方法是程序设计中的有效方法，它为程序设计者打开了一个全新的程序设计　

思路。采用递归思想编程，可以将一些貌似复杂的问题简单化，编写的程序更加简洁明了。本文深入分析了递归思想的特点，递归算　

法的优点和缺点，通过对多个经典算法的递归实现，让读者掌握递归算法程序设计的一些方法和技巧，有助于提高程序初学者的编　

程水平。　

［关键词］递归　算法

１．引言　

程序设计　

阶段，层层返回最终得到问题的解答。如图２所示是递归算法执行过程　

示意图。　

５．递归算法实例　

递归算法是一种直接或者间接地调用自身的算法。在计算机程序　

设计中，递归算法对解决有些问题是十分有效的，它往往使算法的描述　

简洁而且易于理解，当使用非递归方法难于解决问题时，尝试用递归方　

法也许会给你带来意想不到的惊喜。著名的汉诺塔（Ｈａｎｏｉ）问题，八皇　

后问题，斐波那契（Ｆｉｂｏｎａｃｃｉ）的兔子问题，猴子吃桃问题，年龄问题等　

都是递归问题。　

２．递归算法的特点　

递归就是在过程或函数里调用自身。递归程序在执行过程中总是　

不断地调用自身，而每次调用自身时，通常在规模上都有所缩小，当问　

题的规模缩小到某一值时就可以直接给出解答而不再进行递归调用，　

因而每次递归调用都是有条件的（以规模未达到直接解答的大小为条　

件），而且相邻两次调用之间有紧密的联系，前一次要为后一次做准备　

（通常前一次的输出就作为后一次的输入），在使用递归策略时，必须有　

一

个明确的递归结束条件，也称为递归出口。　

递归算法一般用于解决三类问题：　

（１）数据的定义是按递归定义的，如Ｆｉｂｏｎａｃｃｉ函数。　

（２）问题解法按递归算法实现，如回溯问题。　

（３）数据的结构形式是按递归定义的，如树的遍历，图的搜索等。　

递归算法设计的基本思想是：对于一个复杂的问题，把原问题分解　

为若干个相对简单的同类子问题，继续下去直到子问题简单到能够直　

接求解，也就是说到了递归的出口，这样原问题就有递推得解。所以在　

使用递归算法时，首先要弄清楚简单情况下的解法，然后弄清楚如何把　

复杂情况归纳为更简单的情况。　

３．递归算法的分类　

递归算法一般通过函数或子过程来实现。在函数或子过程的内部，　

直接或者间接地调用自己的算法。所以根据递归算法的表示形式，可以　

将递归算法分为递归函数和递归子过程两种；根据递归算法调用的形　

式可以有直接递归和间接递归两种。如图１所示是直接递归和间接递　

归调用过程的示意图。　

旨　当闻｛　小　

捌薹一　

递归函数　

或子过程　问颓匍　

Ｊ、　

Ａ　］　

ｌ１．￣ｉｉｔＢ间Ｉ蠹递归　

图ｌ直接递归和间接递归调用过程的示意图　

４．递归算法的执行过程　

开始递归过程Ａ　递归过程Ａ　递归过程Ａ递归过程Ａ　

苦

静　

结柬　调用Ａ—

　

　：

Ｉ　

　调用Ａ一

ｒ　静管　　

　

图２递归算法执行过程示意图　

递归算法求解问题是通过不断调用自身来实现的，在反复调用过　

程中，通常将问题的规模不断缩小，当缩小到某一值时，就能够直接求　

解，再一一返回后求出问题的最终解。所以递归算法的执行分为两个阶　

段，第一阶段是逐层调用阶段，又称为递推阶段。在这一阶段通常是对　

一

个规模较大问题的求解转化成一个规模较小问题的求解，当规模小　

到某一值时，就能直接得到问题的解答，而不必再递归调用。第二阶段　

是逐层返回阶段，又称为回归阶段。当第一阶段完成后，进入逐层返回　

编写递归程序从两个方面人手，一是找出递归表达式（递归公式），　

二是确定递归的终止条件（递归出口），多数递归都有明确的递归表达　

式，此类递归算法简单明了，在编写此类递归程序时，通常只用简单的　

分支结构就可以实现。例如，求自然数ｎ的阶乘，求斐波那契（Ｆｉｂｏｎ　一　

ｃｉ）数列的第ｎ项的值，求１－ｎ个连续自然数的和等。下面用ＶＢ将我们　

教学中常见的经典算法用递归算法来实现。　

【例１】用递归算法求自然数ｎ的阶乘。　

分析：要求ｎ的阶乘，只要求出ｎ一１的阶乘，则ｎ！＝ｎ　（ｎ一１）！，可以定　

义一个函数ｆａｃｔ（ｎ），表示求ｎ！，则递归表达式为：ｆａｃｔ（ｎ）＝ｎ＊ｆａｃｔ（ｎ一１），递归　

的终止条件是当ｎ＝ｌ或者ｎ＝０时，ｆａｃｔ（ｎ）＝１。递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｆａｃｔ（ＢｙＶａｌ　ａ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｌｏｎｇ　

・求ｎ的阶乘　

Ｉｆ　ｎ：ｌ　Ｏｒｎ＝０Ｔｈｅｎ　

ｆａｃｔ＝１　

Ｅｌｓｅ　

ｆａｃｔ＝ｎ　ｆａｃｔ（ｎ一１１　

ＥｎｄＩｆ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例２】用递归算法求斐波那契（Ｆｉｂｏｎａｃｃｉ）数列第ｎ项的值。　

分析：根据Ｆｉｂｏｎａｃｃｉ数列的特点，可以定义一个函数ｆｉｂ（ｎ），表示求　

Ｆｉｂｏｎａｃｃｉ数列第ｎ项的值，则递归表达式为：ｉｆｂ（ｎ）＝ｆｉｂ（ｎ一１）＋ｆｉｂ（ｎ一２），递　

归的终止条件是当ｎ＝ｌ或者ｎ＝２时，ｆｉｂ（ｎ）＝ｌ。递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｉｆｂ（ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｉｎｔｅｇｅｒ　

’求Ｆｉｂｏｎａｃｃｉ数列第ｎ项的值　

Ｉｆｎ＝１　Ｏｒｎ＝２Ｔｈｅｎ　

ｉｆｂ＝１　

Ｅｌｓｅ　

ｉｆｂ＝ｆｉｂ（ｎ一１１＋ｆｉｂ　ｎ一２、　

ＥｎｄＩｆ　

【例３】用递归算法求１～ｎ个连续自然数的和。　

分析：可以定义一个函数ｓｕｍ（ｎ），表示求ｌ￣ｎ个连续自然数的和，　

则递归表达式为：ｓｕｍ（ｎ）＝ｎ＋ｓｕｍ（ｎ—１），递归的终止条件是当ｎ＝ｌ时，ｓｕｍ　

（ｎ）＝ｌ。递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｓｕｍ（ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｉｎｔｅｇｅｒ　

’求１～ｎ个连续自然数的和　

Ｔｆｎ＝１　Ｔｈ　ｎ　

ｓｕｍ＝１　

Ｅｌｓｅ　

ｓｕｍ　ｎ＋ｓｕｍ（ｎ一１１　

ＥｎｄＩｆ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例４】用递归算法实现字符串的反序。　

分析：要对一个由ｎ个字符组成的字符串反序，只要对该字符串前　

面的ｎ一１个字符实现反序，就可以很容易实现该字符串的反序。可以定　

义一个函数ｒｅｖｅｒｓｅ（ｓｔ），表示对字符串ｓｔ实现反序，则递归表达式为：ｒｅ—　

ｖｅｒｓｅ（ｓｔ）＝Ｒｉｇｈｔ（ｓｔ，１）＆ｒｅｖｅｒｓｅ（Ｌｅｆｔ（ｓｔ，Ｌｅｎ（ｓｔ）一１）），递归的终止条件是当　

Ｌｅｎ（ｓｔ）≤１时，ｒｅｖｅｒｓｅ（ｓ０＝ｓｔ。递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｒｅｖｅｒｓｅ（ｓｔ　Ａｓ　Ｓｔｉｒｎｇ）Ａｓ　Ｓｔｉｒｎｇ　

’字符串反序　

ＩｆＬｅｎ（ｓｔ）＜＝１　Ｔｈｅｎ　

ｒｅｖｅｒｓｅ＝ｓｔ　

Ｅｌｓｅ　

ｒｅｖｅｒｓｅ＝Ｒｉｇｈｔ（ｓｔ，１）＆ｒｅｖｅｒｓｅ（Ｌｅｆｔ（ｓｔ，Ｌｅｎ（ｓｔ）一１））　

－－－——

３８７－－－——　

科技信息　专题论述　

ＥｎｄＩｔ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例５】用递归算法实现将一个十进制整数转换成二进制。　

分析：可以定义一个递归函数ｔｒａｎｓ（ｎ），表示将一个十进制整数ｎ转　

换成二进制，不难得出它的递归表达式为：ｔｒａｎｓ（ｎ）＝ｔｒａｎｓ（ｎ＼２）＆（ｎ　Ｍｏｄ　

２１，当ｎ＝ｌ或者ｎ＝Ｏ时，ｔｒａｎｓ（ｎ）＝ｎ，递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｔｒａｎｓ（ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｓｔｒｉｎｇ　

’将一个十进制整数转换成二进制　

Ｉｆｎ＜：ｌ　Ｔｈｅｎ　

ｔｒａｎｓ＝ｎ　

Ｅｌｓｅ　

ｔｒａｎｓ：ｔｒａｎｓ（ｎ＼２）＆（ｎＭｏｄ　２）　

ＥｎｄＩｆ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例６】用递归算法实现求数组元素之和。　

分析：可以定义一个递归函数ｓｕｍ（ａ０，ｎ），表示求数组ａ中前ｎ个元　

素的和，则递归表达式为：ｓｕｍ（ａ０，ｎ）＝ｓｕｍ（ａ０，ｎ一１）＋ａ（ｎ），当ｎ＝ｌ时，ｓｕｍ（ａ　

０，１）＝ａ（１），递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｓｕｍ（ａ０　Ａｓ　Ｉｎｔｅｇｅｒ，ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｉｎｔｅｇｅｒ　

’求数组前ｎ个元素之和　

Ｉｆｎ＝１　Ｔｈｅｎ　

ｓｕｍ＝ａ（１）　

Ｅｌｓｅ　

ｓｕｍ＝ｓｕ，ｎ（ａ，ｎ—１）＋ａ（ｎ）　

ＥｎｄＩｆ　

Ｅｎｄ　ｕｎｃｔｉｏｎ　

【例７】用递归算法求数组中所有数的最大值。　

分析：要求出数组中所有数的最大值，若能求出前ｎ一１个数的最大　

值（假设数组中共有ｎ个数），则再与第ｎ个数比较，即可得到最大值，　

同样的要求出前ｎ一１个数的最大值，则只要求出前ｎ一２个数的最大值，　

再与第ｎ一１个数比较，如此下去，当ｎ＝ｌ时，最大值就是本身，递归结　

束。　。　

可以定义一个递归函数ｍａｘ（ａ０，ｎ），表示求数组ａ中前ｎ个数的最　

大值，则ｍａｘ（ａ０，ｎ）＝ｍａｘ（ａ０，ｎ—１）与ａ（ｎ）的比较，若ａ（ｎ）＞ｍａｘ（ａ０，ｎ一１），则　

ｍａｘ＝ａ（ｎ），否则ｍａｘ＝ｍａｘ（ａ０，ｎ一１），递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　Ｍａｘ（ａ０　Ａｓ　Ｉｎｔｅｇｅｒ，ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｉｎｔｅｇｅｒ　

’求数组前ｎ个元素的最大值　

Ｉｆｎ：１下ｈＰｎ　

Ｍａｘ＝ａｆ１１　

Ｅｌｓｅ　

Ｍａｘ＝ＭｔＬｘ（ａ，ｎ～ｌ１　

Ｉｆａ（ｎ１＞ＭａｘＴｈｅｎＭａｘ＝ａ（ｎ１　

ＥｎｄＩｆ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例８】用递归算法判断一个数是否是回文数。　

分析：要判断一个数是否是回文数，只要判断首尾数字字符是否相　

等，若不等，则不是回文数，若相等，则去掉该数的首尾数字字符，再判　

断去掉首尾字符后的新数字是否是回文数，如此下去，当新数字的长度　

小于等于１时，是回文数（已知）。递归函数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｈｗｓ（ＢｙＶａｌ　ｓｔ　Ａｓ　Ｓｔｉｒｎｇ）Ａｓ　Ｂｏｏｌｅａｎ　

’判断一个数是否是回文数　

ＩｆＬｅｎ（ｓｔ１＜：１　Ｔｈｅｎ　

ｈｗｓ＝Ｔｒｕｅ　

Ｅｘｉｔ　Ｆｕｎｃｔｉｏｎ　

Ｅｌｓｅｌｆ　Ｌｅｆｔ（ｓｔ，１）＜＞Ｒｉｇｈｔ（ｓｔ，１）Ｔｈｅｎ　

Ｅｘｉｔ　Ｆｕｎｃｔｉｏｎ　

ＥｎｄＩｆ　

ｈｗｓ＝ｈｗｓ（Ｍｉｄ（ｓｔ，２，Ｌｅｎ（ｓｔ）一２））　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

【例９】用递归算法求一个正整数的所有因子，并存放在一个数组　

中。　

分析：可以定义一个递归子过程ｇｅｎ（ｎ，ｎｌ，ａＯ），功能是判断Ｉｎ是否是　

正整数ｎ的一个因子，若是则将Ｉｎ存放在数组中，ｍ从１开始，当ｍ＞ｎ　

时，递归结束，否则ｍ＋ｌ，再调用该递归子过程。递归子过程如下：　

Ｐｒｉｖａｔｅ　Ｓｕｂ　ｇｅｎ（ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ，ｍ　Ａｓ　Ｉｎｔｅｇｅｒ，ａ０　Ａｓ　Ｉｎｔｅｇｅｒ）　

’求一个正整数的所有因子，存放在一个数组中　

Ｓｔａｔｉｃ　ｋ　Ａｓ　Ｉｎｔｅｇｅｒ　

ＩｆｎＭｏｄｍ＝０ＴｈＰｎ　

３８８．．．——　

ｋ＝ｋ＋ｌ　

ＲｅＤｉｍ　Ｐｒｅｓｅｒｖｅ　ａ（ｋ）　

ａ（ｋ）＝ｍ　

ＥｎｄＩｆ　

Ｉｆｍ＞ｎＴｈｅｎ　

Ｅｘｉｔ　Ｓｕｂ　

Ｅｌｓｅ　

Ｃａｌｌ　ｇｅｎ（ｎ，ｍ＋１，ａ）　

ＥｎｄＩｆ　

Ｅｎｄ　Ｓｕｂ　

【例１０】用递归算法实现数组的从大到小排序。　

分析：要对数组ａ中所有元素进行排序，若能对前ｎ一１个元素进行　

排序（假设数组ａ中共有ｎ个元素），则在排序好的ｎ一１个元素中找到　

插人位置，再将ａ（ｎ）插入到该位置即可，同样的要对数组ａ中ｎ一１个元　

素进行排序，则先排序好ｎ一２个元素，如此下去，当ｎ＝１时，递归结束。　

可以定义一个递归子过程ｓｏｒｔ（ａＯ，ｎ），功能是实现数组ａ中前ｎ个元素　

排序。递归子过程如下：　

Ｐｒｉｖａｔｅ　Ｓｕｂ　ｓｏｒｔ（ａ０　Ａｓ　Ｉｎｔｅｇｅｒ，ｎ　Ａｓ　Ｉｎｔｅｇｅｒ）　

对数组前ｎ个元素进行排序　

Ｄｉｍ　ｉ　Ａｓ　Ｉｎｔｅｇｅｒ，ｐｏｓ　Ａｓ　Ｉｎｔｅｇｅｒ　

Ｄｉｍ　ｔｅｍｐ　Ａｓ　Ｉｎｔｅｇｅｒ　

Ｉｆｎ＞１　Ｔｈｅｎ　

Ｃａｌｌ　ｓｏｒｔ（ａ，ｎ一１）　

Ｆｏｒｉ＝１　Ｔｏｎ一１’找插入位置　

Ｉｆａ（ｎ１＞＝ａ（ｉ１　Ｔｈｅｎ　

Ｅｘｉｔ　Ｆｏｒ　

ＥｎｄＩｆ　

Ｎｅｘｔ　

ｐｏｓ　１　

ｔｅｍｐ　ａ（ｎ１　

Ｆｏｒｉ＝ｎ一１　Ｔｏｐｏｓ　Ｓｔｅｐ一１’循环移位　

ａ“＋１）：ａ（ｉ１　

Ｎｅｘｔｉ　

ａ（ｐｏｓ１＝ｔｅｍｐ　

ＥｎｄＩｆ　

Ｅｎｄ　Ｓｕｂ　

【例１　１】用递归算法实现判断一个正整数ｎ是否是素数。　

分析：可以定义一个递归函数ｐｒｉｍｅ（ｎ，ｍ），功能是判断ｍ是否能被　

正整数ｎ整除，若能则该正整数ｎ不是素数，ｍ从２开始，当ｍ＝ｎ时，递　

归结束，否则ｍ＋ｌ，再调用该递归函数。递归甬数如下：　

Ｐｒｉｖａｔｅ　Ｆｕｎｃｔｉｏｎ　ｐｒｉｍｅ（ＢｙＶａｌ　ｎ　Ａｓ　Ｉｎｔｅｇｅｒ，ｍ　Ａｓ　Ｉｎｔｅｇｅｒ）Ａｓ　Ｂｏｏｌｅａｎ　

’判断一个正整数ｎ是否是素数　

Ｉｆｍ＝ｎＴｈｅｎ　

ｐｒｉｍｅ＝Ｔｒｕｅ　

ＥｌｓｅＩｆｎ＜２ＯｒｎＭｏｄｉｎ＝０Ｔｈｅｎ　

ｐｒｉｍｅ＝Ｆａｌｓｅ　

Ｅｌｓｅ　

ｐｒｉｍｅ＝ｐｒｉｍｅ（ｎ，ｍ＋Ｉ）　

ＥｎｄＩｆ　

Ｅｎｄ　Ｆｕｎｃｔｉｏｎ　

６．小结　

递归算法不仅仅可以用于求解递归描述的问题，在其它很多问题　

中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可　

以使用递归思想来实现，递归的思维与人们的常规思维是相逆的　

用递归算法编写的程序虽然简洁明＿『，但递归算法解题的运行效　

率较低。在递归调用的过程中系统为每一层的返回点、局部量等开辟了　

栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算　

法设计程序。例如以上介绍的求斐波那契（Ｆｉｂｏｎａｃｃｉ）数列第ｎ项值的　

递归过程，调用一次要产生两个新的调用，递归次数呈指数增长，时间　

复杂度为Ｏ（２ｎ），若用非递归法求解，它的时间复杂度为Ｏ（ｎ）。　

参考文献　

［１］钟秀玉，陈月峰．基于递归与多线程的丢失文件查找设计［Ｊ］．计　

算机技术与发展，２０１０．　

［２］苗英恺递归程序的教学探讨［Ｉ］电脑知识与技术，２００８．　

［３］符策锐基于ｖＢ的递归模拟演示程序的实现［Ｊ］．电脑开发与应　

用、２００８