倪錦園 張建勛

摘? 要：遞歸思想是算法分析設(shè)計(jì)中最重要的思想之一，遞歸算法應(yīng)用十分廣泛，借助遞歸算法可以把一些較為復(fù)雜的問題簡(jiǎn)潔地表示出來。該文重點(diǎn)介紹了遞歸算法的概念和三個(gè)特點(diǎn)，通過計(jì)算機(jī)博弈樹詳細(xì)說明了遞歸算法在數(shù)據(jù)結(jié)構(gòu)中樹的應(yīng)用，使用點(diǎn)格棋博弈過程落子的不同狀況系統(tǒng)地介紹了遞歸算法在圖的應(yīng)用，并通過對(duì)照實(shí)驗(yàn)重點(diǎn)分析了遞歸算法和遞歸算法非遞歸化的執(zhí)行效率。

關(guān)鍵詞：遞歸;算法;非遞歸化;效率

中圖分類號(hào)：TP301.6? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）20-0146-04

Application and Analysis of Recursive Algorithm

NI Jinyuan，ZHANG Jianxun

（College of Computer Science and Engineering，Chongqing University of Technology，Chongqing? 400054，China）

Abstract：Recursive thought is one of the most important thoughts in algorithm analysis and design. Recursive algorithms are widely used. With the help of recursive algorithms，some more complex problems can be expressed concisely. This article focuses on the concept and three characteristics of the recursive algorithm. This paper describes the application of recursive algorithm in data structure tree in detail through computer game tree，systematically introduces the application of recursive algorithm in graph by using different situations in the process of point chess game，and analyzes the execution efficiency of recursive algorithm and recursive algorithm non recursive through contrast experiments.

Keywords：recursion;algorithm;non-recursive;efficiency

0? 引? 言

在日常編程過程中，通過使用遞歸算法可以簡(jiǎn)化大量的代碼，同時(shí)也讓代碼的可維護(hù)性變得更好。筆者通過將遞歸算法應(yīng)用到點(diǎn)格棋博弈系統(tǒng)中，完成了整個(gè)博弈系統(tǒng)搜索引擎和測(cè)試引擎的實(shí)現(xiàn)，并在全國(guó)計(jì)算機(jī)博弈大賽上取得了較好的成績(jī)。遞歸算法是程序開發(fā)過程中一種重要的方法，通過遞歸算法可以讓程序的結(jié)構(gòu)性更加清晰，可以把一些不容易解決的問題處理好，而且解題思路更為明確，不容易產(chǎn)生歧義。在算法分析與設(shè)計(jì)課程中很多問題都用到了遞歸的方法，比如漢諾塔問題、整數(shù)劃分問題、求階層問題等。遞歸算法的設(shè)計(jì)還是比較復(fù)雜的，要設(shè)計(jì)一個(gè)好的遞歸算法來解決以上問題就要注意三個(gè)關(guān)鍵點(diǎn)：首先分析問題的定義，找到合理的解決辦法就需要找出算法的遞歸公式，設(shè)計(jì)一個(gè)好的遞歸公式是解決問題的關(guān)鍵;其次設(shè)計(jì)一個(gè)遞歸的邊界條件也就是遞歸的終止條件是十分重要的;最后的關(guān)鍵是要不斷地縮小問題的規(guī)模，記錄遞歸時(shí)參數(shù)傳遞的過程[1，2]。

1? 遞歸算法概述

1.1? 遞歸算法概念

遞歸算法是指算法本身可以直接或者間接的調(diào)用自己，將一個(gè)較為復(fù)雜的問題分解為規(guī)模較小的子問題，算法在執(zhí)行過程中重復(fù)不斷地實(shí)現(xiàn)自我調(diào)用的過程。在不斷遞歸調(diào)用的過程中，只有達(dá)到遞歸邊界的臨界值時(shí)，才會(huì)跳出遞歸循環(huán)，遞歸算法會(huì)從后往前依次逆序返回，就是把每一層遞歸調(diào)用的值放入一個(gè)棧中，算法執(zhí)行到遞歸的出口時(shí)，就進(jìn)行出棧的操作，從最后一層遞歸調(diào)用的值逆序返回，返回到第一個(gè)入棧操作，這樣就完成了整個(gè)遞歸算法的操作[3-5]。

