お気楽 Erlang プログラミング入門

再帰定義

関数を定義するとき、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。

ところが、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。とくに関数型言語の場合、再帰定義を積極的に活用してプログラミングを行うので、初心者の方が覚えるべき基礎テクニックのひとつにすぎません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。

●再帰定義の基本

まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。

\(\begin{array}{l} 0! = 1 \\ n! = n \times (n - 1)! \end{array}\)

図 : 階乗の定義

階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。

リスト : 階乗

-module(fact).
-export([fact/1]).

fact(0) -> 1;
fact(N) -> N * fact(N - 1).

関数 fact/1 は引数 N が 0 であれば 1 を返し、そうでなければ N * fact(N - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。

それでは、本当にこれで階乗を計算できるのか、実際に試してみましょう。

> c(fact).
{ok,fact}
> fact:fact(4).
24
> fact:fact(5).
120
> fact:fact(6).
720
> fact:fact(7).
5040

確かに階乗の答えを求めることができました。

●再帰定義のポイント

それでは、再帰定義のポイントを説明しましょう。次の図を見てください。


            図 : fact の再帰呼び出し（n:引数の値, value:返り値)

図は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 N の値は 4 なので N の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出し (Call:2) では、引数 N は 3 に束縛されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 N の値が違うことに注意してください。

関数の引数は局所変数として扱われます。前回説明したように、局所変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。関数呼び出しが行われるたびに新しい局所変数を生成して、そこに値を束縛します。そして、関数の実行が終了すると、生成された局所変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 N は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。

プログラムを見ると変数 N は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 N が作られていくと考えてください。fact(4) を実行しているときの N は 4 であり、fact(3) を呼び出すときには、この N の値を書き換えるのではなく、新しい変数 N を用意して、そこに 3 を束縛するのです。

同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 N が 0 になります。このとき、fact の最初の節が実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、プログラムは正常に終了しません。再帰呼び出しを使う場合は、この停止条件に十分注意してください。

fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行している間、引数 N の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。

●ガード (Guard)

ところで、関数 fact/1 に負の整数値を与えると、再帰呼び出しの停止条件が真にならないので、プログラムは正常に停止しません。Erlang のパターンマッチングにおいて、0 以上の整数値を表すパターンはありません。このような場合、when を使うと条件を指定することができます。when の構文を示します。

関数名(引数, ...) when 条件式 -> 式, ..., 式;

     ・・・・・

関数名(引数, ...) when 条件式 -> 式, ..., 式.


        図 : ガードの設定

パターンとの照合に成功して、かつ when の条件式が真を返す場合に限り右辺の式が評価されます。この機能を「ガード (Guard)」といいます。複数の条件式をカンマ (,) でつなげると論理積になり、セミコロン (;) でつなげると論理和になります。なお、when で指定できる条件式は if の条件式と同じで、制限があることに注意してください。詳細は Erlang のリファレンスマニュアル 8.25 Guard Sequences をお読みください。

ガードを使って関数 fact/1 を書き直すと次のようになります。

リスト : 階乗 (ガード付き)

fact(0) -> 1;
fact(N) when N > 0 -> N * fact(N - 1).

when で条件 N > 0 を指定します。これで N が正のときに節が実行されます。簡単な実行例を示します。

> fact:fact(10).
3628800
> fact:fact(-10).
** exception error: no function clause matching fact:fact(-10)

このように、負の値を入力するとエラーが表示されます。

●累乗の計算

それでは簡単な例題として累乗を求める関数 pow/2 を作ってみましょう。累乗は x の n 乗という x を n 回掛ける計算です。累乗は x の右上に小さく n を書くことで表されますが、ここでは x ** n と書くことにします。

pow (x, y) = x ** y

x ** 3 = x * x * x;
x ** 4 = x * x * x * x;
x ** 5 = x * x * x * x * x;


  図 : 累乗の計算

今回のプログラムは引数 x, y を整数とします。そうすると、x ** y は次のように定義することができます。

\(\begin{array}{l} x ** \ 0 = 1 \\ x ** \ y = x \times (x ** \ (y - 1)) \end{array}\)

