首頁 > 文章 > web前端 > JavaScript實作遞迴演算法的方法介紹

JavaScript實作遞迴演算法的方法介紹

不言轉載: 2019-03-23 11:42:544120瀏覽

這篇文章帶給大家的內容是關於JavaScript實作遞歸演算法的方法介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

我們先來看定義。遞歸演算法，是將問題轉化為規模縮小的同類問題的子問題，每個子問題都用一個同樣的演算法去解決。一般來說，一個遞歸演算法就是函數呼叫自身去解決它的子問題。

　　遞歸演算法的特點：

在函數過程中呼叫自身。
在遞迴過程中，必須有一個明確的條件判斷遞歸的結束，既遞歸出口。
遞歸演算法簡潔但效率低，通常不作為推薦演算法。

　　上面這些是百度百科的解釋，講的也是十分明確，大家配合實例來細細琢磨。

　　階乘

　　問題描述： n! = n*(n-1)*...2*1

　　程式碼實作：

JavaScript實作遞迴演算法的方法介紹

　　我們拿到問題的時候，我們依照定義的說明，可以先將規模縮小到同類的子問題。例如，n! 是等於 n* (n-1)!，然後(n-1)! = (n-1)*(n-2)!。這樣依序往下推，直到if的出口。這裡用了arguments.callee，是為了防止函數名稱的緊密耦合，在這裡它等同於factorial(n-1)。函數實現起來是不是簡潔明了呢。當然因為問題規模簡單，其實實用循環也是可以實現的，大家可以試試看。

斐波那契數列

　　問題描述：1, 1, 2, 3, 5, 8, 13, 21, 34, ....... 求第n個數是多少。

　　程式碼實作：

　　下载 (1).png

#　　其實實用剛才的想法實現，也是非常的簡單的。透過分析可以得到第n個數，是前兩個數的和，透過這個我們就可以透過遞歸，不斷得到所需要的前兩個數，直到n

　　走樓梯問題

　　問題描述：樓梯有n階台階，上樓可以一步上1階，也可以一步上2階或3階，計算共有多少種不同的走法。

　　程式碼實作：

　　下载 (2).png

#　　這其實就是一個斐波那契數列的一種實作。我們分析的時候，可以轉換成小規模的子類問題。當到達指定階梯的最後一步的時候，可以有三種種情況，一是上一步，二是上兩步，三是上三步。所以總的方法是F(n) = F(n-1) F(n-2) F(n-3)。然後自然就成了各自的小計算，不斷循環下去，直到判斷條件的發生。

　　最大公約數

　　問題描述：給兩個數，如果兩個數相等，最大公約數是其本身。若不等，取兩個數相減的絕對值和兩個數中最小的數比較，相等則為最大公約，不等則繼續上面的演算法，直到相等。

　　程式碼實作：

　　下载 (3).png

#　　沒什麼好說的，照問題描述所要求的實作就可以了。遞歸的出口便在於a等於b。

　漢諾塔

　　問題描述：大家都或多或少的玩過，這裡就不再贅述了。

　　程式碼實作：

　　下载 (4).png

#　　在我沒有體會到遞歸的精粹前，我對這個問題簡直百思不得其解。我一直問自己，我怎麼知道下一個該去哪裡？後來，我就知道，我其實更在乎的是，最後那一個該怎麼走。這個怎麼說呢？我們可以從頭想起，我們如果只有1個盤，我們可以讓它到C柱，也可以到B柱。自然兩個盤，也可以實現。 3個盤，也是可以的吧。那我們就講4個盤的情況。 4個盤要完成就要將A上的圓盤，完全轉移到C上。我們把前3個盤當作一個整體放到B上，然後第4個盤就可以到C上了，然後我們再將前三個放到C上，就成功了。那前三個盤，又可以重新當作一個新遊戲，讓前兩個盤，當一個整體，依次類推。這樣我們只需要關心大的整體的事，其它的就轉成小規模問題解決就好了。

二分法快排

　　問題說明：使用二分法，將一個陣列進行由小到大的排序。

　　程式碼實作：

　　下载 (5).png