1.2? 遞歸算法特點(diǎn)

遞歸算法在程序設(shè)計(jì)中是十分重要的方法，幫助解決了許多較為復(fù)雜的問題，遞歸算法極大地簡(jiǎn)化了程序開發(fā)的工作量，使程序的結(jié)構(gòu)性也較為清晰，可讀性更高，同時(shí)讓問題更容易被理解和接納。遞歸算法主要有下面三個(gè)特點(diǎn)。

1.2.1? 設(shè)計(jì)遞歸公式

遞歸算法直接或間接的調(diào)用自己本身，將一個(gè)較為復(fù)雜的問題化解為一個(gè)或多個(gè)子問題來求解，同時(shí)子問題與被分解的問題有同樣的算法，舉個(gè)簡(jiǎn)單的例子遞歸求n個(gè)元素的和，可以寫出公式f（n）=n+f（n-1）進(jìn)行遞歸迭代，還有比較經(jīng)典的漢諾塔問題，就是以c柱為支撐柱，將a柱上n-1的盤子移動(dòng)到b柱上的公式是f（n-1，a，c，b），移動(dòng)的盤子打印輸出move（n，a，c）;以a柱為支撐柱，將b柱上的盤子移動(dòng)到c柱的公式是f（n-1，b，a，c）。每一次迭代遞歸的時(shí)候，問題規(guī)模都在縮小，同時(shí)上一次的輸出成為了下一次迭代遞歸的輸入。

1.2.2? 遞歸算法的邊界條件

邊界條件就是遞歸的出口。遞歸算法不是無窮無盡的，當(dāng)程序遞歸到最后一層時(shí)，就要返回輸出。由于每一層遞歸都會(huì)使問題規(guī)模不斷縮小，所以每一次遞歸都會(huì)越來越趨近于終止條件，直到達(dá)到終止的條件，返回臨界值。例如遞歸求階乘問題f（n）=n·f（n-1），遞歸的終止條件當(dāng)n=1時(shí)，如果沒有遞歸的邊界條件，此時(shí)程序是無限循環(huán)的，沒有輸出結(jié)果。遞歸算法的邊界條件有的時(shí)候也不止一個(gè)，在整數(shù)劃分問題里面，要分別討論最大化分?jǐn)?shù)值和被劃分的整數(shù)值大小關(guān)系，此時(shí)遞歸邊界條件也有多個(gè)的。

1.2.3? 縮小問題的規(guī)模

遞歸過程中需要不斷地減小問題地規(guī)模，而且遞歸算法是在直接或間接地調(diào)用自身，所以遞歸時(shí)參數(shù)傳遞的過程中，要逐步減少或者增加參數(shù)值向遞歸算法的邊界條件靠攏，控制了遞歸方向才能控制遞歸算法。例如斐波那契數(shù)，F(xiàn)（0）=

0，F(xiàn)（1）=1，F(xiàn)（n）=F（n-1）+F（n-2），每一次遞歸調(diào)用的過程中，問題的規(guī)模都在不斷地縮小，直到問題規(guī)?？s小到遞歸出口的時(shí)候，就達(dá)到了遞歸輸出的條件。

2? 遞歸算法的應(yīng)用

2.1? 遞歸算法在樹中的應(yīng)用

樹是一種基本的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合[6，7]。樹里面每一個(gè)節(jié)點(diǎn)具有相同的數(shù)據(jù)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素直接的關(guān)系是“一對(duì)多”，所以很多有關(guān)樹的問題通常用到遞歸的思想。本文提到的計(jì)算機(jī)博弈樹也運(yùn)用了遞歸的思想，博弈樹的每個(gè)節(jié)點(diǎn)代表一個(gè)落子后的一個(gè)局面，每個(gè)局面都是遞歸產(chǎn)生的，而且是通過深度優(yōu)先遍歷，一層一層往下延伸，每一個(gè)局面生成的過程都會(huì)在上一層局面中進(jìn)行遞歸搜索，搜索到上一層局面沒有落子的位置時(shí)，就會(huì)產(chǎn)生新的局面，它的根節(jié)點(diǎn)也就是現(xiàn)在所處的局面，也成為當(dāng)前局面。因?yàn)殡p方落子的不確定性，博弈樹的遞歸發(fā)展也是不一樣的，但總是根據(jù)棋盤信息進(jìn)行模擬遞歸展開的，然后逐漸地就可以形成一個(gè)樹形結(jié)構(gòu)。以井字棋為基礎(chǔ)的博弈樹的示意圖如圖1所示。在圖1中，博弈樹主要是通過井字棋來建立的，表現(xiàn)一局井字棋游戲博弈樹的全部過程，整顆博弈樹構(gòu)建的過程是通過遞歸產(chǎn)生的，井字棋游戲是由雙方輪流著邊的棋類博弈游戲。

