李青柏

摘 要：數(shù)學(xué)在計(jì)算機(jī)程序設(shè)計(jì)中具有重要地位，通過數(shù)學(xué)思維、數(shù)學(xué)計(jì)算方法、數(shù)學(xué)模型的建立等將實(shí)際問題不斷抽象化，并設(shè)計(jì)相應(yīng)的計(jì)算機(jī)程序獲得問題的解，是一個(gè)簡潔、高效的設(shè)計(jì)過程，程序員可以將實(shí)際問題通過各種科學(xué)計(jì)算轉(zhuǎn)換為程序，在這一過程中，數(shù)學(xué)算法的合理應(yīng)用具有重要意義。文章以遞歸算法在計(jì)算機(jī)程序設(shè)計(jì)中的運(yùn)用作為基礎(chǔ)，探討數(shù)學(xué)計(jì)算在計(jì)算機(jī)程序設(shè)計(jì)中的重要作用。

關(guān)鍵詞：遞歸算法；數(shù)學(xué)；計(jì)算機(jī)程序設(shè)計(jì)

遞歸是函數(shù)、過程、子程序運(yùn)行過程中對自身行為的一種直接或間接調(diào)用，是一個(gè)重要的計(jì)算機(jī)科學(xué)概念，一般將采用了遞歸思想的算法稱為遞歸算法。遞歸方法是一種有效的程序設(shè)計(jì)方法，通過遞歸算法編寫程序能夠提高程序的簡潔性與清晰度。在程序設(shè)計(jì)中運(yùn)用遞歸能夠定義句法，而在數(shù)據(jù)結(jié)構(gòu)中則能夠用遞歸解決表或樹形結(jié)構(gòu)排列問題。運(yùn)用遞歸算法設(shè)計(jì)計(jì)算機(jī)程序，也是運(yùn)用數(shù)據(jù)思想構(gòu)造算法與設(shè)計(jì)程序的一個(gè)重要體現(xiàn)[1]。

1 遞歸算法在計(jì)算機(jī)程序設(shè)計(jì)中的運(yùn)用設(shè)計(jì)

1.1 遞算法設(shè)計(jì)的一般步驟

遞歸算法設(shè)計(jì)時(shí)，主要通過3個(gè)步驟完成：（1）分析問題，理解題意，設(shè)計(jì)遞歸關(guān)系表達(dá)式。（2）設(shè)計(jì)遞歸終止表達(dá)式，有效控制遞歸循環(huán)，使遞歸結(jié)束時(shí)能夠獲得原問題的解。（3）明確形式參數(shù)，設(shè)計(jì)遞歸函數(shù)[2]。

1.2 設(shè)計(jì)遞歸關(guān)系式

這一步是將一個(gè)問題轉(zhuǎn)換為若干個(gè)子問題進(jìn)行求解，子問題與原問題需要有相同解法，一些問題可以通過一個(gè)關(guān)系式求解，如FIBONACCI數(shù)列，可以運(yùn)用f（n）=f（n-1）+f（n+2）迭代處理。一些問題則需要運(yùn)用循環(huán)求解，如將一個(gè)十進(jìn)制數(shù)n轉(zhuǎn)化成二進(jìn)制數(shù)進(jìn)行輸出，從而執(zhí)行下一個(gè)循環(huán)，第一步，先輸出為n的2的余數(shù)即n%2；第二步，將n右移一位數(shù)或直接求解n/2，當(dāng)結(jié)束為0時(shí)表示輸出后即可結(jié)束遞歸，當(dāng)結(jié)果不為0時(shí)，需要繼續(xù)執(zhí)行上一步驟。遞歸調(diào)用語言d2b（n/2）必須放在語言count<

1.3 設(shè)計(jì)遞歸終止條件

最后一級遞歸調(diào)用時(shí)，必須確保無法再次進(jìn)行遞歸，有明確的遞歸函數(shù)返回值，避免無窮遞歸。遞歸調(diào)用普遍要受條件控制，調(diào)用過程中，調(diào)用函數(shù)對應(yīng)的參數(shù)修改有一定規(guī)律，每一次遞歸均要使遞歸能夠趨于結(jié)束，能夠進(jìn)一步滿足終止條件，滿足返回值，進(jìn)而結(jié)束遞歸，之后再從原路徑逐層進(jìn)行返回，從而獲得原問題的解。問題不同時(shí)，遞歸終止條件也不同，可能對應(yīng)一個(gè)或多個(gè)終止條件。如，自然數(shù)階乘問題的求解，僅對應(yīng)一條調(diào)用程序，遞歸終止條件僅有一個(gè)。一般情況下，階乘都屬于自然數(shù)范圍，任意自然數(shù)階乘可以表述為：n！=1×2×3×…n，遞歸表述為：0！=1，1！=1，…n！=n×（n-1）！。遞歸求解n！時(shí)，就需要滿足兩個(gè)關(guān)鍵問題，即遞歸終止條件，確保0！與1！能夠直接求解；遞歸表達(dá)式，求解n！時(shí)可以直接轉(zhuǎn)換為求解（n-1）！，n！的遞歸函數(shù)就可以采用如下語句設(shè)計(jì)：

