再帰関数とは
解決初歩的なことですが、教えてください。
ツリービューのノードを読み込む時、再帰関数を使います。
関数を入れ子にするのは理解できるのですが、この時、関数は、どのような働きをしているのでしょうか。
「長男」→「長男」→「長男」と下って、子がなくなったら、「弟」を探しているのでしょうか。
それとも、まずルートの「子」を全部拾って、次に「長男」から順番に、その「子」を全部拾っているのでしょうか。
「入れ子」がどういう働きをしているのかが分りません。
もうひとつ分からないのは、たとえば「子」→「子」と下っていき、子がなくなって、親に戻った場合、コードが川下へ下る方向だと、また子に戻って、「ぐるぐるまわし」になってしまわないのでしょうか。
よろしくお願いいたします。
treeview だと微妙に複雑なので例題にするには高度すぎるかな
俺が再帰について理解というか納得というかしたのは「二分木の辞書順表示」だな
掲示板の文字だけの説明、つまり図なしで説明できる/納得してもらえるとは
とても思えないので、ぐぐってみよう。そっちのほうがはやそう
探索アルゴリズムのお話。
深さ優先探索か、幅優先探索かの話です。
再帰関数は深さ優先探索のために作ります。
どちらも原理的にはループとスタックを使って実装できますが、
深さ優先探索は再帰関数を使うことでスタックを使わずに実装できます。
>「長男」→「長男」→「長男」と下って、子がなくなったら、「弟」を探しているのでしょうか。
再帰関数のふるまいはこちらが正解。深さ優先探索です。
それとも、まずルートの「子」を全部拾って、次に「長男」から順番に、その「子」を全部拾っているのでしょうか。
こちらは幅優先探索。ルートから順に「子すべて」、「孫すべて」、「ひ孫すべて」・・・と探索していきます。
>もうひとつ分からないのは、たとえば「子」→「子」と下っていき、子がなくなって、親に戻った場合、コードが川下へ下る方向だと、また子に戻って、「ぐるぐるまわし」になってしまわないのでしょうか。
なりません。なったとしたら、それは再帰関数の作り方が悪かっただけの話。親に戻ったら二男を探すか、いなければ祖先に戻るかで、また長兄を探していくことはしません。
> 関数を入れ子にするのは理解できるのですが、この時、関数は、どのような働きをしているのでしょうか。
ツリービューが帰納的に定義されてるなら、そのノードはwell-foundedな集合の元となる。それを調べる再帰関数は開始するノードからのinfinite descending chainを辿る働きをするわけだ（これはもちろん有限のステップで停止する）。
↑シロートさんにそーゆー説明しても通じんて。
# infinite? 無限?
ミス
○finite
×infinite
また掲示板でチャットするとか言われるｗｗｗｗｗｗ
すでに突っ込み入ってた
ありがとうございます。
HTREEITEM ht、ツリービューのメンバ変数をm_tree1として、
「長男」→「長男」→「長男」と下ってゆくだけななら、再帰関数を使わなくても、最初にhtにルートのハンドルを置けば
while (1) {
ht = m_tree1.GetNextItem(ht, TVGN_CHILD);
if ( ht == NULL ) {break; }
}
で、取得できます。
次に、関数化して入れ子にするなら、
void C***View::saiki(void)
{
ht = m_tree1.GetNextItem(ht, TVGN_CHILD);
if ( ht == NULL ) {return; }
saiki();
}
を作っておいて、
void C***View::OnBnClickedButton1()
{
saiki();
}
とすれば、同じ結果になります。
次に、「弟」まで取得するなら、HTREEITEM hr を用意して、
void C***View::saiki(void)
{
hr = ht;
ht = m_tree1.GetNextItem(ht, TVGN_CHILD);
if ( ht == NULL ) {
ht = m_tree1.GetNextItem(hr, TVGN_NEXT);
if ( ht == NULL ) {
ht = m_tree1.GetNextItem(hr, TVGN_PARENT);
}
}
saiki();
}
とすると、ちょっと不完全なコードですが、最も川下の「親」とその「子」全ては取得できます。
しかし、最も川下の「親子」だけで、「ぐるぐるまわし」になってしまい、「親の親」にはさかのぼっていきません。
ここから先が分かりません。
それに、サンプルになるような再帰関数を見ると、もっと単純なコードだと思うのです。
アドバイスを頂けませんでしょうか。
引数を与えにゃあかんでしょ。
void 再帰(ノード node) {
nodeに対してなにかする
for ( nodeの子であるchild全員に対して ) {
再帰(child);
}
}
επιστημηさん、ありがとうございます。
void 再帰(ノード node) {}
の中で取得するのは、「長男」ではなく、「子」全員になるのでしょうか。
それで、入れ子に入る「void 再帰(ノード node)」は、１個ではなく、「子」全員の数という考え方でいいのでしょうか。
そんな疑問が湧くなら試してみようとは思わんのでしょうか。
>void 再帰(ノード node) {}
>の中で取得するのは、「長男」ではなく、「子」全員になるのでしょうか。
>それで、入れ子に入る「void 再帰(ノード node)」は、１個ではなく、「子」全員ですよ。じゃないといつ次男を引数とした再帰関数が呼ばれるの。
切り貼りしてたらめちゃくちゃになった。
>void 再帰(ノード node) {}
>の中で取得するのは、「長男」ではなく、「子」全員になるのでしょうか。
>それで、入れ子に入る「void 再帰(ノード node)」は、１個ではなく、「子」全員の数という考え方でいいのでしょうか。
１個ではなく、「子」全員ですよ。じゃないといつ次男を引数とした再帰関数が呼ばれるの。
επιστημηさん、そださん、ありがとうございます。
下記のコードを作りました。
HTREEITEM ht にルートのハンドルを入れておいて、
void C***View::OnBnClickedButton1()
{
saiki(ht);
}
void C***View::saiki(HTREEITEM ht)
{
ht = m_tree1.GetNextItem(ha, TVGN_CHILD);
if ( ht != NULL ) {
saiki(ht);
}
else {ht = ha; }
while(1) {
ht = m_tree1.GetNextItem(ht, TVGN_NEXT);
if ( ht == NULL ) {
ht = m_tree1.GetNextItem(ha, TVGN_PARENT);
ht = m_tree1.GetNextItem(ht, TVGN_NEXT);
if ( ht == NULL ) {return; }
saiki(ht);
if ( ht == NULL ) {return; }
}
saiki(ht);
}
}
これで、ht にノードのハンドルが順番に入ってきました。
ただ、これですと、無限ループになります。
ht が最後のノードのハンドルに出会ったら抜け出す、とか、手段はありそうですが、なんとなくヘンです。
また、saik()の中段で、子がない場合に弟に、進む向きを変えていますが、今までに見た再帰のコードでは、そんな「切り替え」など、やっていなかったように思うのです。
戻り値を使うと、解決しそうに思ったのですが、いろいろ考えても、成功しませんでした。
なんだか固まってしまって、ヒントを頂けませんでしょうか。
ダメダメぢゃん。
> void C***View::saiki(HTREEITEM ht) {
> ht = m_tree1.GetNextItem(ha, TVGN_CHILD);
もらった引数ブチ壊し。 haてなに?
「なにやってんの?」が正直な感想。
> haてなに?
失礼しました。
タイプミスです。
ha は、saiki関数の引数です。
ただ、グローバルな変数、HTREEITEM ht をグローバルに使ってしまっていることには、気付きました。
もう少し、考えてみます。
void C***View::saiki(HTREEITEM ha)
{
ht = m_tree1.GetNextItem(ha, TVGN_CHILD);
if ( ht != NULL ) {
saiki(ht);
}
else {ht = ha; }
while(1) {
ht = m_tree1.GetNextItem(ht, TVGN_NEXT);
if ( ht == NULL ) {
ht = m_tree1.GetNextItem(ha, TVGN_PARENT);
ht = m_tree1.GetNextItem(ht, TVGN_NEXT);
if ( ht == NULL ) {return; }
saiki(ht);
if ( ht == NULL ) {return; }
}
saiki(ht);
}
}
まずは再起関数について考えを整理した方がよいような気がします。
今回の場合は
ツリー構造の要素を一つずつ取得
その要素に子がいるなら・・・
→必要な処理を実施
→自信の関数で、この要素を引数にして調査
その要素に子がいないなら・・・
→必要な処理を実施
次の要素を確認
以上を繰り返し
ですよね？
後はそれに当てはまるものを埋め込んでいけばよいのでは？
それから、無限ループを恐れるのであれば、上限値を決めておき、そこに達し
たら強制的にループを止めるようにする等すればよいかと思います。
あまり具体的ではなくて申し訳ありませんが、動きを理解しながら作っていか
ないと、破綻しちゃうような気がしたので・・・
再帰関数を使うメリットはツリーの段数を決めうちにしないで
処理出来る所ですよね。
ツリーの段数が予めわかっていてそれ以上はありえないなら
再帰を使わなくてもいいわけで。
再帰関数を作成する場合、関数一回の呼び出し範囲での
終了条件はハッキリしているはずです。
これがハッキリしていないのならそもそも再帰は組めないです。
今回の例で言うなら関数の復帰ポイントは与えられたノードの
子供を全てチェックし終えたら終了な訳です。
見つけたノードに更に子供がいたらそのノードを基点に
自関数を呼び出すことでその子供を全てチェックするまで
処理をすると言う事になります。
その理屈から言えば、無限ループになるはずが無いと思います。
ある段階から更に自関数を呼び出した場合、呼び出した段階での
チェック状態は呼び出した自関数から戻ってくるまで保存されて
いるはずですし、保存できるようにして無いとそもそも変です。
呼び出し先の自関数の中の動きが直接影響するような作りは
普通しませんから。
再帰関数として成立する為の関数内での処理と言うのをきちんと
整理できないのであれば、再帰関数は使わない方が良いのでは？
逆にどうしても使いたいのであれば、その部分を整理して理解する
しか道は無いと思います。
それは再帰のメリットになっていない
再帰はループでも表現できるしループは再帰でも表現できる
これは私の持論になってしまうかもしれませんが、ループや再帰関数を使う場
合、予期せぬ事が原因(バグなど)による無限ループを避けるために、必ず万が
一のための停止条件を入れるようにしています。
> その理屈から言えば、無限ループになるはずが無いと思います。
確かに「理屈」ではそうですが、極端な話「どういう条件になっても、いつか
はループが終了する」という状況にしておく方がいいような気がしますが・・・
これって、あまりよい考え方ではないのですかね？
ちょっと話がそれてしまいましたが・・・
> 再帰はループでも表現できるし
繰り返しに置き換え可能な再帰は再帰の一部。
置き換え不可能な再帰は存在します。
# アッカーマン関数とか置き換え不可能っしょ。
> 再帰のメリット
再帰的に定義されたデータ構造を扱うのにもっとも楽
ってこっちゃないですか実装サイドからすれば。
TreeViewとかXMLとかはその最たるものでしょう。
void C***View::saiki(HTREEITEM ha)
{
do_something(ht); /* 何か必要な処理を行なう */
HTREEITEM ht = m_tree1.GetNextItem(ha, TVGN_CHILD); /* 子供ノードを取得 */
while(ht) {
saiki(ht);
ht = m_tree1.GetNextItem(ht, TVGN_NEXT); /* 子供の兄弟を取得 */
}
}
これだけの事でしょ。
質問者の間違いは再帰関数の中でローカルに変数を宣言していないこと！
あと、子供の処理が終わったら「親に戻って」次の子供を処理しようと考えるのも間違い。
再帰で処理する場合、自分の子供だけを処理すればいいんです。
自分の子供の面倒を見たら、後は自分の親に任せるんです。そうすれば自分の親が
兄弟の面倒をみてくれます。
> 関数を入れ子にするのは理解できるのですが、この時、関数は、どのような働きをしているのでしょうか。
下記のツリー:
親(a)-+-長男(b)-+-長男(c)-+-長男(d)
| | +-次男(e)
| +-次男(f)-+-長男(g)
| +-次男(h)
+-次男(i)-+-長男(j)-+-長男(k)
| +-次男(l)
+-次男(m)-+-長男(n)
+-次男(o)
で
void C***View::OnBnClickedButton1()
{
saiki(親);
}
とすると
do_something(ht);
はa,b,c,d,e,,,とアルファベット順に処理します。
> これだけの事でしょ。
ってことを"とっくの昔"に書いたんですけどね (^^;
void 再帰(ノード node) {
nodeに対してなにかする
for ( nodeの子であるchild全員に対して ) {
再帰(child);
}
}
しまった、ツリーがうまく表示出来ていない orz
次男(e)は長男(c)の子供(長男(d)の弟)
次男(f)は長男(d)の子供(長男(c)の弟)
次男(h)は次男(f)の子供(長男(g)の弟)
次男(i)は親(a)の子供(長男(b)の弟)
次男(l)は長男(j)の子供(長男(k)の弟)
次男(m)は次男(i)の子供(長男(j)の弟)
次男(o)は次男(m)の子供(長男(n)の弟)
です。
> ってことを"とっくの昔"に書いたんですけどね (^^;
その通りでした。
質問者はそれを実際のコードにする力がないって話かな。
＞アッカーマン関数とか置き換え不可能っしょ。
スタック使えば再帰排除できるのでは？
>> アッカーマン関数とか置き換え不可能っしょ。
> スタック使えば再帰排除できるのでは？
スタックを持ち出した時点で(繰り返しに置き換え可能とはいえ)
単に再帰(関数call/return)を模倣したに過ぎないんじゃねぇですか?
# 本題とは離れちゃうので僕はここまで (^^;
# 横からチャチャだけ
「ループはアセンブリ言語でも表現できるし、再帰もアセンブリ言語で表現できる。アセンブリ言語で表現できることはループや再帰のメリットではない」が是であれば、ループで表現できるものを再帰で表現するメリットは無いでしょうね。
再帰関数はデバックが大変なのだ♪
＞質問者はそれを実際のコードにする力がないって話かな。
引数の親の子が１人っ子だったときに親の兄弟まで
処理しちゃってるあたりちょっと勘違いしてるだけかなぁ〜と。
最初にmaruさんの書いたような具体的なコードを示せば
あとは追ってみながら理解してくれた気もする。
＞単に再帰(関数call/return)を模倣したに過ぎないんじゃねぇですか?
実装は確かに再帰の模倣だけど、その実装が見えるかどうかってのは重要なポイントの一つだと思うのだけれど、とオレもここまでにしとこう
ありがとうございます。
maru さんのコードで成功しました。
ハンドルに NULL が入っても、if で分岐する必要はない、とか、
最初のハンドルに出会ったらループを抜ける、というような発想は
ありませんでした。
「再帰」は、手持ちの参考書を読んでも、ネット検索しても、
理屈からしてよくわからず、あきらめムードだったのですが、
今回、質問してよかったと思います。
たいへんありがとうございました。
| ツイート |  |