在圖1中的根節(jié)點(diǎn)表示一個(gè)空棋盤，根節(jié)點(diǎn)下面的三個(gè)子節(jié)點(diǎn)中的×表示一號(hào)玩家可以走的位置，在接下面的一層節(jié)點(diǎn)中的○表示的是二號(hào)玩家可以走的位置，二號(hào)玩家的落子位置完全要根據(jù)一號(hào)玩家的落子位置，通過遞歸搜索確定此位置未被一號(hào)玩家占領(lǐng)后，才能產(chǎn)生，因此，在棋局的不斷進(jìn)行中，博弈樹在每一層遞歸的過程中也會(huì)越來越大。

2.2? 遞歸算法在圖中的應(yīng)用

遞歸算法在圖中的應(yīng)用是用來描述點(diǎn)格棋先后落子位置順序的算法，圖是由頂點(diǎn)V集和邊E集構(gòu)成，因此圖可以表示成G=（V，E），圖是一種基本的數(shù)據(jù)結(jié)構(gòu)，在很多有關(guān)于圖的應(yīng)用中都用到了遞歸算法。點(diǎn)格棋博弈的過程中用到了有關(guān)于圖的遞歸算法，點(diǎn)格棋是中國(guó)計(jì)算機(jī)博弈大賽的競(jìng)賽項(xiàng)目之一，博弈雙方輪流將兩個(gè)相鄰的點(diǎn)連接成一條邊，邊屬于雙方共有，只討論格子的所屬，當(dāng)某一個(gè)格子的四條邊都被連成線時(shí)，占領(lǐng)最后一條邊的玩家擁有這個(gè)格子，占領(lǐng)格子后有一個(gè)獎(jiǎng)勵(lì)邊，該玩家必須再下一步。根據(jù)這個(gè)競(jìng)賽規(guī)則，可以用遞歸算法的思想來設(shè)計(jì)點(diǎn)格棋博弈雙方落子的流程圖，點(diǎn)格棋遞歸落子流程圖如圖2所示。

博弈雙方在落子的過程中選擇先后手遞歸進(jìn)行落子，若電腦先手，電腦進(jìn)行落子，然后條件判斷當(dāng)前落子是否達(dá)到占格的條件，若沒有占格，則由玩家進(jìn)行落子，若都沒有達(dá)到占格的條件，就遞歸到另一方進(jìn)行落子。若任意一方達(dá)到占格的條件，則判斷當(dāng)前占格數(shù)量是否超過所有格子的一半，若超過一半就跳出循環(huán)，若未超過一半就又遞歸調(diào)用自身落子的函數(shù)，在點(diǎn)格棋雙方博弈的過程中，不斷地遞歸調(diào)用落子的函數(shù)。

3? 遞歸算法與非遞歸化

對(duì)比遞歸算法和遞歸算法的非遞歸化時(shí)，下面就實(shí)際操作一個(gè)案例來分析各自執(zhí)行效率，完成任務(wù)問題：在一個(gè)雙線程的電腦上，有n個(gè)任務(wù)將要完成，完成一個(gè)任務(wù)都將占用一個(gè)線程。一個(gè)線程完成任務(wù)的方法有兩種，可以一次完成一個(gè)任務(wù)，也可以一次完成兩個(gè)任務(wù)。需要完成n個(gè)任務(wù)，一共有多少種執(zhí)行的方法。

用遞歸思想的具體思路：

（1）當(dāng)只有一個(gè)任務(wù)的時(shí)候，有一種完成任務(wù)的方法。

