---
title: 「你所不知道的 C 語言：遞迴呼叫篇」 筆記
tags: Computer Science,System Software
description: 2019.09.05
---
「你所不知道的 C 語言：遞迴呼叫篇」 筆記
===
###### *2019.09.05 Copyright © 2019 by srhuang*


[影片](https://youtu.be/gilUlOXjLt0)
[講義](http://hackfoldr.org/dykc/https%253A%252F%252Fhackmd.io%252Fs%252FrJ8BOjGGl)
Original by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)

---

## 前言
* 遞迴（recurse）只應天上有, 凡人該當用迴圈（iterate）：https://youtu.be/gilUlOXjLt0?t=10
* 所有的的遞迴都可以改寫成迴圈形式，改寫為迴圈形式通常也可以獲得效率上的提升。

## 遞迴程式沒有你想像中的慢
* GCD 範例遞迴迭代比較：https://youtu.be/gilUlOXjLt0?t=164
* 迭代會多了 local variable.
* [遞迴 (Recursion)](https://notfalse.net/9/recursion)
* 簡介：https://youtu.be/gilUlOXjLt0?t=395
* 陣列加總：https://youtu.be/gilUlOXjLt0?t=482
* 遞迴種類：https://youtu.be/gilUlOXjLt0?t=695
* tail recursion.
* Function Call：https://youtu.be/gilUlOXjLt0?t=789
* stack frame.
* Tail Recursion 的重要性：https://youtu.be/gilUlOXjLt0?t=929
* 自然數總和：https://youtu.be/gilUlOXjLt0?t=985
* local variable 會造成多緒程或是多核最佳化的成本。
* tail recursion 會把中間運算的結果當成參數，以避免重複運算。
* 尾端遞迴其實只是把迭代的 迴圈變化 與 區域變數，放在方法的參數中傳遞罷了。
* Recursive V.S. non-Recursive：https://youtu.be/gilUlOXjLt0?t=1368
* Hanoi Tower (河內塔)：https://youtu.be/gilUlOXjLt0?t=1486

## 案例分析: 等效電阻
* 案例分析：https://youtu.be/gilUlOXjLt0?t=1882

## 案例分析：數列輸出
* 案例分析：https://youtu.be/gilUlOXjLt0?t=2472
* Segmentation fault 意味著 stack overflow.
* 搭配 GDB 實驗。

## 遞迴程式設計
* [Recursive Programming](https://web.archive.org/web/20171116063115/http://www.cs.umd.edu:80/class/fall2002/cmsc214/Tutorial/recursion2.html)：https://youtu.be/gilUlOXjLt0?t=3907
* Tail and Head Recursion：https://youtu.be/gilUlOXjLt0?t=4075
* Binary Search：https://youtu.be/gilUlOXjLt0?t=4162
* The Mandelbrot Set (碎形)：https://youtu.be/gilUlOXjLt0?t=4510

## Fibonacci sequence
* 簡介：https://youtu.be/gilUlOXjLt0?t=4698
* 遞迴法：https://youtu.be/gilUlOXjLt0?t=4799
* 非遞迴法 (Iterative)：https://youtu.be/gilUlOXjLt0?t=4846
* Tail Recursion：https://youtu.be/gilUlOXjLt0?t=4910
* Others and Conclusion：https://youtu.be/gilUlOXjLt0?t=5222

## 案例分析：字串反轉
* https://youtu.be/gilUlOXjLt0?t=5495

## 案例分析: 類似 find 的程式
* https://youtu.be/gilUlOXjLt0?t=6466

## 案例分析: Merge Sort
* https://youtu.be/gilUlOXjLt0?t=8326

## MapReduce
* https://youtu.be/gilUlOXjLt0?t=8715

## 函數式程式開發
* https://youtu.be/gilUlOXjLt0?t=9232