相互遞歸
相互遞歸(粵拼:soeng1 wu6 dai6 gwai1;英文:mutual recursion),又叫互遞歸或者間接遞歸,係遞歸嘅一種形式,指一個子程式呼叫另外一個子程式,而另外嗰個子程式又會呼叫返原先嗰個子程式,從而達致遞歸噉嘅效果。呢種做法可以用嚟整一啲有用嘅程式,例如有限狀態機就可以透過相互遞歸嚟實現。
基本概念
[編輯]遞歸係乜
[編輯]相互遞歸屬於遞歸[e 1]。遞歸係講緊一個子程式會「用到自己」或者「
用遞歸嚟計階乘嘅程式望落大致係噉樣:
- 呢個子程式叫 factorial(x)
- 如果 x == 0:
- Output 係 1
- 否則:
- Output 係 x 乘以 factorial(x-1)
- 如果 x == 0:
——factorial
呢個子程式,會「用返自己」,所以就係遞歸嘅一個例子。
間接遞歸
[編輯]而間接遞歸(相互遞歸)就係指個子程式呼叫另外一個子程式,而另外嗰個子程式又會呼叫原先個子程式轉頭。好似以下噉:
- 子程式 ft_a( n ):
- 如果 n ≤ 0:答案係 n
- 否則 print("Function A: ", n),然後 ft_b (n - 1)
- 子程式 ft_b( n ):
- 如果 n ≤ 0:答案係 n
- 否則 print("Function B: ", n),然後 ft_a (n - 1)
——如果用家設 n 做一個正整數,再入落 ft_a 嗰道,個程式會畀出 n, n-1, n-2, ... 1 嘅結果。喺成個過程當中,ft_a 會呼叫 ft_b,而後者跟住就會呼叫返前者,形成相互遞歸。如果子程式嘅數量有三個或者以上,佢哋之間都可以彼此之間互相呼叫,而形成相互遞歸。
應用
[編輯]响廿一世紀初,相互遞歸幾有用,例如以下嘅子程式(C 程式語言),就用咗相互遞歸,可以用嚟教電腦決定一個數係單數定雙數:
bool is_even(unsigned int n) {
if (n == 0)
return true;
else
return is_odd(n - 1);
}
bool is_odd(unsigned int n) {
if (n == 0)
return false;
else
return is_even(n - 1);
}
有限狀態機
[編輯]有限狀態機[e 2]亦可以透過相互遞歸演算法嚟實現。一部有限狀態機會有若干個「狀態」,每個狀態涉及嘅行為都唔同。例如電子遊戲入便嗰啲 AI 技術就成日會用到有限狀態機,想像而家要製作一隻動作遊戲,遊戲入便嘅 AI 敵人有若干個狀態,就可以用好似以下噉嘅虛擬碼,嚟教電腦點樣控制呢啲敵人:
- 子程式 ceon lo () # 巡邏
- 如果 見到玩家角色,就 zeoi bou ()
- 否則 繼續做巡邏要做嘅嘢。
- 子程式 zeoi bou () # 追捕
- 如果 玩家角色進入射程,就 gung gik ()
- 如果 玩家角色離開視線,就 ceon lo ()
- 否則 繼續做追捕要做嘅嘢。
- 子程式 gung gik () # 攻擊
- 如果 玩家角色離開射程,就 zeoi bou ()
- 否則 繼續做攻擊要做嘅嘢。
就算到咗廿一世紀初,呢種控制遊戲敵人嘅技術都仲好多人用[2][3]。
睇埋
[編輯]詞彙
[編輯]引述
[編輯]- ↑ Reading 14: Recursion,麻省理工學院
- ↑ Millington, I., & Funge, J. (2009). Artificial Intelligence for Games. CRC Press.
- ↑ Rabin, S. (2006). AI Game Programming Wisdom 3 (Game Development Series). Charles River Media, Inc..