# 前言
本文沒有 example, 主要為簡單介紹一下不同類型的遞迴
# Linear recursion (線性遞迴)
這是最常被使用的 recursion 之一, 當一個 function 在每一輪都呼叫自己一次, 就稱為 linear recursion 就像是之前介紹過的 factorial example, 當我們將大問題一步步的分解成小問題, 朝終點前進的這段過程, 又稱為 Winding (纏繞), 而從終點處一路 return 回來, 這段又稱為 Unwinding (解纏繞)
# Binary recursion (二元遞迴)
在 binary recursion 當中, function 每一輪都會呼叫自己兩次。 每一輪的結果來自兩個不同的 recursion 計算後而得之, 可以參考之前介紹過的 Fibonacci sequence binary recursion 被使用在非常多的地方, 像是 binary search (二元搜尋), divide and conquer (分治法), merge sort (合併搜尋法) … 等。 示意圖如下：
# Tail recursion
簡單來說, 就是當 recursion 跑到終點時, 不需要將終點得到的結果再反向的一路計算回來, 例如我們之前介紹過的 GCD Tail recursion 也是 linear recursion 的一種
# Mutual recursion
簡單來說, 就是交替式的呼叫兩個不同的 recursion method, 比方說, 這一輪呼叫 function B, 下一輪又呼叫 function A, 下一輪又回到 function B, 依序輪流的呼叫直到終點
# Nested recursion
當一個 recursion function 呼叫了它自己, 並且 recursion function 的 args 之一也是這個 recursion function, 這樣就稱為 Nested recursion 馬的怎麼有點像繞口令, 如下示意圖：
在 A() 當中, A() 呼叫了 A(), 並且將 A() 當成參數帶入, 這樣就稱為 Nested recursion
# 結語
啊哈, recursion 種類介紹就到此結束啦, 接下來我們來介紹一些 recursion 應用實例 我們下次見！
