從遞歸算法看數學在計算機程序設計方面的應用與研究

李青柏

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

關鍵詞：遞歸算法；數學；計算機程序設計

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

1 遞歸算法在計算機程序設計中的運用設計

1.1 遞算法設計的一般步驟

遞歸算法設計時，主要通過3個步驟完成：（1）分析問題，理解題意，設計遞歸關系表達式。（2）設計遞歸終止表達式，有效控制遞歸循環，使遞歸結束時能夠獲得原問題的解。（3）明確形式參數，設計遞歸函數[2]。

1.2 設計遞歸關系式

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

1.3 設計遞歸終止條件

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

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

當遞歸過程或函數不止對應一條自身調用程序時，就會出現多個遞歸終止條件。如爬樓梯問題的分析，通過遞歸算法解決時，遞推至一定程度后，會面臨剩余樓梯數量不同，解法不同的問題，那么就會出現多個遞歸終止條件。

1.4 確定參數，設計遞歸函數

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

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

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

1.5 遞歸算法執行過程

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

1.6 遞歸算法的問題

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

2 計算機程序設計中的數學應用分析

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

3 結語

從遞歸算法在計算機程序設計的應用中可以發現，抽象數學問題的解決，首先需要完成數學模型設計的問題，運用相應的算法設計一個完善的數學模型，建立一個有效的邏輯結構后，再進行程序設計。合理運用數學解題方法，能夠使計算機編程更為方便。

[參考文獻]

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

[2]遲呈英，王玄同，王子涵，等.數學解題方法與程序設計關系的研究[J].軟件工程，2016（2）：16-18.

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