再帰定義
前回は関数の基本的な使い方について説明しました。今回は「再帰定義」について説明します。
関数定義の中で、その関数自身を呼び出すことを「再帰呼び出し (recursive call)」とか「再帰定義 (recursive definition)」といいます。関数の定義に自分自身を使うことができるなんて、何か特別な仕掛があるのではないかと思われるかもしれません。ところが、再帰定義は特別なことではありません。大昔のプログラミング言語ならばいざしらず、今では再帰呼び出しができないプログラミング言語のほうが珍しいでしょう。もちろん、Ｃ++の関数も再帰呼び出しが可能です。
●再帰定義の基本
再帰定義というと、Lisp / Scheme のような「関数型言語」の専売特許だと思われている方もいるでしょう。実際、Ｃ言語などの手続き型言語では、再帰定義を難しいテクニックの一つと思い込んでしまい、初心者の方は避けて通ることが多いように思います。再帰定義は、今まで説明した関数の呼び出しとまったく同じなので、難しく考える必要はありません。慣れるまでちょっと苦労するかもしれませんが、ポイントさえつかめば簡単に使いこなすことができるようになります。
まずは簡単な例を見てみましょう。階乗を計算するプログラムです。階乗の定義を下図に示します。
図 : 階乗の定義
階乗の定義からわかるように、n の階乗は n - 1 の階乗がわかれば求めることができます。実は、これをそのままプログラムすることができます。次のリストを見てください。
リスト : 階乗 (fact.cpp)
#include <iostream>
using namespace std;
int fact(int n)
{
if (n == 0) {
return 1;
} else {
return n * fact(n - 1);
}
}
int main()
{
for (int i = 0; i < 13; i++) {
cout << i << "! = " << fact(i) << endl;
}
}
$ clang++ fact.cpp $ ./a.out 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600
関数 fact は引数 n が 0 であれば 1 を返し、そうでなければ n * fact(n - 1) の計算結果を返します。fact の定義で fact 自身を呼び出しています。これが再帰呼び出しです。
階乗と同じように再帰定義で表されるアルゴリズムはたくさんあります。階乗の計算は簡単なので、再帰呼び出しを使わなくても繰り返しで簡単にプログラムすることができます。ですが、再帰で定義されるアルゴリズムのなかには、繰り返しに変換すると複雑なプログラムになってしまうものがあります。
このような場合、素直に再帰定義を使ったほうがわかりやすいプログラムになり、間違いを犯す危険性が少なくなります。難しいアルゴリズムでも、再帰定義を使うと簡単にプログラムできる場合もあるのです。
●再帰定義のポイント
それでは、再帰定義のポイントを説明しましょう。次の図を見てください。
図 : fact の再帰呼び出し (n:引数の値, value:返り値)
上図は関数 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 のポイントです。
停止条件がなかったり、あってもその条件を満たさない場合、関数を際限なく呼び出すことになり、Unix 系 OS では Segmentation fault が発生して、プログラムの実行は中止されます。再帰呼び出しを使う場合は、この停止条件に十分注意してください。
fact(0) は 1 を返して fact(1) に戻ります。fact(1) を実行している間、引数 n の値は 1 です。したがって、fact(1) の返り値は 1 * 1 を計算して 1 となります。あとは同様に、再帰呼び出しした関数の返り値を使って値を計算し、最後に fact(4) の値 24 を求めることができます。
●ユークリッドの互除法
もう一つ簡単な数値計算の例を示しましょう。負でない整数 a と b の最大公約数を求めるプログラムを「ユークリッド (Euclid) の互除法」で作ります。まず最初に、ユークリッドの互除法を説明します。
負でない整数 \(a, b \ (a \gt b)\) で、\(a\) を \(b\) で割った余りを \(r\) とする。
このとき、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しい。
ユークリッドの互除法は簡単に証明できます。\(a\) と \(b\) の割り算を式 (1) で表します。
ここで、\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a = m \times a', \ b = m \times b'\) となります。すると、式 (1) は式 (2) で表すことができます。
左辺は \(m\) で割り切れるので、右辺も \(m\) で割り切れる必要があります。\(q \times m \times b'\) は \(m\) で割り切れるので、\(r\) も \(m\) で割り切れることになります。つまり、\(m\) は \(b\) と \(r\) の公約数であることがわかります。\(b\) と \(r\) の最大公約数を \(m'\) とすると、式 (3) が成り立ちます。
次に、\(b = m' \times b'', \ r = m' \times r' \)として式 (1) に代入すると、式 (4) が成り立ちます。
右辺は \(m'\) で割り切れるので、\(a\) も \(m'\) で割り切れる必要があります。つまり、\(m'\) は \(a\) と \(b\) の公約数であることがわかります。したがって、式 (5) が成り立ちます。
式 (3) と (5) より \(m = m'\) となり、\(a\) と \(b\) の最大公約数は \(b\) と \(r\) の最大公約数に等しいことが証明されました。
あとは b を a とし、r を b にして同じ計算をすればいいわけです。この計算を繰り返し行うと、a と b はどんどん小さくなっていき、r = 0 になったときの b が最大公約数になります。
プログラムは再帰定義を使って簡単に作ることができます。次のリストを見てください。
リスト : 最大公約数 (gcd.cpp)
#include <iostream>
using namespace std;
// 最大公約数
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
// 最小公倍数
int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
int main()
{
cout << gcd(42, 30) << endl;
cout << gcd(15, 70) << endl;
cout << lcm(5, 7) << endl;
cout << lcm(14, 35) << endl;
}
関数 gcd は引数 a と b の最大公約数を求めます。b が 0 の場合は a を返します。これが再帰呼び出しの停止条件になります。そうでなければ、gcd を再帰呼び出しして b と a % b の最大公約数を求めます。リストはユークリッドの互除法の定義をそのままプログラムしただけです。このように、再帰定義を使うと簡単にプログラムを作ることができます。
また、整数 a と b の最小公倍数 (lcm) は a * b / gcd(a, b) で求めることができます。それでは実行例を示します。
$ clang++ gcd.cpp $ ./a.out 6 5 35 70
●相互再帰と関数プロトタイプ
相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。Ｃ++はコンパイル型のプログラミング言語なので、foo から bar を呼び出すとき、bar が未定義の場合はコンパイルでエラーが発生します。次のリストを見てください。
リスト : 相互再帰 (sample40.cpp)
#include <iostream>
using namespace std;
// プロトタイプ宣言が必要
// bool bar(int n);
bool foo(int n)
{
return n == 0 ? true : bar(n - 1);
}
bool bar(int n)
{
return n == 0 ? false : foo(n - 1);
}
int main()
{
cout << foo(10) << endl;
cout << foo(11) << endl;
cout << bar(20) << endl;
cout << bar(21) << endl;
}
$ clang++ sample40.cpp
sample40.cpp:9:26: error: use of undeclared identifier 'bar'
return n == 0 ? true : bar(n - 1);
^
1 error generated.
Ｃ言語の場合、定義されていない関数があると、int を返す関数とみなしてコンパイルしますが、Ｃ++ではコンパイルエラーになります。Ｃ/Ｃ++は事前に関数の引数の型や返り値の型を宣言することができます。これを「関数プロトタイプ (function prototype)」といいます。プロトタイプは関数定義から本体を省略した形式になります。プロトタイプの構文を示します。
データ型 関数名(データ型 仮引数, ...);
プロトタイプでは仮引数を省略して、データ型だけ記述してもかまいません。sample40.cpp では関数 foo の前にプロトタイプ宣言 bool bar(int n); を追加すると正常にコンパイルすることができます。
標準ライブラリ関数を呼び出す場合、Ｃ/Ｃ++ではヘッダファイルをインクルードしますが、このヘッダファイルの中にライブラリ関数のプロトタイプが宣言されています。ライブラリ関数を呼び出すときは、ヘッダファイルをインクルードすることをお忘れなく。
このプログラムは関数 foo と bar が相互再帰しています。foo と bar が何をしているのか、実際に動かしてみましょう。
$ clang++ sample40.cpp $ ./a.out 1 0 0 1
結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。
●末尾再帰と繰り返し
再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme [*2] のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。
たとえば、階乗を計算する関数 fact を思い出してください。fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。
リスト : 階乗 (末尾再帰, facti.cpp)
#include <iostream>
using namespace std;
int facti(int n, int a = 1)
{
if (n == 0) {
return a;
} else {
return facti(n - 1, a * n);
}
}
int main()
{
for (int i = 0; i < 13; i++) {
cout << i << "! = " << facti(i) << endl;
}
}
$ clang++ facti.cpp $ ./a.out 0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800 11! = 39916800 12! = 479001600
最後の再帰呼び出しで、関数 facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。
たとえば facti(4) を実行すると、このプログラムでは 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文 などの繰り返し文がないプログラミング言語があります。また、論理型言語 Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。
ところで、最大公約数を求める関数 gcd は末尾再帰になっています。Ｃ/Ｃ++の場合、末尾再帰最適化は規格の範囲外で、Ｃ/Ｃ++コンパイラの最適化に依存する機能になりますが、私たちが繰り返しに変換するのは簡単です。次のリストを見てください。
リスト : 最大公約数を求める (gcdi.c)
#include <iostream>
using namespace std;
// 最大公約数 (繰り返し版)
int gcdi(int a, int b)
{
while (b > 0) {
int c = a;
a = b;
b = c % b;
}
return a;
}
int main()
{
cout << gcdi(42, 30) << endl;
cout << gcdi(15, 70) << endl;
}
$ clang++ gcdi.cpp $ ./a.out 6 5
関数 gcdi は引数 a, b の値を書き換えることで最大公約数を求めています。再帰定義を使ったプログラムはユークリッドの互除法であることがすぐにわかりますが、繰り返しに変換するとプログラムは少しわかりにくくなると思います。
繰り返しは再帰定義に比べると実行速度やメモリの消費量など効率の点で有利です。このため、何がなんでも繰り返しでプログラムしようとする方もいるでしょう。ところが、再帰定義を使うと簡単にプログラムできるが、繰り返しではとても複雑なプログラムになってしまう場合もあります。したがって、とくに問題がなければ再帰定義を繰り返しに変換する必要はないと思います。複雑なプログラムは、しばらくたつと書いた本人でさえ理解できなくなることがよくあります。わかりやすいプログラムがいちばんです。
[*1] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。興味のある方は Appendix; 末尾最適化 をお読みください。
[*2] Scheme は Lisp の方言の一つで、熱心なユーザが多いプログラミング言語です。
●めのこ平方の改良
それでは再帰定義を使って前回作成した「めのこ平方」のプログラムを改良してみましょう。ポイントは、整数を 2 桁ずつ分けて計算していくことです。次の図を見てください。
整数 6789 を 67 と 89 に分ける 1 + 3 + ... + 15 = 82 < 67 両辺を 100 倍すると 802 < 6700 < 6789 802 = 1 + 3 + ... + 159 (= 2 * 80 - 1) 161 + 163 < (6789 - 6400 = 389) < 161 + 163 + 165
整数 6789 を 67 と 89 に分けます。最初に 67 の平方根を求めます。この場合は 8 になり、82 < 67 を満たします。次に、この式を 100 倍します。すると、802 < 6700 になり、6700 に 89 を足した 6789 も 802 より大きくなります。802 は 1 から 159 までの奇数の総和であることはすぐにわかるので、6789 - 6400 = 389 から奇数 161, 163, ... を順番に引き算していけば 6789 の平方根を求めることができます。
プログラムは次のようになります。
リスト : めのこ平方 (sqrtint.cpp)
#include <iostream>
using namespace std;
int sqrt_int(int n, int m)
{
while (n >= m) {
n -= m;
m += 2;
}
return m / 2;
}
int sqrt_int(int n)
{
if (n > 100)
return sqrt_int(n, 1);
else {
int m = 10 * sqrt_int(n / 100);
return sqrt_int(n - m * m, 2 * m + 1);
}
}
int main(void)
{
cout << sqrt_int(1000000) << endl;
cout << sqrt_int(123456789) << endl;
cout << sqrt_int(1234567890) << endl;
}
$ clang++ sqrtint.cpp $ ./a.out 1000 11111 35136
1 引数の sqrt_int を sqrt_int/1, 2 引数の関数を sqrt_int/2 と記述することにします。sqrt_int/1 は n の平方根の整数部分を求めます。n が 100 未満の場合は sqrt_int/2 で平方根を求めます。これが再帰呼び出しの停止条件になります。n が 100 以上の場合は、n の下位 2 桁を取り除いた値 (n / 100) の平方根を sqrt_int/1 で求め、その値を 10 倍して変数 m にセットします。そして、sqr_int/2 で n - m * m から奇数 2 * m + 1, 2 * m + 3 ... を順番に引き算していって n の平方根を求めます。
●順列の生成
最後に「順列 (permutation)」を生成するプログラムを作ってみましょう。異なる n 個の順列の総数は、n の階乗 (n!) 通りあります。たとえば 4 つの整数 1, 2, 3, 4 の順列は 24 通りあります。これをすべて求めるプログラムを作ります。最初に、繰り返しでプログラムしてみましょう。次のリストを見てください。
リスト : 順列の生成 (繰り返し版)
#include <iostream>
using namespace std;
const int N = 4;
int buff[N]; // 順列を格納する配列
bool used[N + 1]; // 使用した数字
int main()
{
// 一つ目の数字を選ぶ
for (int n1 = 1; n1 <= N; n1++) {
if (used[n1]) continue;
buff[0] = n1;
used[n1] = true;
// 二つ目の数字を選ぶ
for (int n2 = 1; n2 <= N; n2++) {
if (used[n2]) continue;
buff[1] = n2;
used[n2] = true;
// 三つ目の数字を選ぶ
for (int n3 = 1; n3 <= N; n3++) {
if(used[n3]) continue;
buff[2] = n3;
used[n3] = true;
// 四つ目の数字を選ぶ
for (int n4 = 1; n4 <= N; n4++) {
if (used[n4]) continue;
buff[3] = n4;
used[n4] = true;
// 順列を出力
for(int i = 0; i < N; i++)
cout << buff[i] << " ";
cout << endl;
used[n4] = false;
}
used[n3] = false;
}
used[n2] = false;
}
used[n1] = false;
}
}
少々長いリストですが、やっていることは簡単です。選んだ数字は配列 buff に格納し、配列 used に印 (true) をつけておきます。あとは used に印がついていない数字を選んでいくだけです。数字を 4 つ選んだら順列 buff を出力します。
そして、次の順列を発生させるため、選んだ数字に対応する used に false をセットします。選ぶ数字がなくなったならば、もう一つ前のループに後戻りします。このように、後戻りしながら数字を選んでいくことで、24 通りの順列を生成することができます。
それでは実行してみましょう。
$ clang++ perm0.cpp $ ./a.out 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
このプログラムは 4 重のループですが、けっこうたいへんですね。もし、1 から 10 の順列を発生させるとなると、10 重のループになってしまいます。ところが、再帰定義を使うともっと簡単にプログラムを作ることができます。次のリストを見てください。
リスト : 順列の生成 (再帰版)
#include <iostream>
using namespace std;
const int N = 8;
int buff[N]; // 順列を格納する配列
bool used[N + 1]; // 使用した数字
// 順列の表示
void print_perm(int m)
{
for (int i = 0; i < m; i++) cout << buff[i] << " ";
cout << endl;
}
void perm(int m, int n)
{
if (n == m)
print_perm(m);
else
for (int i = 1; i <= m; i++) {
if (used[i]) continue;
buff[n] = i;
used[i] = true;
perm(m, n + 1);
used[i] = false;
}
}
int main()
{
perm(3, 0);
perm(4, 0);
}
関数 perm は、1 から m までの順列を生成します。考え方は繰り返し版と同じで、数字を選んで buff にセットし、used に印 (true) をつけます。あとは印のついていない数字を選んでいけばいいのです。最初の呼び出しで 1 つの数字を選び、次の再帰呼び出しで 2 つめの数字を選びます。このように、n 重のループが n 回の再帰呼び出しに対応するわけです。
たとえば、n 番目の数字を選び順列を出力したら、n 番目の再帰呼び出しが終了し、n - 1 番目の再帰呼び出しに戻ります。その後は選んだ数字の印を消して、新しい数字を選びます。もしも、選ぶ数字がなければ、n - 2 番目の再帰呼び出しに戻り、n - 2 番目の数字を選び直します。これで 1 から m までの順列をすべて生成することができます。
それでは実行してみましょう。
$ clang++ perm1.cpp $ ./a.out 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1
このように 3! = 6 通りと 4! = 24 通りの順列をすべて求めることができます。
●Appendix: 末尾最適化
末尾再帰についてもう少し詳しく説明しましょう。末尾再帰の「末尾」とは、関数の最後で行われる処理のことです。とくに末尾で関数を呼び出すことを「末尾呼び出し (tail call)」といいます。関数を呼び出す場合、返ってきたあとに行う処理のため、必要な情報を保存しておかなければいけません。ところが、末尾呼び出しはそのあとに実行する処理がありません。呼び出したあと元に戻ってくる必要さえないのです。
このため、末尾呼び出しはわざわざ関数を呼び出す必要はなく、アセンブリ言語のような低水準のレベルではジャンプ命令に変換することができます。これを「末尾呼び出し最適化 (tail call optimization)」とか「末尾最適化」といいます。とくに末尾再帰は末尾で自分自身を呼び出しているので、関数の中で繰り返しに変換することができます。
また、相互再帰やもっと複雑な再帰呼び出しの場合でも、末尾最適化を適用することで、繰り返しに変換できる場合もあります。このように、再帰プログラムを繰り返しに変換してから実行することを「末尾再帰最適化 (tail recursion optimization)」といいます。厳密にいうと末尾最適化なのですが、一般的には末尾再帰最適化と呼ばれることが多いようです。
Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰最適化を行う処理系があります。なかには Scheme のように、言語仕様に末尾最適化を行うことを明記しているプログラミング言語もあります。最近は、Ｃ/Ｃ++ (gcc, g++, clang, clang++ など) でも末尾最適化が可能になっています。
簡単な例を示しましょう。1 から n までの総和を末尾再帰で求めます。
リスト : 1 から n までの総和 (sample41.cpp)
#include <iostream>
using namespace std;
double sum(int n, double a = 0)
{
if (n == 0) {
return a;
} else {
return sum(n - 1, a + n);
}
}
int main()
{
int i = 10000;
int j = 0;
for (; j < 6; i *= 2, j++) {
cout << i << ", " << sum(i) << endl;
}
}
関数 sum は末尾再帰になっています。clang++ の場合、最適化オプション -O を指定すると末尾最適化が行われます。-O を指定しないと最適化は行われません。なお、g++ で末尾最適化を有効にするには -O2 を指定してください。
実行結果を示します。
$ clang++ sample41.cpp $ ./a.out 10000, 5.0005e+07 20000, 2.0001e+08 40000, 8.0002e+08 80000, 3.20004e+09 160000, 1.28001e+10 Segmentation fault $ clang++ -O sample41.cpp $ ./a.out 10000, 5.0005e+07 20000, 2.0001e+08 40000, 8.0002e+08 80000, 3.20004e+09 160000, 1.28001e+10 320000, 5.12002e+10
このように、-O を指定しないとスタックオーバーフローにより Segmentation fault が発生しますが、-O を指定すると末尾最適化によりスタックオーバーフローせずに総和を計算することができます。
また、次のような相互再帰でも最適化することができます。
リスト : 相互再帰 (sample42.cpp)
#include <iostream>
using namespace std;
// 関数宣言
int odd(int);
int even(int);
int even(int n)
{
if (n == 0) {
return 1;
} else {
return odd(n - 1);
}
}
int odd(int n)
{
if (n == 0) {
return 0;
} else {
return even(n - 1);
}
}
int main()
{
int i, j;
for (j = 0, i = 20000; j < 5; j++, i *= 2) {
cout << i << ", " << even(i) << endl;
cout << i << ", " << odd(i) << endl;
}
}
実行結果は次のようになります。
$ clang++ sample42.cpp $ ./a.out 20000, 1 20000, 0 40000, 1 40000, 0 80000, 1 80000, 0 160000, 1 160000, 0 Segmentation fault $ clang++ -O sample42.cpp $ ./a.out 20000, 1 20000, 0 40000, 1 40000, 0 80000, 1 80000, 0 160000, 1 160000, 0 320000, 1 320000, 0
-O を指定すると末尾最適化によりスタックオーバーフローせずに計算することができます。最近のＣ/Ｃ++コンパイラはとても優秀ですね。興味のある方はいろいろ試してみてください。
改訂 2023 年 4 月 9 日