図 : 累乗の定義

階乗の場合と同様に、x ** y は x ** (y - 1) がわかれば求めることができます。プログラムは次のようになります。

リスト : 累乗 (1)

-module(pow).
-export([pow/2]).

pow(_, 0) -> 1;
pow(X, Y) when Y > 0 -> X * pow(X, Y - 1).

再帰定義を使って X ** Y を計算しています。手続き型言語では単純な繰り返しで実現できる処理ですが、関数型言語では単純な繰り返しでも再帰定義を使って実現します。

簡単な実行例を示します。

> pow:pow(2,8).
256
> pow:pow(2,16).
65536
> pow:pow(2,32).
4294967296

●累乗の高速化

関数 pow(X, Y) は Y 回の掛け算をしなくてはいけませんが、式を変形するともっと少ない回数で累乗を求めることがでます。次の式を見てください。

x ** 4  = (x ** 2) ** 2 -> 2 回
x ** 8  = (x ** 4) ** 2 -> 3 回
x ** 16 = (x ** 8) ** 2 -> 4 回

一般化すると

x ** y = (x ** (y / 2)) ** 2       （y は偶数）
x ** y = ((x ** (y / 2)) ** 2) * x （y は奇数）


        図 : 累乗の高速化

階乗の計算では N を N - 1 の計算に置き換えていきますが、累乗の場合は Y を Y / 2 に置き換えていくことができます。Y が半分になっていくので減少の度合いが大きくなり、計算回数は少なくて済みます。これを単純にプログラムすると、次のようになります。

リスト : 累乗 (2)

pow1(_, 0) -> 1;
pow1(X, Y) when Y > 0 ->
    Z = pow1(X, Y div 2),
    ZZ = Z * Z,
    if
      Y rem 2 == 0 -> ZZ;
      true -> X * ZZ
    end.

% 別解
pow1(_, 0) -> 1;
pow1(X, Y) when Y > 0, Y rem 2 =:= 0 ->
    Z = pow1(X, Y div 2),
    Z * Z;
pow1(X, Y) when Y > 0 ->
    Z = pow1(X, Y div 2),
    X * Z * Z.

変数 Z の値は X ** (Y / 2) です。これは pow1 を再帰呼び出しすれば簡単に求めることができます。ZZ の値は Z ** 2 になります。あとは、Y が偶数であれば、ZZ をそのまま返し、奇数であれば X * ZZ を返します。別解はガードで Y が偶数かチェックして、処理を 2 つの節に分けて記述しています。こちらのほうが Erlang らしいプログラムかもしれません。

簡単な実行例を示します。

> pow:pow1(2, 8).
256
> pow:pow1(2, 16).
65536
> pow:pow1(2, 32).
4294967296
> pow:pow1(2, 64).
18446744073709551616

●フィボナッチ関数

もうひとつ簡単な数値計算の例を示しましょう。フィボナッチ関数も再帰的に定義される関数です。

\( fibo(n) = \begin{cases} 0, & if \ n = 0 \\ 1, & if \ n = 1 \\ fibo(n - 1) + fibo(n - 2), & if \ n \gt 1 \end{cases} \)

0, 1, 1, 2, 3, 5, 8, 13 ... という直前の 2 項を足していく数列

図 : フィボナッチ関数の定義

フィボナッチ関数も再帰定義を使えば簡単にプログラムできます。

リスト : フィボナッチ関数

-module(fibo).
-export([fibo/1]).

fibo(0) -> 0;
fibo(1) -> 1;
fibo(N) when N > 1 -> fibo(N - 1) + fibo(N - 2).

関数 fibo/1 は fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。


              図 : fibo/1 のトレース

同じ値を何回も求めているため、効率はとても悪いのです。もちろん、高速に求める方法があるので、心配しないで下さい。

それでは実行してみましょう。

> fibo:fibo(0).
0
> fibo:fibo(1).
1
> fibo:fibo(2).
1
> fibo:fibo(3).
2
> fibo:fibo(4).
3
> fibo:fibo(5).
5
> fibo:fibo(10).
55
> fibo:fibo(20).
6765

