---
# System prepended metadata

title: DS 讀書會 - 第 8 週
tags: [' tossug', hackpad-import]

---

---
hackpadID: QDK3n2nEvuS
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 8 週

01/13/2015

[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)

## 討論範圍

*   Recursion
    *   Objectives - Sierpinski Triangle

## 預定進度

*   Recursion
    *   Complex Recursive Problems - Programming Exercises

## 認領狀態

*   Exploring a Maze
    *   [Carl Su](/ep/profile/n5euV0AaWLn)
*   Dynamic Programming
    *   [Wen00072](/ep/profile/H12yKD7rYmT)

## 心得筆記

**Recursion 簡介**

*   定義
    *   將問題不斷地切割成類似的子問題，切割到極端簡單就可已解決的情況之後，才開始處理問題。
    *   最大的特點是函數會自己呼叫自己
    *   透過Recursion可以將使用優雅的程式碼解決問題，否則就需要用比較長的程式碼來解決問題。
    *   我個人感覺，recursion操作很像用發條玩具，你一直轉發條，轉到底後，放開發條玩具就開始動作了。

*   簡單拆解範例
    *   n = 1 + 2 + 3 + 4 + 5
    *   可以拆解成
        *   n = 1 + n2
        *   n2 = 2 + n3
        *   n3 = 3 + n4
        *   n4 = 4 + n5
        *   n5 =5
    *   當到n5 = 5就是發條到底的情況，也是最簡單的情況。接下來開始倒轉
    *   n5 = 5
    *   n4 = 4 + n5 = 4 + 5 = 9
    *   n3 = 3 + n4 = 3 + 9 = 12
    *   n2 = 2 + n3 = 2 + 12 = 14
    *   n = 1 + n2 = 1 + 14 = 15

沒feel? 看~~飯粒~~範例

*   #!/usr/bin/env python3
*   def sum_recursin(numList):
*   if len(numList) == 1:
*   return numList[0]
*   else:
*   return numList[0] + sum_recursin(numList[1:])

*   if __name__ == "__main__":
*   print(sum_recursin(list(range(1, 101))))

~~飯粒~~範例2

*   from test import testEqual
*   def reverse(string):
*   if len(string) == 1:
*   return string
*   else:
*   return reverse(string[1:]) + string[0]

*   testEqual(reverse("hello"),"olleh")
*   testEqual(reverse("l"),"l")
*   testEqual(reverse("follow"),"wollof")
*   testEqual(reverse(""),"")

三小？ Let me see see,

res = n2 + ’h’

n2 = n3 + ’e’

n3 = n4 + ’l’

n4 = n5 + ’l’

n5 = ’o’

發條到底了，回來了

n5 = ’o’

n4 = n5 + ’l’ = ’o’ + ’e’ = ’ol’

n3 = n4 + ’l’ = ’ol’ + ’l’ = ’oll’

n2 = n3 + ’e’ = ’oll’ + ’e’ = ’olle’

res = n2 + ’h’ = ’olle’ + ’h’ = ’olleh’

懂？了？

**Recursion 三定律**

*   要有結束情況，定義名稱為base case，就像發條轉到底就無法再轉下去
    *   如前所說，這個就是「最小解決可直接解的問題」片段
*   求解的過程中會漸漸朝向base case，也就是轉發條的動作
*   函數必須自己呼叫自己。轉發條中大概就沒有這樣的類似東西了

## 視覺化

碎形樹

![](https://hackpad-attachments.s3.amazonaws.com/hackpad.com_QDK3n2nEvuS_p.277973_1420939162396_undefined)

## 活動簽到

[Carl Su](https://tossug.hackpad.com/ep/profile/n5euV0AaWLn)

[FourDollars](https://tossug.hackpad.com/ep/profile/tgNQRpN8EgG)

Jonathan Hsieh

[Manuel Stallman](https://tossug.hackpad.com/ep/profile/GgkcGJEol5r)

[RJ Hsiao](https://tossug.hackpad.com/ep/profile/BzrOLagTOUQ)

[Scott Yu](/ep/profile/FXMAg851dkz)

StarNight

[Ted Wu](/ep/profile/xo5A62wXl3B)

Wen00072