采用精度為24位的long long作為函數(shù)返回值，僅能夠計(jì)算到20！，階乘范圍超過20時(shí)，會超出long long數(shù)據(jù)的顯示范圍，就需要采用double作為函數(shù)返回類型。

當(dāng)遞歸過程或函數(shù)不止對應(yīng)一條自身調(diào)用程序時(shí)，就會出現(xiàn)多個(gè)遞歸終止條件。如爬樓梯問題的分析，通過遞歸算法解決時(shí)，遞推至一定程度后，會面臨剩余樓梯數(shù)量不同，解法不同的問題，那么就會出現(xiàn)多個(gè)遞歸終止條件。

1.4 確定參數(shù)，設(shè)計(jì)遞歸函數(shù)

遞歸函數(shù)需要多次自我調(diào)用，子問題規(guī)模足夠小時(shí)，需要直接給出解，而不能再作遞歸調(diào)用，因此每次遞歸均是有條件的，無條件遞歸會造成死循環(huán)，無法正常結(jié)束。遞歸過程或函數(shù)對應(yīng)的參數(shù)在遞歸過程中是按照一定的規(guī)律變化的，函數(shù)值增減方向能夠和遞歸終止條件匹配，確保遞歸調(diào)用在可控范圍內(nèi)[3]。因此，遞歸函數(shù)一般設(shè)計(jì)形式主要可以通過以下語句描述：

T func（mode）//T可以是void，即遞歸函數(shù)不一定必須有返回值，mode是參數(shù)的一般模式：

因此，遞歸問題求解步驟一般為：理解原問題的意思，獲得待求問題解，對應(yīng)函數(shù)為f（n）；尋求另一個(gè)函數(shù)g（），確保f（n）=g（f（n-1）），原問題解能夠通過一些小問題解表示，尋求遞推關(guān)系式，（n-1）一般為n/2，使問題規(guī)模能夠逐漸縮??；確保f（0）與f（1）為已知值，從而通過這兩個(gè)已知的值與函數(shù)g（）求得f（n）的解。

1.5 遞歸算法執(zhí)行過程

執(zhí)行遞歸算法的過程是由回溯與遞推兩個(gè)步驟完成的，回溯是指逐層遞歸調(diào)用，遞推即按原路徑層層遞歸返回兩個(gè)步驟，回溯時(shí)需要保存斷點(diǎn)地址、形式參數(shù)與局部變量，控制整個(gè)求解過程是直接趨向于遞歸調(diào)用入口的過程。遞推是在本次遞歸調(diào)用結(jié)束后，逐層向上一層遞歸調(diào)用返回，同時(shí)要保存本次調(diào)用函數(shù)結(jié)題，使后續(xù)求解能夠繼續(xù)按照原局部變量與形式參數(shù)進(jìn)行求解，并通過調(diào)用時(shí)出現(xiàn)的斷點(diǎn)地址控制遞歸流程逐漸向調(diào)用函數(shù)下一行代碼處轉(zhuǎn)回，以便于執(zhí)行下一個(gè)循環(huán)。從以上過程可以看出，遞歸算法執(zhí)行過程就意味著需要不斷進(jìn)行自調(diào)用，逐步遞歸到終止條件出現(xiàn)后，即可結(jié)束自調(diào)用，達(dá)到條件后，再通過最后調(diào)用過程逐步自最先返回的次序開始進(jìn)行逐層返回求解，在返回到最外層的調(diào)用語句時(shí)，表明這一執(zhí)行過程完結(jié)。

1.6 遞歸算法的問題

