跳去內容

相互遞歸

出自維基百科,自由嘅百科全書
(由間接遞歸跳轉過嚟)

相互遞歸粵拼soeng1 wu6 dai6 gwai1英文mutual recursion),又叫互遞歸或者間接遞歸,係遞歸嘅一種形式,指一個子程式呼叫另外一個子程式,而另外嗰個子程式又會呼叫返原先嗰個子程式,從而達致遞歸噉嘅效果。呢種做法可以用嚟整一啲有用嘅程式,例如有限狀態機就可以透過相互遞歸嚟實現。

基本概念

[編輯]

遞歸係乜

[編輯]

相互遞歸屬於遞歸[e 1]。遞歸係講緊一個子程式會「用到自己」或者「呼叫call自己」,例如係以下嘅虛擬碼可以教電腦階乘[1]。階乘係指一個自然數同所有細過佢嘅正整數乘埋一齊,响數學符號上會用 嚟去表示,譬如:

用遞歸嚟計階乘嘅程式望落大致係噉樣:

呢個子程式叫 factorial(x)
如果 x == 0:
Output 係 1
否則:
Output 係 x 乘以 factorial(x-1)

——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]

睇埋

[編輯]

詞彙

[編輯]
  1. recursion
  2. finite state machine,FSM

引述

[編輯]
  1. Reading 14: Recursion麻省理工學院
  2. Millington, I., & Funge, J. (2009). Artificial Intelligence for Games. CRC Press.
  3. Rabin, S. (2006). AI Game Programming Wisdom 3 (Game Development Series). Charles River Media, Inc..