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

２０１　１年第６期　福建电脑　３５　

如何用递归方法进行程序设计　

黄欣阳，熊东平，谭敏生，阳小华　

（南华大学计算机科学与技术学院湖南衡阳４２１００５）　

【摘　要】：递归方法无论在计算机科学还是在数学中都是一个重要的问题求解方法，许多复杂问题使　

用递归方法能以简单易懂的形式求出问题的解。但初学者较难掌握递归方法，递归程序的设计往往成了程　

序设计中的一个难点。本文通过与递推方法比较给出了递归的概念、递归与递推的区别、使用递归方法求　

解的思路及关键点、保证递归方法求解正确性的条件，最后指出了递归程序设计的思路。　

【关键词】：递归程序；递归方法；程序设计　

在计算机科学和数学中．许多复杂问题的求解都　

可以用递归方法大大简化问题的复杂性．并以简单易　

懂的形式求出问题的解。但初学者较难理解递归方法，　

往往感到它深不可测．更不要说用它去解决新问题了。　

递归程序也成了程序设计教学中的一个难点。学生一　

＝５　｛４　｛３　｛２　｛ｌ　ａ【Ｏ】，）＞）　５　｛４　（３　｛２　｛１　１｝’｝）　

方面对复杂问题不容易理解．弄不清楚递归方法为何　

能得到正确的解：另一方面自己写程序时更是没有头　

这种从目的项ａｆ５１出发，根据表达式（１）变为不断　

绪。因此。本文试图帮助初学者解决以下几个问题：什　

求前一项，直到一个已知的项，再通过不断回代计算．　

么是递归方法？为何递归方法可以得到正确的解？保证　

得到后续项，直到解出目的项的计算过程，称为递归方　

　

递归方法求解正确的条件是什么？如何应用递归方法　

法。

进行问题求解及如何设计递归程序？　

第二种方法即递归方法能正确求解．是由于不断　

１．递归方法的概念以及保证递归方法求解正确性的条　进行问题转化直到一个已知项，然后回代。在回代过程　

件　

中以递推方法进行。因此，只要第一步的问题转化过程　

与递归方法非常相近的是递推方法。为了弄清两　

正确．那么递归方法的正确性无疑等价于递推方法的　

正确性。事实上，在这个例子中可以通过比较（２）和（３）来　

者的关系．我们先看例题ｌ。　

例１对于数列　知道　

（１）　总结例１，我们有如下概念：　

ａ［ｎ］＝ｎ　ａ【ｎ一１】　

当ｎ＝Ｏ时，有ａ【Ｄ］＝１，ｎ为自然数，请求出ａ［５］。　

递推方法：就是构造低阶规模（如规模为ｉ，一般ｉ＿　

分析：要求出ａ［５】，可以用如下两种方法：　ｏ】的问题，并求出其解，然后推导出问题规模为ｉ＋ｌ的　

第一种方法：根据公式ａ［ｎ】＝ｎ掌ａ［ｎ—ｊ】，按照从前向　问题以及其解．依次推到规模为ｎ的问题的解。简而言　

后的顺序依次求出ａ［１ｌ＝ｌ＊ａ［ｏｌ＝ｌ，ａ【２】＝２￥ａ【１】＝２，ａ【３】＝　

之．就是从已知的当前项出发，根据表达式向后推出下　

　

３　ａ【２］＝３　２＝６，ａ［４］＝４＊ａ［３１＝２４，ａ［５］＝５＊ａ［４］＝１２０。将计算　

项。直到求出目的项的方法。

过程写在一起有：　

递归方法：就是将规模为１１的问题，降阶成若干个　

一

ａ【５】＝１　１＂２　３　４　５＝１２０　（２）　

规模为ｎ一１或规模更小的问题．用相同的方法依次降　

这种从数列中的已知项ａ『０］开始，根据关系表达式　阶，直到问题规模可求，并求出该低阶规模问题的解。　

（１）推出下一项直到计算出目的项的过程，就是递推方　代入高阶问题中，直至求出规模为ｎ的问题的解。简而　

法。这是一种很常用的方法。　

言之．就是从未知的目的项出发。根据表达式转化为先　

第二种方法：与第一种方法的求解方向相反。第一　

求得未知的前一项。直到一个已知的项。再回代依次求　

步是问题转化：根据公式ａ［ｎ］＝ｎ＊ａ［ｎ－１］，有ａ［５】＝５　８【４】，　

得后一项的解，直到求出目的项的方法。　

然后有ａ［４】＝４＇ｌｃａ［３］，其次有ａ［３１＝３　ａ【２】，再次有ａ［２】＝　递归方法的优点：在计算过程中新的未知项都与　

２＊ａ［１１。最后有ａｆｌ１＝ｌ书ａ『ｏ１＝ｌ；第二步是以递推方法进　

目的项具有相同的性质。但由于新未知项的规模变小。　

行回代：将ａ【１］代入ａ【２】＝２｝ａ【１】中求出ａ【２】＝２，然后将ａ　因此容易将复杂的问题简化。　

『２］代入ａ［３］＝３＊ａ［２１ｔ９求出ａ［３１＝６，这样可以依次求出ａ　

递归方法的正确性取决于两点：一是降低问题规模的　

『４１：２４，ａ『５１＝１２０。将上述求解过程用一个式子来表示　

过程正确，即转换表达式正确无误；另一点是能够将问　

基金项目：湖南省２００９年研究生精品课程项目（ＫＣ２００９Ｂ０２１）：南华大学２００８年学位与研究生教育教学改革研究项目（２Ｏ０８０１）；　

