李偉

摘要：遞歸算法，結(jié)構(gòu)清晰，形式簡(jiǎn)單，符合人的思維習(xí)慣，容易被理解和閱讀，因而成為計(jì)算機(jī)程序設(shè)計(jì)中的一種重要方法，掌握它也有助于理解其他算法。該文闡述了遞歸算法的基本概念，成立的三個(gè)條件，直接和間接遞歸分類，通過(guò)實(shí)例深入分析遞歸在數(shù)據(jù)結(jié)構(gòu)、函數(shù)應(yīng)用和執(zhí)行過(guò)程中的應(yīng)用，以及將遞歸轉(zhuǎn)化為非遞歸的一般方法。

關(guān)鍵詞：遞歸；算法；消除；程序；應(yīng)用

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044（2012）30-7229-06

1 遞歸概念

1.1 概述

本文闡述了遞歸算法的基本定義、成立的必要條件和遞歸執(zhí)行的特點(diǎn)以及在實(shí)例中的具體應(yīng)用，讓學(xué)生能理解“遞歸是一種思想”這個(gè)概念。

在生活實(shí)際中，有些問(wèn)題是不能用數(shù)學(xué)公式解決的，需要通過(guò)其他方式、其他算法才能完成，其他重要算法有分治法、回朔法和動(dòng)態(tài)規(guī)劃等。分治法的三個(gè)步驟為：①分解：將當(dāng)前區(qū)間一分為二，求分裂點(diǎn)；②求解：遞歸地對(duì)兩個(gè)子區(qū)間進(jìn)行歸并排序；③組合：將已排序的兩個(gè)子區(qū)間歸并為一個(gè)有序的區(qū)間。其遞歸的終結(jié)條件：子區(qū)間長(zhǎng)度為1（一個(gè)記錄自然有序）。 回朔法的三個(gè)步驟：①搜索策略：符合遞歸算法，問(wèn)題解決可以化為子問(wèn)題，其子問(wèn)題算法和原問(wèn)題相同，只是數(shù)據(jù)增大或減少；②控制策略：避免不必要的窮舉搜索，遇到搜索失敗，從失敗點(diǎn)返回到上一點(diǎn)重新搜索；③數(shù)據(jù)結(jié)構(gòu)：用數(shù)組保存搜索過(guò)程中的狀態(tài)、路徑?？梢?，其他算法依然以遞歸算法為基礎(chǔ)，利用遞歸幫助解決問(wèn)題。

1.2 概念和成立條件

遞歸是設(shè)計(jì)和描述算法的一種有力的工具，它在復(fù)雜算法的描述中被經(jīng)常采用

1.2.1 概念

一個(gè)函數(shù)、過(guò)程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說(shuō)明內(nèi)部直接地或間接地出現(xiàn)有其本身的引用，或者是為了描述問(wèn)題的某一狀態(tài)，必須用到它的上一狀態(tài)，而描述上一狀態(tài)，又必須用到它的上一狀態(tài)………這種用自己定義自己的方法，稱之為遞歸或者是遞歸定義。

1.2.2 成立條件

應(yīng)滿足三點(diǎn)：①符合遞歸的描述：需要解決的問(wèn)題可以化為子問(wèn)題求解，而子問(wèn)題求解的方法與原問(wèn)題相同，只是數(shù)量增大或減少；②遞歸調(diào)用的次數(shù)是有限的；③必須有遞歸結(jié)束的條件。

1.3 遞歸分類

1.3.1 直接遞歸

程序設(shè)計(jì)中，過(guò)程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。子程序直接調(diào)用自己，這稱為直接遞歸；嵌套關(guān)系的子程序A和B，內(nèi)層的B調(diào)用外層的A，這是間接低歸；平級(jí)關(guān)系的子程序A和B，其中A調(diào)用了B，B調(diào)用了A，這也是間接遞歸，不過(guò)，這種間接遞歸用到了“超前引用”的規(guī)則。

2 遞歸本質(zhì)

2.1 函數(shù)遞歸調(diào)用機(jī)制

遞歸函數(shù)調(diào)用同樣遵守函數(shù)調(diào)用機(jī)制，當(dāng)函數(shù)調(diào)用自己時(shí)也要將函數(shù)狀態(tài)、返回地址、函數(shù)參數(shù)、局部變量壓入棧中進(jìn)行保存。

實(shí)際上函數(shù)被調(diào)用時(shí)執(zhí)行的代碼是函數(shù)的一個(gè)副本，與調(diào)用函數(shù)的代碼無(wú)關(guān)。當(dāng)一個(gè)函數(shù)被調(diào)用兩次，則函數(shù)就會(huì)有兩個(gè)副本在內(nèi)存中運(yùn)行，每個(gè)副本都有自己的?？臻g且與調(diào)用函數(shù)的棧空間不同，因此不會(huì)相互影響。這種調(diào)用機(jī)制決定了函數(shù)是可以遞歸調(diào)用的。

2.2 遞歸調(diào)用優(yōu)缺點(diǎn)

