再帰呼び出しについて

C言語のプログラムについてです。

テキストからランダムに並べられたアルファベットを順番にひっぱってきて、
二分木の構造にアルファベットをアルファベット順に格納していき、その順番で表示するプログラムなのですが、

typedef struct rec{
char word[1];
struct rec *left;
struct rec *right;
}rec;

という構造体が定義されており、

二分木構造に（なるように）アルファベットを順番に格納していったあと、
それをアルファベット順に表示していく関数が以下の関数hyoujiなのですが、
（二分木を生成する際にmallocを使用しているので、freeがありますが今回は無視してください。）

void hyouji(rec *top){
if(top!= NULL){
hyouji(top->left);
printf("%s\n",top->word);
hyouji(top->right);
free(top);
}
}

この再帰呼び出しの動きがよくわかりません。（つまりはhyoujiの関数の動きがわかりません。）

*topは二分探索木の一番上のアドレスを示しています。
wordにアルファベットが格納されています。


たとえば、下のように格納されていたらどのようにhyouji関数は動くのでしょうか。
順番に説明していっていただけたらありがたいです。
（ちなみにプログラム的に下の例のように格納されていきます。
まずtopを生成して、テキストファイルの先頭のアルファベットを入れて、そこから順に
格納していくので、topがaとは限りません。）

........................[b]
....................／...＼
.................[a]........[e]
...........................／...＼
.......................[c].........[g]

No.3 ベストアンサー 回答者： kmee 回答日時： 2013/05/21 08:38

落ち着いて、よく考えてください。

「見ての通り、hyouji(top->left);の後、hyouji(top->right);の前です。」と書きました。
「top->left全体の表示」の後
「top->right全体の表示」の前
に、top自身だけのprintfです。


これが
void hyouji(rec *top){
if(top!= NULL){
hyouji0(top->left);
printf("%s\n",top->word);
hyouji0(top->right);
free(top);
}
}

なら、実行順番わかりますよね?

この回答へのお礼

度重なる質問に、丁寧に答えていただきありがとうございました。
なんとか理解をつめたかったので本当に助かりました。

お礼日時：2013/05/21 10:15

No.5 回答者： jjon-com 回答日時： 2013/05/21 10:13

No.4に対して２点補足。

----------------
１点目。
(1) 左の人を呼び出す（左の人にバトンを渡す）
(2) （左の人から自分にバトンが戻ってきたら）自分のwordを表示する
(3) 右の人を呼び出す（右の人にバトンを渡す）
(4) 自分を呼び出した呼び出し元にバトンをもどす

という箇所の(4)は，(2)の表記に合わせて次のように書いた方がよかったです。

(4) （右の人から自分にバトンが戻ってきたら）自分を呼び出した呼び出し元にバトンをもどす

----------------
２点目。
(1)○の左は存在しないのでバトンはそのまま

という箇所は単純にこう説明したけれど，存在しないかどうか判定しているのは本当は自分ではなく，次のようになります。

↓左の人を呼び出す
↓呼び出してみたら if (top != NULL) で左の人は存在しないことが判明
↓そのまま呼び出し元に戻る

No.4 回答者： jjon-com 回答日時： 2013/05/21 10:02

再帰をイメージする際，

「自分自身を呼び出す」のように自分にループして戻ってくるイメージで捉えると，同じ場所をぐるぐる回って何回目の呼び出しか自分でも区別していないイメージになるので，
「自分のクローンを生み出してそれを呼び出す。用が済んだらそのクローンは消える」のように，「自分のコピーという“別人”」を呼び出すイメージで捉えると分かりやすいように思います。

(1) hyouji(top->left);
(2) printf("%s\n",top->word);
(3) hyouji(top->right);
(4) }

というコードは(1)→(2)→(3)→(4)の順に処理が進んでいくのだけれど，陸上競技の400mリレー走よろしく，現在その箇所を実行中であることをバトンの有無で示すならば，次のような比喩で説明できます。

(1) 左の人を呼び出す（左の人にバトンを渡す）
(2) （左の人から自分にバトンが戻ってきたら）自分のwordを表示する
(3) 右の人を呼び出す（右の人にバトンを渡す）
(4) 自分を呼び出した呼び出し元にバトンをもどす

........................[b]
....................／...＼
.................[a]........[e]
...........................／...＼
.......................[c].........[g]

ですから，上記の二分木の根(root)を起点に，この規則にしたがって木を走査すると，次の流れを上から一つずつ順に追った処理になります。