●ユークリッドの互除法

フィボナッチ関数は二重再帰でプログラムしたので実行速度はとても遅いのですが、再帰定義を使うと非効率的なプログラムになるというわけではありません。累乗のプログラムのように、再帰定義でも効率的なプログラムを作ることができます。たとえば、負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ってみましょう。まず最初に、ユークリッドの互除法を説明します。

[ユークリッドの互除法]
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。

ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。

\(a = q \times b + r \quad \quad (1)\)

ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。

\(m \times a' = q \times m \times b' + r \quad \quad (2)\)

左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。

\(m \leq m' \quad \quad (3)\)

次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。

\(a = q \times m' \times b'' + m' \times r' \quad \quad (4)\)

右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。

\(m' \leq m \quad \quad (5)\)

式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。

あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。

プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。

リスト : 最大公約数と最小公倍数

-module(gcd).
-export([gcd/2, lcm/2]).

# 最大公約数
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

% 最小公倍数
lcm(A, B) -> A * B div gcd(A, B).

関数 gcd/2 は引数 A と B の最大公約数を、関数 lcm/2 は最小公倍数を求めます。B が 0 の場合は A を返します。これが再帰呼び出しの停止条件になります。そうでなければ gcd を再帰呼び出しして、B と A rem B の最大公約数を求めます。上記リストはユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。それから、整数 A と B の最小公倍数は A * B / gcd(A, B) で求めることができます。

それでは実行してみましょう。

> gcd:gcd(42, 36).
6
> gcd:gcd(36, 42).
6
> gcd:gcd(15, 70).
5
> gcd:gcd(70, 15).
5
> gcd:lcm(5, 7).
35
> gcd:lcm(14, 35).
70

●組み合わせの数

次は組み合わせの数を求めるプログラムを作ってみましょう。ここでは組み合わせの数を \({}_n \mathrm{C}_r\) と表記します。\({}_n \mathrm{C}_r\) を求めるには、次の公式を使えば簡単です。

\( {}_n \mathrm{C}_r = \dfrac{n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)}{1 \times 2 \times 3 \times \cdots \times r} = \dfrac{n!}{r! \times (n-r)!} \)

皆さんお馴染みの公式ですね。ところが、整数値の範囲が限られているプログラミング言語では、この公式を使うと乗算で桁あふれを起こす恐れがあります。Erlang は多倍長演算をサポートしているので、桁あふれを心配する必要はありません。

この公式をそのままプログラムすることもできますが、次の式を使うともっと簡単にプログラムできます。

\( {}_n \mathrm{C}_r = \begin{cases} 1 & if \ r = 0 \\ 1 & if \ r = n \\ \dfrac{{}_n \mathrm{C}_{r-1} \times (n - r + 1)}{r} \quad & if \ r \gt 0 \end{cases} \)

この式は \({}_n \mathrm{C}_r\) と \({}_n \mathrm{C}_{r-1}\) の関係を表しています。あとは階乗と同じように、再帰定義を使って簡単にプログラムできます。次のリストを見てください。

リスト : 組み合わせの数を求める

-module(comb).
-export([combination_number/2]).

combination_number(N, N) -> 1;
combination_number(_, 0) -> 1;
combination_number(N, R) -> combination_number(N, R - 1) * (N - R + 1) div R.

とても簡単ですね。ところで、整数値の範囲が限られているプログラミング言語では、この方法でも桁あふれする場合があるので注意してください。

それでは実行してみましょう。

> comb:combination_number(2, 0).
1
> comb:combination_number(2, 1).
2
> comb:combination_number(2, 2).
1
> comb:combination_number(4, 0).
1
> comb:combination_number(4, 1).
4
> comb:combination_number(4, 2).
6
> comb:combination_number(4, 3).
4
> comb:combination_number(4, 4).
1
> comb:combination_number(5, 3).
10
> comb:combination_number(10, 5).
252

●ハノイの塔

再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は棒に刺さっている円盤を、次に示す規則に従ってほかの棒にすべて移動させる問題です。

1 回に 1 枚の円盤しか動かせない。
小さな円盤の上に大きな円盤を乗せることはできない。
最初は 1 本の棒に、大きい円盤の上に小さな円盤が順番に刺さっている。

ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、5 番目の円盤を左から中央の棒に移す場合、その上の 4 枚の円盤を右の棒に移しておけば、5 番目の円盤を動かすことができるようになります。そして、5 番目の円盤を中央に移したら、右の棒に移した 4 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように表現できます。

n - 1 枚の円盤を左から右に移す
n 枚目の円盤を左から中央へ移す
n - 1 枚の円盤を右から中央へ移す

これを素直にプログラムすると次のようになります。

リスト : ハノイの塔

-module(hanoi).
-export([hanoi/4]).

hanoi(1, From, To, _) -> io:write({From, to, To});
hanoi(N, From, To, Via) ->
    hanoi(N - 1, From, Via, To),
    io:write({From, to, To}),
    hanoi(N - 1, Via, To, From).

引数 N は動かす円盤の枚数、From は移動元の棒、To は移動先の棒、Via は残りの棒を示します。円盤の枚数が 1 枚の場合は簡単です。From にある円盤を To へ移すだけです。これが再帰の停止条件になります。io:write() は標準出力にデータを出力する関数です。このプログラムでは移動手順をタプルで示しています。

2 番目の規則は、円盤が複数枚ある場合に対応します。hanoi を再帰呼び出しして、N - 1 枚の円盤を棒 Via に移動します。棒 From に残った円盤は 1 枚なので、それを棒 To に移動します。これを write で出力します。最後に、棒 Via に移した円盤を棒 To に移動します。ここでも再帰呼び出しが行われます。

これで完成です。それでは実行してみましょう。

> hanoi:hanoi(3, a, b, c).
{a,to,b}{a,to,c}{b,to,c}{a,to,b}{c,to,a}{c,to,b}{a,to,b}ok
> hanoi:hanoi(4, a, b, c).
{a,to,c}{a,to,b}{c,to,b}{a,to,c}{b,to,a}{b,to,c}{a,to,c}{a,to,b}{c,to,b}{c,to,a}
{b,to,a}{c,to,b}{a,to,c}{a,to,b}{c,to,b}ok

●format

きれいに印字したい場合はモジュール io に用意されている関数 format を使いましょう。この関数はＣ言語の関数 printf や Common Lisp の関数 format に相当する働きをします。format は表示に関していろいろな指定を行うことができますが、その分使い方が少しだけ複雑になります。

format('書式文字列', 引数リスト).

第 1 引数は書式文字列で、出力に関する様々な指定を行います。これにはアトムを使います。format はアトムをそのまま出力するのですが、文字列の途中にチルダ ~ が表れると、その後ろの文字を変換指示子として理解し、引数リストのデータをその指示に従って表示します。よく使われる指示子を表に示します。

表：foramt の変換指示子
指示子	機能
w	項を Erlang の形式で表示する
p	項を整形して表示する
s	文字列を表示する
e, f, g	浮動小数点数を表示 (Ｃ言語 printf と同じ)
b	整数を表示 (2 - 32 までの基数を指定する)
n	改行
t	タブ
~	チルダ

簡単な例を示しましょう。

> io:format('~b ~.8b ~.16b ~n', [256, 256, 256]).
256 400 100
ok

書式文字列の中には、複数の変換指示子を設定することができます。チルダの前までは、そのまま文字を表示します。チルダ ~ の次の文字 b, n が変換指示子です。b は整数値を表示する指示子で、n は改行を表す指示子です。b の場合、~ の後ろに "ドット + N" を指定すると、整数値を N 進数で表示することができます。与えるデータと指示子の数が合わないとエラーになります。ご注意くださいませ。

アトムを表示する場合は w または p 変換指示子を使い、チルダを出力したい場合は ~~ と続けて書きます。このほかにも、浮動小数点数を表示する指示子などがあります。それらの機能は、必要になった時点で説明することにしましょう。

format を使ってプログラムを書き換えると、次のようになります。

リスト：ハノイの塔

hanoi1(1, From, To, _) -> io:format('~w to ~w~n', [From, To]);
hanoi1(N, From, To, Via) ->
        hanoi1(N - 1, From, Via, To),
        io:format('~w to ~w~n', [From, To]),
        hanoi1(N - 1, Via, To, From).

それでは実行してみましょう。

> hanoi:hanoi1(3, a, b, c).
a to b
a to c
b to c
a to b
c to a
c to b
a to b
ok

●パスカルの三角形

もう一つ簡単な例題として、関数 combination_number/2 を使って「パスカルの三角形」を作ってみましょう。次の図を見てください。


                         図 : パスカルの三角形

パスカルの三角形は、左側の図のように両側がすべて 1 で、内側の数はその左上と右上の和になっています。これは \((a + b)^n\) を展開したときの各項の係数を表しています。そして、その値は右側の図のように組み合わせの数 \({}_n \mathrm{C}_r\) に対応しています。

きれいな三角形にはなりませんが、パスカルの三角形を表示するプログラムを示します。

リスト : パスカルの三角形

pascal_sub(N, 0) -> io:format('~w~n', [combination_number(N, 0)]);
pascal_sub(N, R) -> io:format('~w ', [combination_number(N, R)]), pascal_sub(N, R - 1).

pascal(0) -> pascal_sub(0, 0);
pascal(N) -> pascal(N - 1), pascal_sub(N, N).

関数 pascal/1 は N + 1 段のパスカルの三角形を表示します。関数 pascal_sub/2 は (N, 0) から (N, N) までの combination_number/2 の値を表示します。pascal(N) は pascal(N - 1) を再帰呼び出ししてから pascal_sub(N, N) を呼び出しているところに注意してください。これにより 0 から順番に値が表示されます。pascal_sub は簡単ですね。format で combination_number(N, R) の値を表示するだけです。

それでは実行結果を示します。

> comb:pascal(10).
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
ok

●相互再帰

相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。Erlang は相互再帰している関数でも簡単に定義することができます。次のリストを見てください。

リスト : 相互再帰

-module(recur).
-export([foo/1, bar/1]).

foo(0) -> true;
foo(N) -> bar(N - 1).
bar(0) -> false;
bar(N) -> foo(N - 1).

このプログラムは関数 foo/1 と bar/1 が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。

> recur:foo(10).
true
> recur:foo(11).
false
> recur:bar(11).
true
> recur:bar(12).
false

結果を見ればおわかりのように、foo は N が偶数のときに真を返し、bar は N が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。

●末尾再帰

再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。

ML や Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」^[*1] といいます。なかには Scheme のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。

たとえば、階乗を計算する関数 fact/1 を思い出してください。最初に定義した fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。

リスト : 階乗 (末尾再帰)

facti(0, A) -> A;
facti(N, A) -> facti(N - 1, N * A).

facti(N) when N > 0 -> facti(N, 1).

> fact:facti(9).
362880
> fact:facti(10).
3628800
> fact:facti(11).
39916800

関数 facti/2 を見てください。2 番目の節で facti を再帰呼び出しして返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 A の使い方がポイントです。

たとえば facti(4, 1) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 A に記憶しているのです。facti の呼び出し (末尾再帰最適化を適用する前の動作) をトレースすると次のようになります。

facti(4, 1)
  facti(3, 4)
    facti(2, 12)
      facti(1, 24)
        facti(0, 24)
        => a の値 24 を返す
      => 24
    => 24
  => 24
=> 24


  図 : facti() の動作

引数 A には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。

純粋な関数型言語の場合、while や for などの繰り返しがないプログラミング言語があります。Erlang や論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を用いてプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

-- note --------
[*1] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。詳しい説明は拙作のページ Scheme Programming 関数型電卓プログラム fncalc の作成 (4) 末尾再帰とは？をお読みください。

●フィボナッチ関数の高速化

今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ関数を取り上げます。フィボナッチ関数の定義は二重再帰になっているので、そのままプログラムすると時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。次のリストを見てください。

リスト : フィボナッチ関数(末尾再帰)

fiboi(0, A, _) -> A;
fiboi(N, A, B) -> fiboi(N - 1, B, A + B).

fibo1(N) when N > 0 -> fiboi(N, 0, 1).

累算変数 A と B の使い方がポイントです。現在のフィボナッチ数を変数 A に、ひとつ前の値を変数 B に格納しておきます。あとは A と B を足し算して、新しいフィボナッチ数を計算すればいいわけです。関数 fiboi/2 の呼び出しを図に示すと、次のようになります。

fiboi(5, 0, 1)
  fiboi(4, 1, 1)
    fiboi(3, 1, 2)
      fiboi(2, 2, 3)
        fiboi(1, 3, 5)
          fiboi(0, 5, 8)
          => A の値 5 を返す
        => 5
      => 5
    => 5
  => 5
=> 5

図 : 関数 fiboi/2 の呼び出し

二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、プログラムを高速に実行することができます。

それでは実際に試してみましょう。

> timer:tc(fibo, fibo, [38]).
{1859027,39088169}

> timer:tc(fibo, fibo1, [38]).
{0,39088169}

> timer:tc(fibo, fibo1, [100]).
{31000,354224848179261915075}

実行環境 : Windows 10, Intel Core i5-6200U 2.30GHz

timer:tc/3 が返す値はタプルで、最初の要素が計測した時間 (μsec) で、二番目の要素が関数の返り値です。fibo(38) を計算するのに約 2 秒ほどかかりますが、fibo1(38) ならば瞬時に終わります。fibo1(100) でも高速に計算することができます。

末尾再帰 (繰り返し) は再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるのに、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムが一番だと思います。

●FizzBuzz 問題

最後に簡単な例題として FizzBuzz 問題を Erlang で解いてみましょう。FizzBuzz 問題は 1 から 100 までの値を表示するとき、3 の倍数のときは Fizz を、5 の倍数ときは Buzz を表示するというものです。FizzBuzz 問題の詳細については Fizz Buzz - Wikipedia をお読みください。

今回は fizz, buzz, fizzbuzz と小文字で表示することにします。プログラムは次のようになります。

リスト : FizzBuzz 問題 (fizzbuzz.erl)

-module(fizzbuzz).
-export([fizzbuzz/0]).

fizzbuzz(N) when N > 100 -> ok;
fizzbuzz(N) ->
    X = if
            N rem 15 == 0 -> fizzbuzz;
            N rem 3  == 0 -> fizz;
            N rem 5  == 0 -> buzz;
            true -> N
        end,
    io:format('~p ', [X]),
    fizzbuzz(N + 1).

fizzbuzz() -> fizzbuzz(1).

% 別解
check(N) when N rem 15 == 0 -> io:format('fizzbuzz ');
check(N) when N rem 3 == 0 -> io:format('fizz ');
check(N) when N rem 5 == 0 -> io:format('buzz ');
check(N) -> io:format('~p ', [N]).

fizzbuzz1(N) when N > 100 -> ok;
fizzbuzz1(N) -> check(N), fizzbuzz1(N + 1).

fizzbuzz1() -> fizzbuzz1(1).

fizzbuzz/1 も別解 fizzbuzz1/1 も難しいところはないと思います。それでは実行してみましょう。

> c(fizzbuzz).
{ok,fizzbuzz}
> fizzbuzz:fizzbuzz().
1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz 16 17 fizz 19 buzz fizz 22 23 fizz buzz 26 fizz 28 29 
fizzbuzz 31 32 fizz 34 buzz fizz 37 38 fizz buzz 41 fizz 43 44 fizzbuzz 46 47 fizz 49 buzz fizz 52 53 fizz buzz 56 
fizz 58 59 fizzbuzz 61 62 fizz 64 buzz fizz 67 68 fizz buzz 71 fizz 73 74 fizzbuzz 76 77 fizz 79 buzz fizz 82 83 
fizz buzz 86 fizz 88 89 fizzbuzz 91 92 fizz 94 buzz fizz 97 98 fizz buzz ok

正常に動作していますね。

初出 2011 年 10 月 2 日
改訂 2018 年 12 月 9 日

Functional Programming