---
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，也就是轉發條的動作
* 函數必須自己呼叫自己。轉發條中大概就沒有這樣的類似東西了

## 視覺化

碎形樹


## 活動簽到

[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