遞歸算法在求解時(shí)有一個(gè)較嚴(yán)重的問題，以FIBONACCI數(shù)列為例如果需要計(jì)算40！時(shí)，基本計(jì)算涉及39次加法，即使在運(yùn)行速度相對較快的計(jì)算機(jī)上也需要較長時(shí)間的運(yùn)行，時(shí)間花費(fèi)過大，其根本問題就在于遞歸的多余計(jì)算較多，計(jì)算f（n）時(shí)，就需要計(jì)算f（n-1），依次類推，后續(xù)計(jì)算還會涉及f（n-2），f（n-3）等的計(jì)算，需要多次對上一次計(jì)算結(jié)果進(jìn)行遞歸調(diào)用，每一次遞歸均對應(yīng)更多的計(jì)算過程，計(jì)算效率較低，因此，需要確保遞歸過程中不需要通過單獨(dú)的遞歸調(diào)用對類似問題進(jìn)行處理，以避免問題復(fù)雜化。

2 計(jì)算機(jī)程序設(shè)計(jì)中的數(shù)學(xué)應(yīng)用分析

數(shù)學(xué)是目前各門科學(xué)的重要基礎(chǔ)，計(jì)算機(jī)科學(xué)從一開始僅是一個(gè)數(shù)學(xué)分支，時(shí)代的發(fā)展使計(jì)算機(jī)與數(shù)學(xué)之間的關(guān)系不斷密切化，計(jì)算機(jī)實(shí)際上已經(jīng)成為一個(gè)重要的計(jì)算工具，要解決實(shí)際問題時(shí)，可以運(yùn)用各種科學(xué)計(jì)算設(shè)計(jì)一個(gè)計(jì)算機(jī)程序，直接將實(shí)際問題抽象轉(zhuǎn)換成計(jì)算機(jī)程序，這一轉(zhuǎn)換過程就是實(shí)際問題的不斷抽象化過程，運(yùn)用合理的數(shù)學(xué)算法設(shè)計(jì)一個(gè)完善、簡潔、清晰的數(shù)學(xué)模型，才能夠?qū)崿F(xiàn)實(shí)際問題到計(jì)算機(jī)程序的轉(zhuǎn)換，這就要求程序員的數(shù)學(xué)科學(xué)基礎(chǔ)更為完備。算法是軟件程序最為重要的思想，算法又是以數(shù)學(xué)思維為基礎(chǔ)的，程序僅是外在，算法才是其靈魂，算法以數(shù)學(xué)為基礎(chǔ)，若不具備豐富的數(shù)學(xué)思維，就無法弄懂算法。如，四色問題的求解就涉及幾何、離散數(shù)學(xué)、小波分析、有限單元數(shù)值計(jì)算法、仿生計(jì)算等多個(gè)數(shù)學(xué)分支；運(yùn)用萊文賓—杜賓遞推算法的大規(guī)模矩陣運(yùn)算還能夠在VC++環(huán)境下設(shè)計(jì)一個(gè)濾波器模擬軟件；數(shù)字信號的處理也涉及三角函數(shù)、傅里葉變換、微積分、數(shù)值逼近及高次方程求解等多種數(shù)學(xué)基礎(chǔ)知識。因此，數(shù)學(xué)知識在計(jì)算機(jī)程序設(shè)計(jì)中具有重要地位，要解決一些程序設(shè)計(jì)當(dāng)中的問題，需要運(yùn)用各種數(shù)學(xué)思想及計(jì)算方法，使程序員能夠?qū)?shí)際問題有效轉(zhuǎn)換為計(jì)算機(jī)程序，通過一個(gè)有效的抽象過程，使實(shí)際問題能夠轉(zhuǎn)換為數(shù)學(xué)模型，進(jìn)而完成程序設(shè)計(jì)。

3 結(jié)語

從遞歸算法在計(jì)算機(jī)程序設(shè)計(jì)的應(yīng)用中可以發(fā)現(xiàn)，抽象數(shù)學(xué)問題的解決，首先需要完成數(shù)學(xué)模型設(shè)計(jì)的問題，運(yùn)用相應(yīng)的算法設(shè)計(jì)一個(gè)完善的數(shù)學(xué)模型，建立一個(gè)有效的邏輯結(jié)構(gòu)后，再進(jìn)行程序設(shè)計(jì)。合理運(yùn)用數(shù)學(xué)解題方法，能夠使計(jì)算機(jī)編程更為方便。

[參考文獻(xiàn)]

[1]周法國.基于遞歸的程序設(shè)計(jì)淺析[J].天津科技，2017（6）：103-105.

[2]遲呈英，王玄同，王子涵，等.數(shù)學(xué)解題方法與程序設(shè)計(jì)關(guān)系的研究[J].軟件工程，2016（2）：16-18.

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