c言語の再帰について教えてください。

質問

c言語を勉強してるんですが、再帰のイメージがなかなかつかめません。

例えば、入力した文字列を逆から一文字ずつ表示させるのには
どうしたらいいのか教えてください！

入力：ABCDE
E
D
C
B
A

ソースで処理される順序など説明等していただけたらうれしいです。

回答No.5

salsberry · ベストアンサー

この処理をする関数をf()とします。引数は文字列を指すポインタとします。
f()の処理はこのようになります。

a. もし引数のポインタが指す文字列が長さ0ならば、何もしないでリターン
b. そうでない場合(長さ1以上): 引数の指す文字列を "XYZ" とすると、
b-1. 先頭の1文字を除いた "YZ" を指すポインタを引数として、f()を呼ぶ
b-2. 次に、1文字目の"X"を表示してリターン

再帰処理の流れを図示するとこのようになります。

f("ABCDE")を呼ぶ
　　b-1. f("BCDE")を呼ぶ
　　　　b-1. f("CDE")を呼ぶ
　　　　　　b-1. f("DE")を呼ぶ
　　　　　　　　b-1. f("E")を呼ぶ
　　　　　　　　　　b-1. f("")を呼ぶ
　　　　　　　　　　　　a. 何もしないでリターン
　　　　　　　　　　b-2. "E"を表示してリターン
　　　　　　　　b-2. "D"を表示してリターン
　　　　　　b-2. "C"を表示してリターン
　　　　b-2. "B"を表示してリターン
　　b-2. "A"を表示してリターン

お礼

なるほど。非常にわかりやすいですね。
ありがとうございました！

回答No.4

jx-word

学校の課題かなんかですかね？
No.2の方がその処理は再帰に適していないと書いてますが、
再帰の演習問題としては結構いい感じだと思います。

再帰の考え方の基本は、大きな情報まとめて処理するより、
小さな情報に分割して再度自分自身を実行すると言うことになります。
質問の内容であれば、5文字の処理は面倒なので1文字だけ処理して、残りは再帰で処理するという感じです。

コードを書かずに説明するのは難しい・・・・

補足

1文字だけ処理して、残りは再帰で処理する

そういう考え方なのですね。ヒントをいただけたので
考えてみたいと思います！ありがとうございました。

回答No.3

asuncion

> C言語で書くとこうなります。

こうなる場合がある、というのが正確でありましょう。
戻り値を取る再帰関数もありますしね。

お礼

なるほど。意外と簡単に書けるんですね。
最後の入力文字からprintfされるという理屈がまだ
あいまいなのでもうちょと勉強します！

回答No.2

LegaC2

質問に記載されている例は、再帰に適していないと思います。

再帰関数とは、自分自身を繰り返し、呼び出す関数を指します。

C言語で書くとこうなります。
ある条件を満たす限り、自分自身を呼び続けます。

void Recursive()
{
if( ある条件 )
Recursive()
}

例えば、以下のような家族構成の人物がいます。

山本太郎：自分自身
山本一郎：山本太郎の長男
山本次郎：山本太郎の次男
山本花子：山本太郎の長女
山本一男：山本次郎の長男

そして、ここに以下のような再帰関数があったとします。

void 名前表示関数( 人物 )
{
本人の名前を表示 --- (A)
if( 子供がいたら ) --- (B)
{
for( 一人ずつ )
{
名前表示関数( 人物 ) --- (C)
}
}
}

この名前表示関数に山本太郎を与えると以下のように処理が流れます。

1. 山本太郎の名前を表示(A)
2. 山本太郎には子供がいるので、(B)の条件を満たす
3. まずは、一人目の山本一郎を名前表示関数に与える(C)
3-1. 山本一郎の名前を表示(A)
3-2. 山本一郎には子供がいないので、(B)の条件は満たさない
3-3. そのまま関数を抜ける
4. 次に、二人目の山本次郎を名前表示関数に与える(C)
4-1. 山本次郎の名前を表示(A)
4-2. 山本次郎には子供がいるので、(B)の条件を満たす
4-3. 山本一男を名前表示関数に与える(C)
4-3-1. 山本一男の名前を表示(A)
4-3-2. 山本一男には子供がいないので、(B)の条件は満たさない
4-3-3. そのまま関数を抜ける
4-4. 山本次郎にはこれ以上子供がいないので、関数を抜ける
5. 次に、三人目の山本花子を名前表示関数に与える(C)
5-1. 山本花子の名前を表示(A)
5-2. 山本花子には子供がいないので、(B)の条件は満たさない
5-3. そのまま関数を抜ける
6. 山本太郎にはこれ以上子供がいないので、関数を抜ける

以上で終了となります。

結果として、以下のような順番で名前が表示されます。
山本太郎
山本一郎
山本次郎
山本一男
山本花子

簡単に説明するとこんな感じです。

要は、深さが一概に判断できないような場合にこのような関数を作成し、繰り返し処理を行います。

一度、簡単なプログラムを作成することをお勧めします。

お礼

ノートに書きながら順番を追っていくとだんだんつかめてきました。
ありがとうございました！

回答No.1

asuncion

その問題をどうしても再帰呼び出しで実装したいのであれば、
例えばこんな感じでしょうか。

#include<stdio.h>

int main(void)
{
int c;

while ((c = getchar()) != EOF) {
main();
printf("%c\n", c);
}
return 0;
}