（2）當(dāng)只有兩個(gè)任務(wù)的時(shí)候，有四種完成任務(wù)的方法：分別是兩個(gè)任務(wù)分別占用兩個(gè)不同的線程，有兩種;一個(gè)線程一次性完成兩個(gè)任務(wù)，有兩種。

完成任務(wù)問題的算法實(shí)現(xiàn)包括了遞歸算法和非遞歸算法。

3.1? 遞歸算法

遞歸算法在程序執(zhí)行的過程中，不斷地直接或間接的進(jìn)行自我的調(diào)用，遞歸調(diào)用的過程中，系統(tǒng)會(huì)為每一層調(diào)用開辟新的棧來存儲(chǔ)信息，直到程序執(zhí)行到邊界條件的時(shí)候，才完成自我調(diào)用，然后逆序返回棧中每一層存儲(chǔ)的數(shù)據(jù)，直到把棧里面的數(shù)據(jù)全部返回，到此就完成了整個(gè)遞歸算法的執(zhí)行。在解決很多問題的時(shí)候，遞歸算法是十分有效的，它對(duì)問題的描述清楚易懂，便于對(duì)整個(gè)程序的編寫和調(diào)試。但是遞歸的過程中需要用到系統(tǒng)的堆棧，會(huì)消耗更多的空間資源，當(dāng)遞歸深度過于龐大的時(shí)候，程序有可能會(huì)出現(xiàn)異常死機(jī)的現(xiàn)象[8]。完成任務(wù)問題的遞歸算法代碼為：

#include

#include

#include

int Digui（int n）

{

if（n==1）? ? ? ? //只有一個(gè)任務(wù)時(shí)，有一種方法

return 1;

if（n==2）

return 4;? ?//有兩個(gè)任務(wù)時(shí)，有四種方法

return Digui（n - 1）+Digui（n - 2）;

}

int main（）

{

long int begin，end;

time（&begin）;

int n;

printf（"請(qǐng)輸入任務(wù)量：＼n"）;

scanf（"%d"，&n）;

printf（"任務(wù)完成的方法一共有：＼n"）;

printf（"%d＼n"， Digui（n））;

time（&end）;

printf（"程序執(zhí)行過程中的時(shí)間：＼n"）;

printf（"%d＼n"，end-begin）;

return 0;

}

3.2? 非遞歸算法

非遞歸算法執(zhí)行效率更高，運(yùn)行時(shí)間會(huì)隨著程序循環(huán)的次數(shù)增加而增加，沒有其他額外調(diào)用的開銷，非遞歸算法比遞歸方法更快，因?yàn)榉沁f歸方法避免了一些列函數(shù)調(diào)用和返回中涉及的額外開銷，在性能上更具有優(yōu)勢(shì)[9，10]。完成任務(wù)問題的非遞歸算法代碼為：

#include

#include

#include

int main（）

{

long int begin，end;

time（&begin）;

int x1=1，x2=4;

int n，x;

printf（"請(qǐng)輸入任務(wù)量：＼n"）;

scanf（"%d＼n"，&n）;

for（int i=3;i<=n;i++）

{

x=x1+x2;

x1=x2;

x2=x;

}

printf（"任務(wù)完成的方法一共有：＼n"）;

printf（"%d＼n"，x）;

time（&end）;

printf（"程序執(zhí)行過程中的時(shí)間：＼n"）;

printf（"%d＼n"，end-begin）;

return 0;

}

對(duì)照兩個(gè)實(shí)驗(yàn)可以發(fā)現(xiàn)：遞歸算法程序結(jié)構(gòu)簡(jiǎn)單，易讀性更高，程序調(diào)試也很方便，但是遞歸算法依靠棧來實(shí)現(xiàn)操作的，不斷地在系統(tǒng)內(nèi)部進(jìn)出棧，占用了大量的時(shí)間和空間，消耗了更多的計(jì)算機(jī)資源，上述遞歸算法的時(shí)間復(fù)雜度O（2n），其中n代表問題的規(guī)模。而非遞歸算法程序結(jié)構(gòu)較為復(fù)雜，在編寫和調(diào)試程序時(shí)，會(huì)花更多的時(shí)間，但因?yàn)榉沁f歸算法依賴于調(diào)用其他函數(shù)進(jìn)行進(jìn)出棧操作，相對(duì)于遞歸算法來說，消耗了較少的時(shí)間和空間。上述非遞歸算法的時(shí)間復(fù)雜度O（n）。

