算法——遞歸(以漢諾塔爲例)

首先理解一下什麼叫遞歸,為什麼要用遞歸,它的優勢是什麼?(為了方便於理解,不一定對)

先說一個笑話:

算法——遞歸(以漢諾塔為例)

遞歸:無限調用自身這個函數,每次調用總會改動一個關鍵變量(每次的改變都會被保存下來,為了後面的“歸”),直到這個關鍵變量達到邊界的時候(也就是“遞”到了盡頭,什麼是盡頭呢?這是需要你自己設定的),之後不再調用,然後開始”歸“。像「老和尚給小和尚講故事」那種遞歸一般都不能無限循環下去,因為那樣講的人會受不了,所以一般到了最後,那個人會說:「他講的故事是:就是這個故事!」。於是,遞歸結束了。

遞歸是一種思想,是一種複雜問題簡單化的思維方式,而這種思維方式在程序中的體現就遞歸算法!遞歸算法在實現上就是函數不斷調用自身的過程!

需要確定的是:1.遞歸的邊界條件 2.遞歸通式

遞歸可以先通過有限的次數,找出規律,總結出公式,這個公式第N項的值跟第N-1項的值存在一定的關係就可以使用遞歸(一定要考慮邊界條件),這是真正的關鍵部分!!!!

本文不講棧,只針對初次接觸的同學們,不然一篇文章不太能講清楚,後期更新中小編會安排結合棧來講算法遞歸的,喜歡的觀眾老爺請加關注噢!!!


比如說求N!

一般第一思維會用循環啊(沒錯,但是現在要求用遞歸!)

算法——遞歸(以漢諾塔為例)

如果對於C掌握的還行的話,這段代碼應該很好理解。遞歸,顧名思義就是“遞”和“歸”。也就是說,寫每一個遞歸函數的時候,都應該在寫之前考慮清楚,哪裡體現了“遞”,哪裡體現了“歸”。

上面我們所講的邊界也就是if語句,當n=1時開始結束調用開始”歸“。而Func就是關鍵變量。為什麼會這樣寫呢?因為我們很容易的找到這樣的規律:1*2*3*4……*n。都是n*(n+1),這就是規律,而在C語言上變現出來的就是遞歸算法。

算法——遞歸(以漢諾塔為例)

結合圖片再想想(ง •_•)ง

但是常常遞歸函數會比較複雜, “遞”和“歸”看起來並不是那麼明顯,這就需要我們進一步來理解遞歸算法的思想。


有人會說那我循環也可以做到的事為什麼大費周章的用遞歸呢?

先說說兩者的關係:

  • 相同點:

(1)都是通過控制一個變量的邊界或者多個),來改變多個變量為了得到所需要的值,而反覆而執行的;

(2)都是按照預先設計好的推斷實現某一個值求取;(請注意,在這裡循環要更注重過程,而遞歸偏結果一點)

  • 不同點:

(1)遞歸通常是逆向思維居多,“遞”和“歸”不一定容易發現(比較難以理解);而循環從開始條件到結束條件,包括中間循環變量,都需要表達出來(比較簡潔明瞭)。

簡單的來說就是:用循環能實現的,遞歸一般可以實現,但是能用遞歸實現的,循環不一定能。因為有些題目只注重循環的結束條件和循環過程,而往往這個結束條件不易表達(也就是說用循環並不好寫);注重循環的次數而不注重循環的開始條件和結束條件(這個循環更加無從下手了)。可能到這裡大家還是不太清楚。下面結合漢諾塔實例來講解。


來看看“漢諾塔問題”

如圖,漢諾塔問題是指有三根杆子A,B,C。C杆上有若干碟子,把所有碟子從A杆上移到C杆上,每次只能移動一個碟子,大的碟子不能疊在小的碟子上面。求最少要移動多少次?

算法——遞歸(以漢諾塔為例)

這是一個循環只注重循環次數的經典例子,我們知道,用循環有點無從下手(文章結束小編將給出代碼),但是遞歸就很好寫了。

漢諾塔,什麼鬼,我不會啊?

別急,慢慢來。

我們首先需要一點思維:解決n塊盤子從A移動到C,那麼我只需要先把n-1塊盤子從A移到B,然後把最下面的第n塊盤子從A移到C,最後把n-1塊盤子從B移到C(這就完成了)。

等等,那麼如何把n-1塊盤子從A移到B?

很好,這說明你已經開始遞歸入門了。

同樣這樣去想:解決n-1塊盤子從A移動到B,那麼我只需要先把n-2塊盤子從A移動到C,然後把倒數第二塊盤子從A移到B,最後把n-2塊盤子從C移到B(這就完成了)。

這就是遞歸的“遞”!

那麼“歸”呢?n==1的時候?

算法——遞歸(以漢諾塔為例)

換一句話說,我們來一個一個找規律:

當只有一個盤子的時候,只需要從將A塔上的一個盤子移到C塔上。

當A塔上有兩個盤子是,先將A塔上的1號盤子(編號從上到下)移動到B塔上,再將A塔上的2號盤子移動的C塔上,最後將B塔上的小盤子移動到C塔上。

當A塔上有3個盤子時,先將A塔上編號1至2的盤子(共2個)移動到B塔上(需藉助C塔),然後將A塔上的3號最大的盤子移動到C塔,最後將B塔上的兩個盤子藉助A塔移動到C塔上。

當A塔上有n個盤子是,先將A塔上編號1至n-1的盤子(共n-1個)移動到B塔上(藉助C塔),然後將A塔上最大的n號盤子移動到C塔上,最後將B塔上的n-1個盤子藉助A塔移動到C塔上。(真正的規律所在!!)

綜上所述,除了只有一個盤子時不需要藉助其他塔外,其餘情況均一樣。

我們來看看普通算法的解決過程:(真的是又臭又長。。)

算法——遞歸(以漢諾塔為例)

算法——遞歸(以漢諾塔為例)

算法——遞歸(以漢諾塔為例)

算法——遞歸(以漢諾塔為例)

算法——遞歸(以漢諾塔為例)

調試運行結果

希望大家能通過這篇文章理解遞歸,也在此向大家拜年了!!祝大家性的一年學習進步,生活美滿!!

也希望大家動動手加個關注,評論一下,給小編繼續碼字發文的動力!!!


分享到:


相關文章: