【算法】算法圖解筆記_遞歸

tomlingtm 發布于2019-07-31 10:12 / 728人閱讀

遞歸是個有意思的概念，正如在前面所說，遞歸能讓算法的可讀性大大提高，而且通常要比使用循環結構更能寫出準確的算法。這本書形象引入了遞歸，并沒有太深入，所以我進行了一點“添油加醋”。

遞歸概念

遞歸其實就是自己調用自己。可以從多種維度對遞歸分類，我見過的最常見的分類：

直接遞歸

自己直接調用自己。如：

--haskell
length" :: [a] -> Int
length" [] = 0
length" (_:xs) = 1 + length" xs

上面定義的length"就是通過直接遞調用自身完成列表長度的計算。

間接遞歸

可以認為只要不是直接調用自己的遞歸都是間接遞歸，其表現形式較多，如A->（調用）B，B->（調用）A，如奇偶謂詞函數：

--haskell
odd" :: Int -> Bool
odd" 0 = False
odd" n = even" (n - 1)

even" :: Int -> Bool
even" 0 = True
even" n = odd" (n - 1)

也可以有A->B，B->C，... Z->A。這里就不舉例子了。

書中的例子

有一個盒子，盒子里套著一個或多個盒子，盒子里的盒子又有盒子，依次類推。而鑰匙就在某個盒子里，我們怎么找到鑰匙呢。

策略一

偽代碼如下：[偽代碼是對手頭問題的簡要描述,看著像代碼,但其實更接近自然語言。]

def look_for_key(main_box):
  pile = main_box.make_a_pile_to_look_through()
  while pile is not empty:
    box = pile.grab_a_box()
    for item in box:
      if item.is_a_box():
        pile.append(item)
      elif item.is_a_key():
        print "found the key!"

如果學習過樹的遍歷，是不是發現這就是廣度優先遍歷啊

策略二

偽代碼如下：

def look_for_key(box):
  for item in box:
    if item.is_a_box():
      look_for_key(item)
    elif item.is_a_key():
      print "found the key!"

對應的就是深度優先遍歷啊

這兩種方法的作用相同,但第二種方法更清晰。遞歸只是讓解決方案更清晰,并沒有性能上的優勢。實際上,在有些情況下,使用循環的性能更好。Leigh Caldwell在Stack Overflow上說的一句話:“如果使用循環,程序的性能可能更高;如果使用遞歸,程序可能更容易理解。如何選擇要看什么對你來說更重要。”

基線條件和遞歸條件

每個遞歸函數都有兩部分:基線條件(base case)和遞歸條件(recursive case)。遞歸條件指的是函數調用自己,而基線條件則指的是函數不再調用自己,從而避免形成無限循環。遞歸條件一定是向基線條件靠攏的，否則，只能無限遞歸下去。如

#python
def countdown(i):
  print i
  if i <= 0:
    return
  else:
    countdown(i-1)

上述函數中i的值收斂于0，即達到基線條件，從而不會無限遞歸下去。

棧

主要講了與遞歸相關的一種數據結構--棧（stack）。棧是一種支持FILO（First In Last Out）的數據結構。
為什么要提這種數據結構呢？

調用棧

這是因為現代計算機對函數的實現用到了調用棧（call stack）的棧。調用函數時，計算機將首先為該函數調用分配一塊內存。每當你調用函數時,計算機都將函數調用涉及的所有變量的值存儲到內存中。

假設A函數調用B函數，此時計算機為兩個函數分配了內存，暫且稱之為A函數內存和B函數內存，它們的位置關系如下：
----棧頂----
B函數內存
—————
A函數內存
—————

若B函數執行完，計算機就可以回收B函數內存了，即從棧頂彈出B函數內存，此時只有A函數內存了。
----棧頂----
A函數內存
—————

以上操作符合FILO的定義，調用棧是棧的一種具體應用。

那如果調用棧數量太多，會有什么后果呢？

遞歸調用棧

#python
def fact(x):
  if x == 1:
    return 1
  else:
    return x * fact(x-1)

對于較小的正整數，這個程序沒有問題；而如果x較大，在fact執行的時會發現內存量會飆升，甚至會出現程序無法正常執行下去。這是因為此時遞歸調用棧的情況類似：
----棧頂----
fact(1)函數內存
———————
...
———————
fact(n-2)函數內存
———————
fact(n-1)函數內存
———————
fact(n)函數內存
———————

fact(n)依賴fact(n-1)，依次類推，導致計算機存儲了大量函數調用的信息。這類問題大體有兩種解決方式：

重新編寫代碼,轉而使用循環。

使用尾遞歸。現在已經有很多編譯器支持尾遞歸優化了。

我的公眾號地址

GPU云服務器云服務器排序算法圖解最大值算法遞歸 java遞歸算法樹 java 樹遞歸算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/43432.html

【算法】算法圖解筆記_快速排序

摘要：再談大表示法快速排序的獨特之處在于其速度取決于選擇的基準值。在平均情況下快速排序的運行時間為在最糟情況下退化為。快速排序和合并排序的算法速度分別表示為和，是算法所需的固定時間量被稱為常量。分而治之分而治之(divide and conquer,D&C)是一種著名的遞歸式問題解決方法。只能解決一種問題的算法畢竟用處有限,而D&C提供了解決問題的思路,是另一個可供你使用的工具。 D&C...

YanceyOfficial 2019-07-31 10:14 評論0 收藏0
【算法】算法圖解筆記_算法簡介

摘要：在本書中你將學習比較不同算法的優缺點該使用合并排序算法還是快速排序算法或者該使用數組還是鏈表。這樣的算法包括快速排序一種速度較快的排序算法。在讀《算法圖解》這本書，這本書有兩個優點：手繪風格的圖，看著很讓人入戲；算法采用Python語言描述，能更好的表達算法思想。關于算法的學習有兩點心得：算法思想最重要，理解了思想，算法是很容易寫出來的，所以盡量不要把過多精力放在細節上...

tomlingtm 2019-07-31 10:10 評論0 收藏0
【算法】算法圖解筆記_選擇排序

摘要：選擇排序是下一章將介紹的快速排序的基石。需要存儲多項數據時有兩種基本方式數組和鏈表。但它們并非都適用于所有的情形因此知道它們的差別很重要。選擇排序是一種靈巧的算法但其速度不是很快。選擇排序是下一章將介紹的快速排序的基石。內存的工作原理計算機就像是很多抽屜的集合體,每個抽屜都有地址。showImg(https://segmentfault.com/img/bVbpWvv?w=413...

mylxsw 2019-07-31 10:12 評論0 收藏0
【算法】算法圖解筆記_廣度優先搜索

摘要：解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優先搜索讓你能夠找出兩樣東西之間的最短距離。使用廣度優先搜索解決問題。你經常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...

sanyang 2019-07-31 10:18 評論0 收藏0