(0) [現在位置はｂ]
(1) 左のａにバトンを渡す
........(0) [現在位置はａ]
........(1)ａの左は存在しないのでバトンはそのまま
........(2)「私はａ」と表示★
........(3)ａの右は存在しないのでバトンはそのまま
........(4)呼出元ｂにバトンをもどす
(2)「私はｂ」と表示★
(3) 右のｅにバトンを渡す
........(0) [現在位置はｅ]
........(1)左のｃにバトンを渡す
................(0) [現在位置はｃ]
................(1)ｃの左は存在しないのでバトンはそのまま
................(2)「私はｃ」と表示★
................(3)ｃの右は存在しないのでバトンはそのまま
................(3)呼出元ｅにバトンをもどす
........(2)「私はｅ」と表示★
........(3)右のｇにバトンを渡す
................(0) [現在位置はｇ]
................(1)ｇの左は存在しないのでバトンはそのまま
................(2)「私はｇ」と表示★
................(3)ｇの右は存在しないのでバトンはそのまま
................(3)呼出元ｅにバトンをもどす
........(3)呼出元ｂにバトンをもどす
(4)呼出元にバトンを戻す（一連の処理の終了）

この回答へのお礼

本当にわかりやすい説明ありがとうございました。
助かります！

お礼日時：2013/05/21 10:27

No.2 回答者： kmee 回答日時： 2013/05/21 06:48

再帰呼び出しを理解するコツは、呼び出した先のことは考えないで、機能だけを考える、ということだと思います。

これは、普段からやっていることでもあります。
printfが中でどんな動きをしているか、考えて使ってますか?「指定した書式で出力する」って「機能」だけを考えているのではないでしょうか。

また、同じ行を実行しているので、「(ループのように)戻ってくる」と考えると、混乱の元です。
呼び出されたhyoujiと呼び出したhyoujiは、#1にあるように「機能はまったく同じの、別の関数」だと考えましょう。



void hyouji(rec *top){
if(top!= NULL){

/*
top->leftを「hyouji」する。
今実行している「hyouji」ではなく、別の「hyouji」が実行される
中でどうなっているかは、ひとまず置いておく
*/
hyouji(top->left);


/* top->world をprintfで出力 */
printf("%s\n",top->word);

/*
top->rightを「hyouji」する。
今実行している「hyouji」ではなく、別の「hyouji」が実行される
中でどうなっているかは、ひとまず置いておく
*/
hyouji(top->right);

}
}


> どのタイミングでPrintfが実行されるのでしょうか。

見ての通り、hyouji(top->left);の後、hyouji(top->right);の前です。
hyouji(top->left);やhyouji(top->right);の中でprintfが実行されているかもしれませんが、それは「別の関数」なので、関係ありません。

> Printfでこけてしまうとはどういうことでしょうか？

char word[1];
に格納できる「文字列」は、何文字までだと思いますか?
文字列には、本体の文字列の他に'\0'が必要です。少なくとも、printfの書式%sは、「'\0'で終わる文字列」を必要とします。

あるいは、1文字だけなら、「文字列」である必要はありません。charで文字だけ記憶して、%cを使う、という方法もあります。

この回答への補足

ただ、そうなるとtop、(top)のleft、(top)のrightが表示されてから、つまり今回の木の例だと[b]、[a]、[e]の順に表示されてしまいそうですが、（実際はabcegとできている）どこで理解が間違えているのでしょうか。
何度も申し訳ありません。

printfがこける　に関してはそのとおりです。
指摘ありがとうございます。

補足日時：2013/05/21 07:28

No.1 回答者： Tacosan 回答日時： 2013/05/20 23:31

これ, printf でこけるよね.

さておき.

top が b を指すとしたら
・a を指すポインタを使って hyouji を呼び出す
・printf を実行する
・e を指すポインタを使って hyouji を呼び出す
というだけですが....

わかりにくかったら, hyouji をコピーして
void hyouji0(rec *top){
if(top!= NULL){
hyouji1(top->left);
printf("%s\n",top->word);
hyouji1(top->right);
free(top);
}
}
void hyouji1(rec *top){
if(top!= NULL){
hyouji2(top->left);
printf("%s\n",top->word);
hyouji2(top->right);
free(top);
}
}
(以下略)
としてみたら?

この回答への補足

回答ありがとうございます。

どのタイミングでPrintfが実行されるのでしょうか。
質問に質問をかさねてすいません。

あと、Printfでこけてしまうとはどういうことでしょうか？
どこか不都合な点があったりしますか

補足日時：2013/05/21 00:09