フィボナッチ数列は相互再帰だという話

この記事では，Haskellの記法を使います。

自然数は以下のように定義しておきます。

data Nat = Zero | Succ Nat

フィボナッチ数列を計算する関数　典型的な定義

fib Zero            = Zero
fib (Succ Zero)     = Succ Zero
fib (Succ (Succ n)) = fib n  +  fib (Succ n)

2段階目の場合分け部分を関数としてくくり出す

fib (S n'')の引数(S n'')は必ず1以上になるので，1段階目で無駄な場合分けが発生します。

1段階目の場合分けをパスして，2段階目の場合分けにジャンプするために，2段階目の場合分け部分を関数としてくくり出します。

fib Zero = Zero
fib (Succ n) = fibS n

fibS Zero = Succ Z
fibS (Succ n) = fib n + fibS n

2段階目の場合分け部分を，fibSという関数にしました。
fibとfibSは相互再帰関数です。

fibとfibSの関数呼び出し関係を図にすると，こんな感じです。