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

# 前言

本文沒有 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

簡單來說, 就是交替式的呼叫兩個不同的 recursion method, 比方說, 這一輪呼叫 function B, 下一輪又呼叫 function A, 下一輪又回到 function B, 依序輪流的呼叫直到終點

何謂 Nested recursion

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

Laravel - Basics - Session (官方文件原子化翻譯筆記) Laravel - Digging Deeper - Cache (官方文件原子化翻譯文件)

留言

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×