遞歸使一些復(fù)雜的問(wèn)題處理起來(lái)簡(jiǎn)單明了，尤其在學(xué)習(xí)算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)時(shí)更能體會(huì)到這一點(diǎn)。但是，遞歸在每一次執(zhí)行時(shí)都要為局部變量、返回地址分配?？臻g（對(duì)方法的每次遞歸調(diào)用都會(huì)生成新的局部變量和局部參數(shù)。假如遞歸層次太多的話，就會(huì)消耗太多的stack），這就降低了運(yùn)行效率，也限制了遞歸的深度。因此，在必要的時(shí)候可以只使用遞歸的思想來(lái)求解，而程序則轉(zhuǎn)用非遞歸的方式書寫。

3 遞歸的應(yīng)用

3.1 遞歸定義的數(shù)據(jù)結(jié)構(gòu)

3.1.1 二叉樹（定義）

二叉樹的遞歸定義二叉樹或者是一棵空樹，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是二叉樹。

下面介紹二叉樹的二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。我們先給出二叉鏈表鏈結(jié)點(diǎn)類型描述：

tnode為鏈表結(jié)點(diǎn)類型名，tlink為指向鏈結(jié)點(diǎn)的指針類型，elemtp為結(jié)點(diǎn)數(shù)據(jù)的類型.

那么如何根據(jù)輸入的數(shù)據(jù)建立二叉鏈表呢？設(shè)二叉樹結(jié)點(diǎn)數(shù)據(jù)類型為字符型，各結(jié)點(diǎn)數(shù)據(jù)按照二叉樹的數(shù)組表示方式存儲(chǔ)在字符串str中，字符串變量為s；string、整型變量為n；integer及指針為root；tlink，它們已經(jīng)在外部說(shuō)明，則二叉鏈表的建立過(guò)程可表示為procedure build（str；string）；其功能為根據(jù)字符串str的內(nèi)容建立二叉樹的二叉鏈表，并讓root指向這個(gè)二叉鏈表。其處理過(guò)程為：以1為參數(shù)調(diào)用遞歸子函數(shù)function build0（i；integer）：tilink完成二叉鏈表的建立，并讓root指向該鏈表。遞歸子函數(shù)function build0（i；integer）：tilink的功能為：以字符串str的第i個(gè)元素為二叉樹的根結(jié)點(diǎn)遞歸的建立二叉鏈表，并返回指向該鏈表的指針。其處理過(guò)程為：

若i小于字符串的長(zhǎng)度，且字符串的第i個(gè)元素為非空格符，則創(chuàng)建一個(gè)鏈結(jié)點(diǎn)，在其數(shù)據(jù)域中存放字符串的第i個(gè)元素；

以下是程序清單：

3.2 遞歸定義函數(shù)

3.2.1 階乘

《例》 用遞歸計(jì)算n！

3.3 遞歸定義過(guò)程

3.3.1 樹的遍歷

根據(jù)二叉樹的遞歸定義，一棵非空二叉樹由根結(jié)點(diǎn)、左子樹和右子樹組成，因此遍歷一棵非空二叉樹的問(wèn)題可分解為三個(gè)問(wèn)題，即訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹和遍歷右子樹。顯然，遍歷左、右子樹的問(wèn)題仍然遍歷二叉樹的問(wèn)題，所以二叉樹的這三種遍歷方式可以用遞歸算法實(shí)現(xiàn)。

我們以遍歷方案DLR（因?yàn)樵L問(wèn)根結(jié)點(diǎn)的操作在遍歷左、右子樹之前，故稱之為前序遍歷或先根遍歷）為例，若二叉樹不為空，則

訪問(wèn)根結(jié)點(diǎn)；

以前序遍歷方式遍歷根結(jié)點(diǎn)的左子樹；

以前序遍歷方式遍歷根結(jié)點(diǎn)的右子樹；

設(shè)p為指向二叉樹根結(jié)點(diǎn)的指針，則前序遍歷過(guò)程可表示為 procedure preorder0（p：tlink），

其功能為對(duì)p所指的二叉樹進(jìn)行前序遍歷，輸出前序遍歷的結(jié)點(diǎn)序列，其處理過(guò)程為：

若p非空，則

① 顯示p所指的結(jié)點(diǎn)數(shù)據(jù)；

② 前序遍歷p所指的左子樹；

③ 前序遍歷p所指的右子樹；

以下為程序清單：

4 遞歸消除

為了提高算法的程序運(yùn)行速度及減少占用內(nèi)存空間，和透切理解遞歸遞歸機(jī)制（這種理解是熟練掌握遞歸程序技能的必要前提），我們接下來(lái)探討遞歸消除。

遞歸消除，就是將一個(gè)遞歸算法轉(zhuǎn)化為等價(jià)的非遞歸算法。遞歸消除一般有兩種方法：

一、基于循環(huán)的遞歸消除。不是用工作棧作為工作機(jī)制，而是利用循環(huán)算法，即采用遞推算法，這樣可避免重復(fù)計(jì)算，提高了效率，如下面所要講的斐波那契數(shù)列。

