関数定義の中で、その関数自身を呼び出すことを再帰呼び出し (recursive call) とか再帰定義 (recursive definition) といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではないのです。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん Lua の関数も再帰呼び出しが可能です。
再帰定義というと、Lisp / Scheme のような関数型言語の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックのひとつと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができます。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を図 5 に示します。
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。リスト 9 を見てください。
リスト 9 : 階乗
function fact(n)
if n == 0 then
return 1
else
return n * fact(n - 1)
end
end
関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しでプログラムできますが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合は、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
実行結果は次のようになります。
> for i = 0, 15 do print(fact(i)) end 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
それでは、再帰定義のポイントを説明しましょう。図 6 を見てください。
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│Call:1 │->│Call:2 │->│Call:3 │->│Call:4 │->│Call:5 │
│n:4 │ │n:3 │ │n:2 │ │n:1 │ │n:0 │
│value : 24│<-│value : 6 │<-│value : 2 │<-│value : 1 │<-│value : 1 │
└─────┘ └─────┘ └─────┘ └─────┘ └─────┘
図 6 : fact の再帰呼び出し（n:引数の値, value:返り値）
図 6 は関数 fact(4) の呼び出しを表したものです。最初の呼び出し (Call:1) では、引数 n の値は 4 なので n の値を 1 減らして fact を再帰呼び出しします。2 回目の呼び出しでは、引数 n の値に 3 が代入されます。ここで、最初に呼び出したときと、2 回目に呼び出したときでは、引数 n の値が違うことに注意してください。
関数の引数はローカル変数として扱われます。前回説明したように、ローカル変数には有効範囲（スコープ）があります。引数の場合、その関数が実行されている間だけ有効です。ローカル変数は関数呼び出しが行われるたびに新しく生成されて、そこに値が代入されます。そして、関数の実行が終了すると、生成されたローカル変数は廃棄されます。つまり、1 回目の呼び出しと 2 回目の呼び出しでは、引数 n は名前が同じでも異なる変数になるのです。ここが再帰呼び出しを理解するポイントの一つです。
プログラムを見ると変数 n は一つしかありませんが、再帰呼び出しが行われるたびに新しい変数 n が作られていくと考えてください。fact(4) を実行しているときの n は 4 であり、fact(3) を呼び出すときには、この n の値を書き換えるのではなく、新しい変数 n を用意して、そこに 3 を代入するのです。
同様に再帰呼び出しが行われ、5 回目の呼び出し (Call:5) で引数 n が 0 になります。このとき、if の then ブロックが実行され 1 が返されます。ここで再帰呼び出しが止まります。これを再帰呼び出しの停止条件といいます。ここが第 2 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Lua であればプログラムの実行は途中で停止します。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行しているあいだ、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*2] といいます。なかには Scheme のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。ちなみに Lua も末尾再帰最適化を行います。
たとえば、階乗を計算する関数 fact を思い出してください。リスト 9 の fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換するとリスト 10 になります。
リスト 10 : 階乗（末尾再帰）
function facti(n, a)
if n == 0 then
return a
else
return facti(n - 1, a * n)
end
end
最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば facti(4, 1) を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算します。このとき、計算の途中経過を引数 a に記憶しているのです。facti の呼び出し (末尾再帰最適化を適用する前の動作) を図 7 に示します。
facti(4, 1) | facti(3, 4) | | facti(2, 12) | | | facti(1, 24) | | | | facti(0, 24) | | | | => a の値 24 を返す | | | => 24 | | => 24 | => 24 => 24 図 7 : facti のトレース
引数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。
関数型言語の場合、while文 や for文 などの繰り返しがないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
実行結果を示します。
> for i = 0, 15 do print(facti(i, 1)) end 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
ところで、末尾再帰を繰り返しに変換することは簡単です。実際に関数 facti を繰り返しに変換すると次のようになります。
リスト 11 : 階乗 (繰り返し)
function fact_loop(n)
local a = 1
while n > 1 do
a = a * n
n = n - 1
end
return a
end
手続き型言語に慣れている方は、こちらのプログラムのほうがわかりやすいかもしれません。実行結果は次のようになります。
> for i = 0, 15 do print(fact_loop(i)) end 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです
もう一つ簡単な数値計算の例を示しましょう。フィボナッチ関数は階乗と同様に再帰的に定義される関数です。
フィボナッチ関数も再帰呼び出しを使えば簡単にプログラムできます。
リスト 12 : フィボナッチ関数
function fibo(n)
if n == 0 or n == 1 then
return n
else
return fibo(n - 1) + fibo(n - 2)
end
end
> for i = 0, 16 do print(fibo(i)) end 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
関数 fibo は階乗の計算を行う関数 fact とは違い、自分自身を 2 回呼び出しています。これを「二重再帰」といいます。fibo の呼び出しをトレースすると下図のようになります。
fibo(5) ┬ fibo(4) ┬ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │ │ │
│ │ │ └ fibo(0)
│ │ └ fibo(1)
│ └ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
│
└ fibo(3) ┬ fibo(2) ┬ fibo(1)
│ │
│ └ fibo(0)
└ fibo(1)
図 9 : 関数 fibo のトレース
同じ値を何回も求めているため、fibo の効率はとても悪いのです。この場合、二重再帰を「末尾再帰」に変換すると高速化することができます。そこで累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。プログラムは次のようになります。
リスト 13 : フィボナッチ関数（末尾再帰）
function fiboi(n, a1, a2)
if n < 1 then
return a1
else
return fiboi(n - 1, a1 + a2, a1)
end
end
> for i = 0, 15 do print(fiboi(i, 0, 1)) end 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
累算変数 a1 と a2 の使い方がポイントです。現在のフィボナッチ数を変数 a1 に、その次の値を変数 a2 に格納しておきます。あとは a1 と a2 を足し算して、新しいフィボナッチ数を計算すればいいわけです。fiboi の呼び出しを下図に示します。
fiboi(5) | fibo(4, 0, 1) | | fiboi(3, 1, 1) | | | fiboi(2, 1, 2) | | | | fiboi(1, 2, 3) | | | | | fiboi(0, 3, 5) | | | | | => a1 の値 3 を返す | | | | => 3 | | | => 3 | | => 3 | => 3 => 3 図 10 : 関数 fiboi のトレース
二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。もちろん、末尾再帰になっているので、末尾再帰最適化を行う処理系では、プログラムをより高速に実行することができます。
ちなみに、関数 fiboi を繰り返しに変換すると次のようになります。
リスト 14 : フィボナッチ関数（繰り返し）
function fibo_loop(n)
local a1, a2 = 0, 1
while n > 0 do
a1, a2 = a1 + a2, a1
n = n - 1
end
return a1
end
> for i = 0, 16 do print(fibo_loop(i)) end 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
再帰といえば忘れてはいけないのが「ハノイの塔」でしょう。ハノイの塔は、棒に刺さっている大きさが異なる複数の円盤を、次の規則に従ってほかの棒に移動させるパズルです。
ハノイの塔は、再帰を使えば簡単に解ける問題です。たとえば、3 枚の円盤が左の棒に刺さっているとします。この場合、いちばん大きな円盤を中央の棒に移すには、その上の 2 枚の円盤を右の棒に移しておけばいいですね。いちばん大きな円盤を中央に移したら、右の棒に移した 2 枚の円盤を中央の棒に移すことを考えればよいわけです。したがって、n 枚の円盤を左から中央の棒に移すプログラムは次のように定義できます。
これを素直にプログラムすると次のようになります。
リスト 15 : ハノイの塔
function hanoi(n, from, to, via)
if n == 1 then
print(from .. " => " .. to)
else
hanoi(n - 1, from, via, to)
print(from .. " => " .. to)
hanoi(n - 1, via, to, from)
end
end
n は動かす円盤の枚数、from は移動元の棒、to は移動先の棒、via は残りの棒を示します。棒は文字列で表します。円盤の枚数が 1 枚の場合は簡単ですね。from にある円盤を to へ移すだけです。これが再帰の停止条件になります。この動作を print で表示します。
円盤が複数枚ある場合、from にある円盤の n - 1 枚を via に移します。この処理は hanoi を再帰呼び出しすればいいですね。次に、残りの 1 枚を to に移して print で表示します。そして、via に移した n - 1 枚の円盤を to に移します。この処理も hanoi を再帰呼び出しするだけです。
これでプログラムは完成です。それでは実行してみましょう。
> hanoi(3, "A", "B", "C") A => B A => C B => C A => B C => A C => B A => B
このように、再帰定義を使うとハノイの塔を簡単に解くことができます。