---
# System prepended metadata

title: 「你所不知道的 C 語言：遞迴呼叫篇」 筆記
tags: [System Software, Computer Science]

---

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

![](https://i.imgur.com/to3YZ8P.png)

[影片](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