二、基于棧的遞歸消除。大部分遞歸問(wèn)題無(wú)法用遞推算法來(lái)消除，在這種情況下，引用一個(gè)工作棧作為控制機(jī)構(gòu)以消除遞歸算法，其原理是：利用數(shù)組模擬工作棧，保存“返回位置”，以實(shí)現(xiàn)過(guò)程調(diào)用和返回控制。

4.1 利用棧消除遞歸

我們以Hanoi（河內(nèi)/漢諾）塔問(wèn)題為例，看如何利用數(shù)組建立的棧來(lái)消除遞歸的。

例： Hanoi（河內(nèi)/漢諾）塔問(wèn)題

有n個(gè)圓盤，依半徑大?。ò霃蕉疾煌?，自下而上套在A柱上，每次只允許移動(dòng)最上面的一個(gè)盤子到另外的柱子上去（除A柱子外，還有B柱子和C柱子，開始時(shí)這兩個(gè)柱子上沒盤子），但絕不允許發(fā)生柱子上出現(xiàn)大盤子在上，小盤子在下的情況，現(xiàn)在要求設(shè)計(jì)將A柱子上n個(gè)盤子搬到C柱子上去的方法。

問(wèn)題解析：本題是典型的遞歸程序設(shè)計(jì)題。

3） 當(dāng)n=3時(shí)，需要將前2個(gè)盤子移到B柱子，再將第三個(gè)盤子移到C柱子，然后將2個(gè)在B柱子上的盤子借助A柱子移動(dòng)到C柱子，因此可以得到移動(dòng)盤子的一般規(guī)律：

a.先將n-1個(gè)盤子從A 柱子移動(dòng)到B柱子，C柱子為中間柱子；

b.將第n個(gè)盤子從A柱子移動(dòng)到C柱子；

c.再將n-1個(gè)盤子從B柱子移動(dòng)到C柱子，A柱子為中間柱子。

其程序如下：

為了保證遞歸調(diào)用正確執(zhí)行，系統(tǒng)要建立一個(gè)遞歸調(diào)用工作棧，為各層次的調(diào)用分配數(shù)據(jù)存儲(chǔ)區(qū)。每一層遞歸調(diào)用所需要的信息構(gòu)成一個(gè)工作記錄，其中包括所有實(shí)參指針，所有局部變量以及返回上一層的地址。每進(jìn)入一層遞歸調(diào)用，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。每退出一層遞歸調(diào)用，就從棧頂彈出一個(gè)工作記錄。

4.2 利用循環(huán)消除遞歸

例：用遞歸的方法求斐波那契數(shù)列中的第n個(gè)數(shù)

程序清單如下：

這樣，就可以將遞歸程序轉(zhuǎn)化為非遞歸的程序了。

斐波那契數(shù)列用非遞歸算法求解的程序如下：

5 總結(jié)

總的說(shuō)來(lái)，遞歸是一種非常重要的，應(yīng)用很廣泛的程序設(shè)計(jì)方法。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。用遞歸思想寫出的程序往往十分

簡(jiǎn)潔易懂，結(jié)構(gòu)清晰，形式簡(jiǎn)單，符合人們的日常思維習(xí)慣，容易被理解和閱讀。其他算法，如分治法，有許多是源于遞歸思想，或是由遞歸分解+合并處理，還有如回朔法和動(dòng)態(tài)規(guī)劃問(wèn)題 ，動(dòng)態(tài)規(guī)劃的子問(wèn)題重疊性質(zhì)與遞歸有某種相似之處，遞歸+動(dòng)態(tài)修改查表是一種不錯(cuò)的建立動(dòng)態(tài)規(guī)劃模型的方法。可見，掌握遞歸算法、理解遞歸思想對(duì)于學(xué)習(xí)其他程序設(shè)計(jì)方法也是很有幫助的。

遞歸使一些復(fù)雜的問(wèn)題處理起來(lái)簡(jiǎn)單明了，尤其在學(xué)習(xí)算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)時(shí)更能體會(huì)到這一點(diǎn)。但是，遞歸在每一次執(zhí)行時(shí)都要為局部變量、返回地址分配?？臻g，假如遞歸層次太多的話，就會(huì)消耗太多的stack，對(duì)內(nèi)存要求很高，這就降低了程序運(yùn)行效率，也限制了遞歸的層次和深度。因此，在必要的時(shí)候可以只使用遞歸的思想來(lái)求解，而程序則轉(zhuǎn)用非遞歸的方式書寫。

參考文獻(xiàn)：

[1] 吳再陵，高建軍.全國(guó)青少年信息學(xué)培訓(xùn)教材[M].南京： 南京大學(xué)出版社，2002.

[2] 朱振元，朱承.數(shù)據(jù)結(jié)構(gòu)教程--面向?qū)ο髮?shí)現(xiàn)方法[M].西安：西安電子科技大學(xué)出版社，2000.

[3] 鄧毅.Delphi 4.0入門與提高[M].北京：清華大學(xué)出版社，1999.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1992.

[5] 李大友.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：機(jī)械工業(yè)出版社，1996.

[6] 旺曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社，2004.