當(dāng)輸入任務(wù)量為20時(shí)，遞歸算法程序執(zhí)行時(shí)間不到1秒，非遞歸算法程序執(zhí)行時(shí)間也不到1秒，由此看來，任務(wù)量較小的時(shí)候，遞歸算法和非遞歸算法執(zhí)行的時(shí)間幾乎相同。當(dāng)輸入的任務(wù)量為40時(shí)，遞歸算法程序執(zhí)行時(shí)間為6秒，非遞歸算法程序執(zhí)行時(shí)間只有2秒，當(dāng)任務(wù)量較大的時(shí)候，遞歸算法明顯比非遞歸算法更慢。

4? 結(jié)? 論

全文對(duì)遞歸算法進(jìn)行分析，通過對(duì)遞歸算法的概念和特點(diǎn)進(jìn)行闡述，然后分別介紹了遞歸算法在樹、圖中的應(yīng)用，接著做了遞歸算法和非遞歸算法的對(duì)照實(shí)驗(yàn)，發(fā)現(xiàn)當(dāng)數(shù)據(jù)量不夠大時(shí)，遞歸算法和非遞歸算法的時(shí)間效率幾乎相同，當(dāng)數(shù)據(jù)量越來越大時(shí)，遞歸算法的執(zhí)行時(shí)間相比非遞歸算法來說就越來越慢，遞歸算法的時(shí)間復(fù)雜度也要大于非遞歸算法的時(shí)間復(fù)雜度，所以遞歸算法的執(zhí)行效率更低。因此在實(shí)際計(jì)算中，還是建議不要大規(guī)模使用遞歸算法。

參考文獻(xiàn)：

[1] 宋衛(wèi)紅.數(shù)據(jù)結(jié)構(gòu)中遞歸算法的教學(xué)研究 [J].現(xiàn)代信息科技，2020，4（13）：188-190+193.

[2] 張耀民.遞歸算法在程序設(shè)計(jì)中的應(yīng)用與分析 [J].電子測(cè)試，2013（13）：1-2.

[3] 楊嬌.遞歸思想及其算法設(shè)計(jì)的探討 [J].數(shù)字通信世界，2018（11）：109+204.

[4] 晏素芹.遞歸算法的教學(xué)方法探討——以C程序設(shè)計(jì)為例 [J].福建電腦，2018，34（8）：170-171.

[5] 周世杰.從計(jì)算思維的視角辨析算法中的遞歸與迭代 [J].中國(guó)信息技術(shù)教育，2020（9）：53-55.

[6] 劉曉靜.“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)改革與實(shí)踐 [J].微型電腦應(yīng)用，2015，31（11）：14-17+2.

[7] 張安勤，田秀霞，張挺.數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)結(jié)構(gòu)課程案例設(shè)計(jì)研究與實(shí)踐 [J].軟件工程，2020，23（4）：54-56.

[8] 王愛法，楊梅梅，福春霞.二叉樹及其遍歷算法的應(yīng)用 [J].重慶理工大學(xué)學(xué)報(bào)（自然科學(xué)），2018，32（11）：194-198.

[9] 肖紅德.漢諾塔問題遞歸算法與非遞歸算法比較 [J].軟件導(dǎo)刊，2018，17（8）：118-120.

[10] 詹澤梅.數(shù)據(jù)結(jié)構(gòu)中遍歷操作的非遞歸算法 [J].電腦知識(shí)與技術(shù)，2017，13（28）：40-42.

作者簡(jiǎn)介：倪錦園（1996—），男，漢族，重慶九龍坡人，碩士，研究方向：數(shù)字圖像處理與分析;張建勛（1971—），男，漢族，四川樂山人，教授，碩士生導(dǎo)師，CCF專業(yè)會(huì)員，博士，研究方向：數(shù)字圖像處理與分析、實(shí)時(shí)計(jì)算機(jī)圖形學(xué)。