南华大学２００９高等教育研究与改革项目（Ｏ￣Ｙ０２．＂２ｏｏｇＰＹｏ￣２）　

３６　福建　电脑　２０１　１年第６期　

题规模降低到一个可求解的低阶规模．我们称之为边　

界条件。使用递归方法求解时只要新问题与目的问题　

性质相同（这样才能保证可以用相同的方法降低问题　

规模）、规模越来越小并会到达边界，则该递归方法是　

由于ｈ（ｎ一１，ａ，ｃ，ｂ）和ｈ（ｎ，１，ｂ，ａ，ｃ）与原问题ｈ（ｎ，ａ，ｂ，ｃ）　

可以正确求解的。例如，ｆ３）式所示的递归求解过程中每　

次问题的规模减少１，则肯定可以到达边界规模Ｏ．因　

是相同性质的问题，但规模更小，并且问题的规模只降　

低１，边界条件１必然可达。于是可解得递归表达式。　

此．该递归方法能得到正确的解。　

２．递归方法的求解过程　

解．ｈｃｎ，　＝　后ｍ　最威　蝴　

从第一部分关于递归方法的描述可知．递归方法　

进行求解的关键步骤是在降低问题规模的同时保证问　

设计递归程序关键是求出递归表达式　

题性质的相同性。即求出合适的转换表达式（或转换函　

３．

递归方法求解实质上就是用相同的方法不断降低　

数），按见名知意原则，以下称为递归表达式。用递归方　

法可以对数值问题及非数值问题求解。通常，数值问题　

问题规模的过程。因此。在程序设计中可以根据递归表　

比较容易得到递归表达式．而非数值问题则需要经过　

达式通过程序对自身的调用，即递归调用来实现。需要　

注意的是：每次调用自身时，参数变小，即问题的规模　

形式化转换才能得到递归表达式。下面举例说明。　

变小．这一变化过程必须保证边界条件能够达到，否则　

例２用递归方法求ｎ的阶乘ｎ！。　

递归程序设计实际上是编程实　

分析：要求出ｎ！等于多少。如果能先求得ｆｎ—１）！等　

程序将无法结束。因此，

于多少，然后用ｎ半（ｎ一１）！，即可求得ｎ！；由于（ｎ一１）！与ｎ！　

现递归表达式　如果知道问题的递归表达式，编递归程　

属于相同性质的问题。规模变小了。因此，ｎ！－－ｒｌ＊（Ｅ［一１）！，　

序将变得非常容易。因为递归程序结构非常简单，只需　

即是递归表达式：当规模ｎ为０时。有０１＝１。该边界０　

要在分支结构中以较小的参数调用自身。并注意边界　

条件的处理即可。下面举例说明。　

是能达到的。　

解：ｎ！的递归表达式为：　

，ｚ　＝

｛　木　一　）’　

例３反向输出一个正整数（非数值问题）。　

分析：非数值问题通常无法象数值问题那样能直　

接得出递归表达式，但可以通过形式化转换来实现。假　

设整数ｎ＝ａｍ　ｌ…ａ　ａｏ，问题即变为要反向输出ａⅡｌ　ａ口卜１　

…ａ　ａ０。为了减少问题的规模，先输出ａｏ，还剩下ａｍ　ａ　

正如例５所示编程实现例题２是非常简单的事　

…ａｌ，这时要继续对ａｍ　ａⅡ卜１．．・ａ　进行反向输出，这意味　

着降低了问题的规模。如果令ｉｎｖＰｒｉｎｔ（ａ．ａｍ＿１．．－ａｌａｏ）表　

情。在例６中除了数值方式与非数值方式的转换存在　

示反向输出ａｍ　…ａ。ａｏ，则有如下递归表达式。边界条　

定的技巧外．总体来说是比较简单的。可见设计递归　

程序关键是求出问题的递归表达式。　

件ｍ＝０。即ｎ只有一位数。是可达的。　

一

４．结束语・　

综述以上内容可知。设计递归程序时关键要先设　

计出递归表达式。然后利用分支语句，通过递归调用来　

例４汉诺塔问题的规则为：ｆ１）一次只能移动一个　

实现　递归程序设计的难点是利用降低问题规模的方　

盘子；（２）大的盘子不能放在小的上面；（３）只能在三根针　

法设计出递归表达式。本文给出了递归方法的概念、及　

其与递推方法的区别、递归方法求解的思路、保证递归　

上移动。　

分析：用ｈｆｎ，ａ，ｂ，ｃ）表示任务：借助ｂ针将ｒ１个盘子　

方法求解正确性的条件及关键点。并指出了设计递归　

解：ｉｎｖＰｒｉｎｔ（　书　然后一～　

程序的思路　

从ａ针移到ｃ针。用降低规模法处理如下（见图１）：　

１、要解决原问题可先设法借助ｃ针将ａ针上的　

参考文献：　

ｎ一１个盘子移到ｂ针上，表示为ｈ（ｎ一１，ａ，ｃ，ｂ）。　

１】王慧娇，程序设计中递归函数教学问题探究Ｏ】，计算机教育，　

２、此时ａ针上剩下一个盘子，直接将它从ａ针移到　

【

ｃ

针上，表示为ｉｒｌｏｖｅ（ａ，ｃ）。　

２０１０，【１　６）　

３、再设法借助ａ针将ｂ针的ｎ一１个盘子移到Ｃ针　

上，表示为ｈ（ｎ一１，ｂ。ａ，ｃ）。　

［２］－５新。浅谈Ｃ语言函数的递归调用，科技信息，２０１０年第２７　

期　

［３】王岁花，马巍巍，Ｃ程序设计课程中递归教学过程设计，教育　

与教学研究，２００８（０４）