遞歸算法用函數來實現，通俗地說就是函數對自身的調用，求解遞歸問題就轉化為函數的調用關系問題。函數f(n)隨自變量n的增加而變化，函數的調用關系也就表現為f(n)與f(n-1)或f(n-2)關系的問題。

下面我們按由簡到難的順序介紹遞歸算法的R語言實現。

n的階乘

01

n的階乘問題中，f(n)與f(n-1)關系非常明顯，即f(n)=f(n-1)*n.

R語言代碼如下：

當n=5時，調用函數：

factorial(5)

輸出結果：

120

斐波那契數列

02

兔子繁殖問題是由意大利數學家裴波那契（Fibonacci Leonardo，約1170-1250年）在他的著作《算盤書》中提出的：

假設第一個月有一雌一雄一對兔子，兔子兩個月達到性成熟，且開始交配生產小兔子，并且生產出的小兔子也是一雌一雄，同樣在兩個月后達到性成熟并交配生產一對一雌一雄的小兔子；兔子都不死，兔子就這樣繁殖下去；在一年后（第12個月）有多少對兔子？

根據假設，n-2個月的兔子在第n個月可以生產一對兔子，所以第n個月的兔子就是第n-1個月的兔子對數加上n-2個月的兔子對數（即新出生的兔子對數）

R語言代碼如下：

當n=12時，調用函數：

fibonacci(12)

輸出結果：

144

九連環問題

03

九連環的每兩個環互相制約，只有第一環能夠自由上下，但若要想下或上第n個環，就必須滿足兩個條件（第一個環除外）：

（1）第n-1個環在架上；

（2）第n-2個環及前面的環全都不在架上。

下面我們先以三個環為例，說明求解九連環問題的步驟。假設三個環全部在架上：

（1）下第一個環，再下第三個環；（2步）

（2）上第一個環，下第二個環；（2步）

（3）下第一個環，至此三個環全部解下。（1步）

上面解三連環共用了5步。

從解三連環的步驟中，我們可以總結解n連環的步驟（設解n連環需要的最少步驟數為r(n)）：

（1）先下前n-2個環；（r(n-2)步）

（2）下第n個環；（1步）

（3）上前n-2個環，下第n-1個環。（r(n-2)+r(n-1)步）

從上面步驟可以看出求解n連環所需的最少步驟數r(n)=2* r(n-2)+ r(n-1)+1。（上前n-2個環與下前n-2個環所用步驟數相同）

R語言代碼如下：

當n=9時，調用函數：

NineRing(9)

輸出結果：

341

注：當n=2時，第2個環和第1個環也可同時卸下，這時公式會不同，感興趣的讀者可自行思考練習。

羅漢塔問題

04

漢諾塔(Hanoi)游戲相傳出現在古印度圣廟中。游戲的規則是：

在一塊銅板裝置上，有三根編號分別為A、B、C的桿，在A桿上按自下而上、由大到小按順序放置著64個金盤，每次只能移動一個金盤，并且在移動過程中三根桿上都始終保持大盤在下、小盤在上，操作過程中盤子可以置于A、B、C任意一桿上，如何把A桿上的金盤全部移到C桿上？

對于64個金盤的漢諾塔，求解過程較為復雜，我們先看三個金盤的情況：將三個盤子按由小到大的順序分別記作P1，P2，P3。若要按照規則將三個金盤從A桿移至C桿，則必須：

（1）先將P1移至C桿，再將P2移至B桿，然后將P1移至B桿，此時P1和P2均在B桿上；（3步）

（2）將P3移至C桿；（1步）

（3）將P1移至A桿，將P2移至C桿，最后將P1 移至C桿。（3步）

在這個過程中，要將P3移至C桿，先將C桿當作中介，將P1移至C桿；再將P1、P2先移至B桿，借用B桿做中介；再將P2移至C桿時，又先將P1移至A桿，借用了A桿做中介。（總共7步完成）

當盤子的數量增多時，上述遞歸思想仍然適用：設移動盤子的數量為n，n越大，表示盤子越大。為了將這n個盤子從A桿移動到C桿，同樣可以做以下三步:

（1）以C桿為中介，從A桿將1至n-1號盤移至B桿；

（2）將A桿中剩下的第n號盤移至C桿；

（3）以A桿為中介，從B桿將1至n-1號盤移至C桿。

漢諾塔問題中，當盤子的數量為n時，按上述方法移動的步數h(n)=2*h(n-1)+1。原因如下：

將第n個盤子移到C桿上之前，需要先將前n-1個盤子移到B桿上，需要h(n-1)步；將第n個盤子從A桿移動到C桿上，需要1步；再將前n-1個盤子移動到C桿上，還需要h(n-1)步（所需步數與前n-1個盤子在B桿上還是A桿上沒有關系，因為A桿、B桿只是中介），共2*h(n-1)+1步。

下面我們可以通過盤子的數量為4時，驗證漢諾塔問題的求解過程和所需要的最少步驟數：h(4)=15。

（1）以C桿為中介，將P1、P2、P3移至B桿：將P1移至B桿，再將P2移至C桿，再將P1移至C桿，再將P3移至B桿；然后將P1移至A桿，再將P2移至B桿，再將P1移至B桿；（7步）

（2）將P4移至C桿；（1步）

（3）以A桿為中介，從B桿將P1、P2、P3移至C桿：將P1移至C桿，將P2移至A桿，再將P1移至A桿，將P3移至C桿；再將P1移至B桿，將P2移至C桿，最后將P1移至C桿。（7步）

R語言代碼如下：

當n = 4時，調用函數：

hanoi(4)

輸出結果：

15

注：本文根據作者已發布在《今晚報》（副刊）上的文章“游戲中的遞歸算法”改編。

遞歸算法的R語言實現 （羅漢塔、九連環、斐波那契數列等問題的求解）?mp.weixin.qq.com

總結

以上是生活随笔為你收集整理的c++调用cplex求解例子_递归算法的R语言实现 （罗汉塔、九连环、斐波那契数列等问题的求解）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。