Thinkers'Studio
JavaとC言語の自習ツール
再帰呼出しとは
 いきなりですが、問題です。

 問8 再帰呼出しの説明はどれか  (平成24年春期 基本情報技術者試験より)

 ア あらかじめ決められた順番ではなく、起きた事象に応じた処理を行うこと
 イ 関数の中で自分自身を用いた処理を行うこと
 ウ 処理が終了した関数をメモリから消去せず、必要になったとき再び用いること
 エ 処理に失敗したときに、その処理を呼び出す直前の状態に戻すこと

再帰呼出しとは

 再帰呼出しとは、関数が自分自身を呼び出すことです。 上記の答えは「イ」ですね。
 再帰呼出しの例として階乗(factorial)を求めるプログラムが有名です。 例えば 4 の階乗は 4! と表わしますが、4×3×2×1 のことです。 4! = 4×3!、3! = 3×2!、・・・ ですから、関数 factorial は、次のように簡単に書けます。
int factorial( int n ) {
    if( n == 1 ) return 1;
    return n*factorial( n - 1 );
}
 同じ処理を次のように書けますが、上の方が理解しやすいのではないでしょうか?
 この例は再帰呼出しの仕組みを示すためのもので、効果的な再帰呼出しの例とはいえません。
int factorial( int n ) {
    int i, p;

    for( i = n, p = 1; i > 1; i-- ) p *= i;
    return p;
}
 C言語でも Javaでも再帰呼出しを行うことができます。

再帰呼出しが有効と思われるとき

 処理自体が再帰的な性質を持つ場合で、例えば下記のようなものです。
  • ソートやしらみつぶしの検査などで、同様の処理を分割して行うような場合
  • データ構造が階層的になっており、そのそれぞれに同じ処理をするとき
  • 同じ図形を再帰的に繰り返し描画することで複雑な図形を描画するような場合
     (フラクタル図形と呼ばれます。下記に描画例を示します)

 下記の描画例を見てください。
 どちらの図形も、図の一部にさらに同じ図形が現われています。

再帰呼出しの描画

平成18年度春期の基本情報技術者試験 午後の問6 C言語問題で出題されたもの
← のような図は、コッホ曲線と呼ばれます。
これを描画するプログラムで再帰呼出しが使われています。
 (こちらで問題を見ることができます: 基本情報 C過去問

プログラミング講座 cClip のグラフィック機能を使って描いたもの
← のような図は、樹木曲線と呼ばれます。
枝の長さと傾きを変えながら描いています。 枝分かれ回数を指定し、描いては回数を減らしながら再帰呼出しします。 枝分かれ回数が0になったら再帰終了です。
 (cClip のグラフィック機能について: グラフィック


※ 参考 C言語Tips の 最大公約数を求めるプログラム再帰呼出しを使います。