相互遞歸

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

基本概念

遞歸係乜

内文：遞歸 (電腦科學)

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

$3!=3\times 2\times 1=6$

$4!=4\times 3\times 2\times 1=24$

$5!=5\times 4\times 3\times 2\times 1=120$

$9!=9\times 8\times 7\times 6...$

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

呢個子程式叫 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);
}

有限狀態機

内文：有限狀態機

有限狀態機亦可以透過相互遞歸演算法嚟實現。一部有限狀態機會有若干個「狀態」，每個狀態涉及嘅行為都唔同。例如電子遊戲入便嗰啲 AI 技術就成日會用到有限狀態機，想像而家要製作一隻動作遊戲，遊戲入便嘅 AI 敵人有若干個狀態，就可以用好似以下噉嘅虛擬碼，嚟教電腦點樣控制呢啲敵人：

子程式 ceon lo () # 巡邏

如果 見到玩家角色，就 zeoi bou ()

否則 繼續做巡邏要做嘅嘢。

子程式 zeoi bou () # 追捕

如果 玩家角色進入射程，就 gung gik ()

如果 玩家角色離開視線，就 ceon lo ()

否則 繼續做追捕要做嘅嘢。

子程式 gung gik () # 攻擊

如果 玩家角色離開射程，就 zeoi bou ()

否則 繼續做攻擊要做嘅嘢。

就算到咗廿一世紀初，呢種控制遊戲敵人嘅技術都仲好多人用。

睇埋

• 圖論上講嘅環