Recursion (遞迴) - 不同類型的遞迴

12月 29 2020 Data Structure and Algorithm 6 分钟讀完 (大概 873 字)

# 前言

本文沒有 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 應用實例
我們下次見！

# Questions and Answers

何謂 linear recursion?

recursion method 在每一輪都呼叫自己一次, 直到終點

recursion 中, 朝向終點的遞迴過程又稱為？

winding (纏繞)

recursion 中, 從終點返回計算的過程又稱為

unwinding (解纏繞)

何謂 binary recursion?

在 binary recursion 當中, function 每一輪都會呼叫自己兩次。每一輪的結果來自兩個不同的 recursion 計算後而得之

何謂 Tail recursion?

簡單來說, 就是當 recursion 跑到終點時, 不需要將終點得到的結果再反向的一路計算回來

<?php
function gcd(int $a, int $b): int { 
    if ($b == 0) { 
     return $a; 
    } else { 
     return gcd($b, $a % $b); 
    } 
}

何謂 Mutual recursion

何謂 Nested recursion

當一個 recursion function 呼叫了它自己, 並且 recursion function 的 args 之一也是這個 recursion function, 這樣就稱為 Nested recursion

#Recursion