では今回の本題に入りましょう。今回は前回の解答の別解をやってみます。 前回の問題は以下のようなものでした。
問題１ ： 文字列を受取り、その逆順を返すプログラムを書け。───────０）
char data[65535];という文字配列を使用しましたが、これでは大きさが65535以上の文字列は扱えません。
そこで、今回は４．５．３でやった再帰を用いて無限の大きさの文字列を扱うプログラムを組んでみましょう。（無限の大きさと言っても各マシンのメモリー数を越えることはできませんが）今回も前回と同じ様な段階をふんで行きます。
１）問題１の分析─────────────────────────────１）
-
（１）入力元は何で、出力先は何か。
（２）文字列の長さはどれくらいか。（１）は前回と同じです。解決策も前回と同じ、標準入力、標準出力にしましょう。
（２）については今回は関係ありませんね。 ２）データとデータ構造の決定───────────────────────２）
-
今回はこれが問題です。入力される文字列の大きさは予めわかっていないのに、データ構造と呼べるほどのものを用意できるのでしょうか。今のところ、答えはＮＯです。（もう少しＣについて勉強するとできます）では、どうすればいいのでしょうか。
とりあえずわかっているものとしては、前回最後に出てきた、入力文字を判定する一文字分のデータが必要なことはわかります。それ以外は用意できそうにありませんのでこのままにして先に進みましょう。
必要データと型 ： 入力終了文字取得のための文字、文字型。
３）全体の大まかな流れを考える。─────────────────────３）
-
再帰的に処理するという基本方針は決まっているのですが、一体これはどういうことなのでしょうか。もう少し具体的に考えてみましょう。４．５．３ で少しやりましたが、再帰構造とは、”その処理が再帰的に行われるもの”ということです。ｎ階乗の関数などはこのいい例でしょう。（後で出てきます）では、今回の問題では、何が再帰的に処理されているのでしょうか。今回考える再帰構造は少し変わっているかもしれません。それは、”一文字入力し、その文字を出力する”という構造を持つからです。”？？”なんて考え込まず、気を楽にして先に進んでください。
その前に少しおさらいです。４．５．３で再帰構造について学びました。その中では階乗を求める関数の説明をしていますが、これはｆ（ｎ）＝ｎ！とすると、
５！ ＝ ５ ＊ ４！ ＝ ５ ＊ ４ ＊ ３！ ＝ ５ ＊ ４ ＊ ３ ＊ ２！ ＝ ５ ＊ ４ ＊ ３ ＊ ２ ＊ １！ ＝ ５ ＊ ４ ＊ ３ ＊ ２ ＊ １ ＊ ０！ ＝ ５ ＊ ４ ＊ ３ ＊ ２ ＊ １ ＊ １
となって正しい答えが得られることがわかります。ここまではNo.8でやったので、おさらいはここまでですが、この後の説明のためもう少し、詳しく見てみましょう。上の例で５！を求めるのに５と４！を掛け合わせていますが、これは４！がその値を持っているということですね。えっ、何を当たり前のことをいっているのかって？ それとも良くわかりません？？ では先の関数ｆ（ｎ）＝ｎ！を用いて説明しましょう。
上の例は
ｆ（５） ＝ ５ ＊ ｆ（４） ＝ ５ ＊ ４ ＊ ｆ（３） ．．．．．．．．．．．．．．．．．．． ＝ ５ ＊ ４ ＊ ３ ＊ ２ ＊ １ ＊ ｆ（０） ＝ ５ ＊ ４ ＊ ３ ＊ ２ ＊ １ ＊ １
となるのですが、一行目でｆ（５）を計算するのに５とｆ（４）を掛け合わせていますが、このときｆ（４）は４！の値を知っていることになります。同様に次の行ではｆ（３）が３！の値を知っていることになります。同様に最後までいくと、ｆ（０）が出てくるわけですがこれは定義にはっきりと１と書いてあるので、ここで計算のための展開は終了します。（計算はしていないことに注意。展開が終ってから始めて計算ができるようになります。）ここでは各ｆ（ｎ−１）がその値を知っていることに注意してください。この各関数が何か情報を持っているということと、各ｆ（ｎ）がｆ（ｎ−１）を呼び出していることがこれから重要になってきます。このことを上記の例を参考にしながら、今回の問題に当てはめて考えてみましょう。説明のため以下の関数を定義します。
ｒ（ｘ） ： 関数ｒは情報として文字ｘを持っている。
また、表記上の約束として以下のことを約束することにしましょう。
ｒ（） ： 関数ｒは何も情報を持たない。 ｒ（） ← x ： 関数ｒに情報 xを入力する。 xは文字列でも良く、この場合は一文字受けとって もう一度自分自身を呼び次の文字を入力させる。 ｒ（x） ｒ（y） ： 関数ｒ（y）は関数ｒ（x）に呼び出されている。
簡単な例でabcdeを入力させたいとします。この時、関数ｒがこれらの情報を順番に持っていればどうなるでしょうか。ｒ（） ← abcde ｒ（a） ｒ（） ← bcde ｒ（a） ｒ（b） ｒ（） ← cde ｒ（a） ｒ（b） ｒ（c） ｒ（） ← de ｒ（a） ｒ（b） ｒ（c） ｒ（d） ← e ｒ（a） ｒ（b） ｒ（c） ｒ（d） ｒ（e）
大体これで感じがつかめるでしょうか。最終的には１行目： 関数ｒに文字列abcdeを渡す。 ２行目： 関数ｒはaを文字列として持ち、さらに自分自身を呼び出し、残りの文字列bcdeを渡す。 ３〜５行目： 同様 ６行目： 入力文字がなくなったら、終り。 ｒ（a）はｒ（b）を呼びだし、 ｒ（b）はｒ（c）を呼びだし、 ｒ（c）はｒ（d）を呼びだし、 ｒ（d）はｒ（e）を呼び出すことによって、
文字列abcdeは関数達が持っていることになります。これを利用すれば、変数を用意しなくても、文字列は保持することができます。では、逆順に出力するにはどうしたら良いでしょうか。上の説明の文字列の保持は、先の階乗関数の例でいくと展開したことに相当します。つまりまだ計算段階に到っていません。実際、階乗関数の再帰版では、展開した右端から計算していくようになっています。計算が終るとその関数は計算結果をreturn文で呼び出した関数に返し、終了してしまいます。（Progrraming Lecture No8参照）つまり
ｆ（０）は１ をｆ（１）に返すと終了し、 ｆ（１）は１＊１ をｆ（２）に返すと終了し、 ｆ（２）は２＊１ をｆ（３）に返すと終了し、 ｆ（３）は３＊２ をｆ（４）に返すと終了し、 ｆ（４）は４＊６ をｆ（５）に返すと終了し、 ｆ（５）は５＊２４を計算して終了。
となるわけです。これを関数ｒに当てはめて考えてみましょう。ｒ（ｅ）はｅを印字すると終了し、 ｒ（ｄ）はｄを印字すると終了し、 ｒ（ｃ）はｃを印字すると終了し、 ｒ（ｂ）はｂを印字すると終了し、 ｒ（ａ）はａを印字して終了。
という風にすればいいでしょう。話しがややこしくてわかりにくそうですが、もう一度見直してみるなどして、少し考えてみてください。プログラムに少し自身のある人は読み飛ばして、プログラムを見るとよくわかることと思います。
さてこれで大まかな流れはおわかり頂けたかと思います。ところで再帰構造で最も重要なことは、
・停止条件は何か ・必ず止まるか。（停止条件に引っかかるか）
ということです。（本質的にはプログラム自体にこのことが当てはまります。つまり、どんな入力に対しても必ず停止するかということです。この問に対する厳密な解を与えることは現在では不可能で、多くの研究者が研究中です。ただここでは”自分自身を呼ぶのを止めて、戻り始める条件は何か”ということです。例えば、ｎ階乗のプログラムでは関数fact内の if(n == 0) がこれに当ります。int fact(int n) { int dum; if (n == 0) dum = 1; else dum = n * fact(n - 1); return dum; /* End of fact */
ｎ階乗のプログラム（部分） つまり、ｎが０でなければ、ｎを１引いて自分自身を呼出し、ｎが０になったら１を返して呼び出しを止めています。（Programming Lecture No.8参）これは渡された引数が正の整数であれば必ず停止条件に引っかかり、停止します。
では、今回の問題での関数の停止条件はなんでしょうか。そうです、入力終了文字（CRかEOF）が入力されたら停止すればいいのですね。
ではこれに肉付けをする形で細かい部分を考えることにしましょう。
４）データ構造にあったアルゴリズムを考える。───────────────４）
-
今までのことを整理してまとめてみましょう。
・再帰的に入力すること ・再帰的に出力すること ・そのためにはもう一つ別の関数を（メインの他に）作成する必要があること ・再帰的なアルゴリズムには、終了条件が必要なこと ・終了条件は入力終了記号が入力されたときであること
これらをもとにアルゴリズムを考えてみましょう。まず、メインルーチンですがこれは単に、入力と出力を行なう関数を呼ぶだけですね。
では、入力と出力を行なう関数はどうすればいいのでしょうか。考える前にもう一つ考えることがあります。関数には返り値の型と引数というものがあったことを思い出してください。例えば先の階乗関数では返り値の型はint型、引数は一つで型はintでした。この場合はどうなるでしょうか。何か値を返す必要があるでしょうか。何か引数として渡す必要があるでしょうか。このことも交えて少し考えてみてください。
： では解答です。まず、この関数の返り値の型と引数ですが、これはどちらも必要ありません。解説で用いた関数ｒは引数として入力された文字というものを持っていましたが、これは実際にはプログラム中に埋め込むため必要なくなるのです。これは下の解答を見てもわかります。以下の部分はサブルーチンである関数のアルゴリズムであることに注意してください。
：
：
：
：
：
：
：
：一文字入力する。 if(その文字が入力終了記号でないなら) ｛ 自分自身を呼び出す。 一文字出力する。 ｝ 関数終了。
これで終りです。以外とあっさりしているので、落胆したかも知れませんが、これで充分なのです。これは実際にプログラムを見るとよくわかります。では、実際にプログラムを組んでみましょう。 ５）プログラミング────────────────────────────５）
-
いきなりですが、今までの解説をもとに少し考えてみてください。わからなければ悩まずすぐ先に進んでください。
： では解答です。このプログラムでは特別な関数は一切使っていないので、#include文で取り込まれるものは<stdio.h>だけです。
：
：
：
：
：
：
：
：#include <stdio.h>
次に使用する関数の宣言を行ないます。標準関数ではなく、ユーザ定義の関数を使う場合、予め宣言しておく必要があります。ここではサブルーチンとなる関数を作成しますので、宣言しておきます。宣言は返り値の型 関数名（引数、引数、、、、）； ← セミコロンがあることに注意。
でした。関数宣言の場合は最後にセミコロンが付くことを忘れないで下さい。前に書いた階乗関数のプログラムを見ればわかりますが、実際の定義のところでは最後にセミコロンは付けません。
ここでは関数名getandwriteとして宣言します。
void getandwrite(void);
返り値のところのvoidは”この関数は返り値がない”ことを表しており、引数のところのvoidは”この関数は引数がない”ことを表しています。次にメインですが、これは前にも書いたとおり、サブルーチンを呼び出すだけです。
main() { getandwrite(); }呼ばれる側では引数がない場合にはvoidと宣言しましたが、呼ぶ側では何も書かず（）だけ書いておきます。さて、では問題のサブルーチンです。４）の解説をもとに書いて見ましょう。
void getandwrite(void) { char c; c = getchar(); if(( c!= EOF) && (c != '\n')) { getandwrite(); write("%c", c); } return; }となります。では、解説していきましょう。
まずこの関数では一文字入力を行なうので、そのためのデータが必要となります。型は当然char型です。
次にこの変数に一文字読ませるのですが、これはとりあえずgetchar()を使いましょう。scanf()でも今回は問題ないのですが、こちらの方が関数らしくていい感じです。
で、次のif文ですが（）内は”入力終了記号でないなら”を表しています。（詳しくはNo.9参照）すると自分自身を呼び出し、返ってきたら入力された一文字を出力して終っています。プログラム全体をまとめて書くと以下のようになります。
論より証拠。実際にコンパイルして動かしてみましょう。/* Program */ /* Short Program 1 */ /* 無限に文字列を受取り、その逆順を返す */ #include <stdio.h> void getandwrite(void); main() { getandwrite(); printf("\n"); } void getandwrite(void) { char c; c = getchar(); if((c != '\n') && (c != EOF)) { getandwrite(); printf("%c",c); } return; } ６）コンパイル──────────────────────────────６）
-
コンパイル中でエラーがでたら、エディタで編集し直してエラー箇所を取り除きます。大体エラーは、｛｝の対応付けが出来ていない、；がない等が多いようなのでよく見てみましょう。
７）テスト────────────────────────────────７）
-
コンパイルできたら、実際に動かしてみましょう。適当に文字列をいれてみて、ちゃんと動くかどうか確認してみます。スペース等が入ってもきちんと動きますし、ファイルからリダイレクションで渡しても、大丈夫です。
８）改良─────────────────────────────────８）
-
今回は改良するところはないでしょう。手を加える余地があるとすれば、
- getchar()ではなく、scanf()を使う。
- 後に保存できるように、配列などのデータに入力した文字列を代入していく。
scanf()を使う場合には、 scanf("%c",c); として使います。
配列などへの代入は、後でポインタを勉強したときに公開することにしましょう。
９）完成─────────────────────────────────９）
-
さて、悩んだ割にはあっというまに完成です。今回はどちらかというと、演習というよりは講義という感じでしたが、再帰の考え方は慣れるまではけっこう面倒なので今回はこういう形式になってしまいました。再帰に関する要点（３、４参照）は述べてあるので、もう一度読み返してしっかり理解してください。
練習問題として、前々回練習問題として出しておいたユークリッドの互除法について再帰的なプログラムを組んでみてください。互除法の定義に関しては以下に転載しておきます。
演習問題
- ユークリッドの互除法を用いて、２つの数の最大公約数を求めるプログラムを再帰的に定義せよ。ユークリッドの互除法については、以下の例で説明しよう。
例 １２８と３６の最大公約数を求める。 （１２８，３６） → （３６，１２８を３６で割った余り） → （３６，２０） → （２０，３６を２０で割った余り） → （２０，１６） → （１６，２０を１６で割った余り） → （１６，４） → （４，１６を４で割った余り） → （４，０） ↑ この４が１２８と３６の最大公約数 プログラミングのヒント ｘとｙの最大公約数を求める関数をｇｃｄ（ｘ，ｙ）とする。 一般にｒ＝ｘ ％ ｙとすると
とにかく再帰で考えることは、
・何が再帰か ・停止条件は何か
の二点です。これをしっかり考えてアルゴリズム等をたててください。この問題は多くの本で例題として挙げているので参考に見てみてもいいでしょう。本によっては再帰的なプログラムと非再帰的なプログラムと両方載っているので見比べてみてください。ここでの解答は次回行うことにします。（比較のため、３種類のプログラムを公開します）
今回はここまでです。