動(dòng)態(tài)規(guī)劃變形算法在遞歸函數(shù)中的應(yīng)用

封震震

摘要：能夠編寫(xiě)遞歸函數(shù)必須具備兩個(gè)條件，一個(gè)是遞歸方程，另一個(gè)是邊界條件，動(dòng)態(tài)規(guī)劃算法具有最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題兩個(gè)性質(zhì)，動(dòng)態(tài)規(guī)劃思想的引入可以降低遞歸函數(shù)的運(yùn)行時(shí)間，也就是減少了計(jì)算所有小于或等于給定參數(shù)的遞歸調(diào)用所要求的時(shí)間，其中僅僅處理一次遞歸調(diào)用的時(shí)間，避免重復(fù)問(wèn)題重復(fù)計(jì)算。以斐波那契數(shù)列為例，通過(guò)編程對(duì)照動(dòng)態(tài)規(guī)劃變形算法在遞歸函數(shù)的應(yīng)用。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃;遞歸調(diào)用;時(shí)間復(fù)雜度

中圖分類(lèi)號(hào)：TP311? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? 文章編號(hào)：1009-3044（2019）03-0067-02

1 一般遞歸函數(shù)定義格式

遞歸就是一個(gè)函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身。執(zhí)行遞歸函數(shù)將反復(fù)調(diào)用其自身，每調(diào)用一次就進(jìn)入新的一層。層數(shù)越多重復(fù)計(jì)算量就越大，遞歸有兩個(gè)要素，遞歸方程和邊界條件。當(dāng)函數(shù)一直遞歸調(diào)用，直到遇到邊界條件后返回。斐波那契數(shù)列遞歸函數(shù)的兩個(gè)要素如下。

2 遞歸函數(shù)改進(jìn)前后比較

2）改進(jìn)后，定義一個(gè)函數(shù)Fib（long? a[]，int n），具有兩個(gè)參數(shù)，形參a[]表示斐波那契數(shù)列，形參n表示第幾個(gè)數(shù)列，a[]數(shù)組具有備忘功能的自頂向下存值，當(dāng)要引用某一個(gè)值時(shí)，判定是否計(jì)算過(guò)，若已經(jīng)計(jì)算，直接賦值即可。若n=6時(shí)，改進(jìn)后，遞歸處理的過(guò)程如圖3所示，其計(jì)算效率很高。

3 結(jié)束語(yǔ)

動(dòng)態(tài)規(guī)劃變形算法（備忘錄方法）與動(dòng)態(tài)規(guī)劃算法是有不同點(diǎn)，備忘錄方法的遞歸方式是自頂向下的，而動(dòng)態(tài)規(guī)劃算法則是自底向上的，但兩者在處理重復(fù)性問(wèn)題時(shí)的思路是一樣，避免重復(fù)計(jì)算。使用動(dòng)態(tài)規(guī)劃變形算法可彌補(bǔ)遞歸調(diào)用的缺點(diǎn)：1）分配空間及調(diào)用次數(shù)倍數(shù)減少。遞歸是函數(shù)調(diào)用自身，在程序中函數(shù)調(diào)用是有時(shí)間和空間的消耗的，進(jìn)行每一次函數(shù)調(diào)用時(shí)，都需要在內(nèi)存棧中分配空間來(lái)保存參數(shù)、返回地址以及臨時(shí)變量。2）避免重復(fù)計(jì)算問(wèn)題。遞歸中很多計(jì)算都是重復(fù)的，由于其本質(zhì)是把一個(gè)問(wèn)題分解成兩個(gè)或者多個(gè)小問(wèn)題，多個(gè)小問(wèn)題存在相互重疊的部分，則存在重復(fù)計(jì)算。3）不會(huì)超出棧的容量。調(diào)用棧可能會(huì)溢出，其實(shí)每一次函數(shù)調(diào)用會(huì)在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的，當(dāng)調(diào)用的層次太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致棧溢出。

函數(shù)具有時(shí)間復(fù)雜度和空間復(fù)雜度，尤其時(shí)間復(fù)雜度是函數(shù)的重要指標(biāo)，當(dāng)我們編寫(xiě)程序的時(shí)候一定要考慮其效率，盡可能應(yīng)用相關(guān)的算法提高函數(shù)的性能。

參考文獻(xiàn)：

[1] 陳曉梅，張晶.動(dòng)態(tài)規(guī)劃算法的教學(xué)探討[J].電腦知識(shí)與技術(shù)，2018，14（26）：146-147.

[2] 呂丹，楊子寒，周君.動(dòng)態(tài)規(guī)劃算法在生活中的應(yīng)用[J].電腦知識(shí)與技術(shù)，2018，14（17）.

[3] 李從宏.基于遞歸調(diào)用技術(shù)的關(guān)鍵字搜索軟件設(shè)計(jì)[J].電腦編程技巧與維護(hù)，2018（12）.

[4] 劉卓亞.基于C語(yǔ)言的遞歸算法研究[J].數(shù)字技術(shù)與應(yīng)用，2018，36（3）：132-133.

[5] 張瑋.動(dòng)態(tài)規(guī)劃法求解最大連續(xù)子序列和問(wèn)題[J].電子技術(shù)與軟件工程，2018（20）：122.

【通聯(lián)編輯：朱寶貴】