再帰呼出について

質問

クイックソートのコーディングのように、自関数の中で自関数を
呼出のが再帰呼出と言う、とのことですが、その考えまではわかるものの、何故それが必要になるのかがよくわかりません。

回答No.5

Tasuke22 · ベストアンサー

具体的な話は皆さんされているので、私は概念
的な面から。

再帰呼出しの最たる言語がLispだと思いますが、
Lispでリスト処理が前提で再帰関数にすると、
問題を解くのに日本語で考えるより、Lispで考
えた方が早くなってきました。

後から日本語に翻訳するのですが、これが難しい。
日本語で表し難い概念を再帰は簡単に表現できた
ようです。

プロ相手に教えることもありましたが、生徒がこ
れが分からない、という問題を説明するのに、
問題を見た瞬間プログラムが出来るので、白板に
回答を書きながら、それを見て日本語に同時翻訳
しながら説明が出来るくらいになります。

つまり再帰は考え易い、と私は思います。
そして自然言語的ではない、とも感じますね。
その点、繰り返し処理は、自然言語のコンパイラ
言語化というイメージを持っています。

なので、再帰が自分の物になるには若干時間が掛か
りました。最初は取っ付き難かった記憶があります。

補足

＃１さんのリンク先を参考にさせていただいたのですが、
出来あがったプログラムを見る限りでは、
確かに動かすとものの見事に動くな、というのはわかるのですが
どうやったら普通のプログラムから再帰を用いたプログラムに変えれるのか、
或いは
どうやったら仕様から再帰を用いたプログラムに変えれるのかが
わかりません。作り方の（考え方の）問題なのですが・・

今はためしにクイックソートで考えていますが、
どのようにしたら作れるのでしょうか？

検索すると腐るほどコードは出てきますが、
再帰を使うためにどう考えたらよいのかがわかりません。

クイックソートを例に御説明/御教授いただけると助かります。
宜しくお願いします。

回答No.8

Tasuke22

> その判定を過ぎた後の中の処理をどう単純化
> させたらよいのかが不明です。

それは処理内容によりますので、一つずつ学んで
行くしかないでしょう。頑張ってください。

回答No.7

Tasuke22

> 再帰を使うためにどう考えたらよいのかがわかりません。

クイックソートを例にということですが、
申し訳ありませんが、再帰の作り方のコツ、
とさせて頂きます。

最初は単純な繰り返しを再帰で作られたら
如何でしょうか。

再帰は、まず、関数の最初で再帰が終わったか？
と問うのが一番のコツです。

例えば1から与えられた数までの合計では、

int sigma(n){
if(n==0)return 0; //再帰の終わり
return n+sigma(n-1);
}

int total = sigma(50); //こんな呼出しで

というように、繰り返しの終わりである
数値が0かどうかからチェックします。

なお、if(n==1)return 1;
としたら繰返し数が1回少なくなりますが、
私は0をコードした方が分かりやすいと感じ
ます。意見が分かれる所でしょう。

次に、この関数にはありませんが例外処理
を行います。全ての終了、例外チェックが
終わってから、メインの処理を行います。
この流れが再帰関数のパターンですね。
これを崩すと複雑な関数になりやすいです。

このコーディングを行うと、多分直ぐに気
づかれると思うのですが、ifの入れ子が激
減します。また、forの入れ子も激減します。
再帰は1つの関数で、forの2次元3次元処理が
こなせます。このあたりが再帰が考え易い、
ということにつながりそうです。

本当は数の合計などは再帰関数に向いている
とは言えません。多くの教科書が書いている
ようなアンポンタンな例で失礼しました。

再帰関数に向いている問題と言うのはありま
す。私はc++でしたら、クラスのインスタンス
が木構造にリンクされて、その木構造を手繰
りながら処理するような問題に、再帰関数は
もっとも力を発揮するのではないか、と考え
ています。

例えば計画問題。多くの要素をどのように並
べるともっとも良いか、という問題ですね。
a～eまでの5つの要素があったら、最初は
a～eまで可能性があり、二番目はaの次は
b～eまでの可能性があります。
これらを全ての可能性を表すと木構造になり
ます。この中からどれが良いか、と判断する
ような問題です。

要素数が10や20はそれほどではありませんが、
50とか100とかになりますと、超難解問題に突
入します。こんな時、再帰でないと私は処理が
考えられません。

しかし、少ししか書いていないようで、もう
長文になりました・・・

補足

おっしゃっている事は特にポイントだからわかるんですけど、
その判定を過ぎた後の中の処理をどう単純化させたらよいのかが不明です。

回答No.6

gau_puzzler

再帰を使うと考え方が簡単になるからです
たとえば迷路を解く問題を考えてみます
（コード的に足りない部分がありますが、考え方ということで）
実際に手で迷路を解くときはあちこち移動しては
「あ、行き止まりだ」
「さっきのところまで戻ろう」
・・・
というようにいったりきたりしながらプ解きますよね？
これをプログラムしようと思ったら非常に大変だと思います
ところが再帰を使うと非常にシンプルに組めます

　｜　｜
＿｜Ｂ｜＿
Ａ　　　Ｃ　
￣｜↑｜￣
　｜　｜

迷路を解く(位置）
{
　if (位置＝＝ゴール) {
　　ゴール();
　　おわり
　}
　if (左方行ける＆＆今まで通った道じゃない)
　　迷路を解く(左方);
　if (前方行ける＆＆今まで通った道じゃない)
　　迷路を解く(前方);
　if (右方行ける＆＆今まで通った道じゃない)
　　迷路を解く(右方);
}

回答No.4

tatsu99

そのことにより、コーディングするステップ数が劇的に減るからです。
その為、メンテナンス性が向上します。
そのかわり、処理速度が落ちる、スタックのオーバーフローの問題が発生する等の欠点もあります。
プロジェクトによっては、上記の弊害のため、再帰呼び出しのプログラムの作成を禁止しているところもあります。

回答No.3

black2005

例えば
(・・・(・(・・(・・・）・・・)・・・)・・・)のような複雑な計算をする場合
左括弧のたびに再帰呼び出しをし、右括弧のたびに処理を抜ける
これを繰り返す事によって、驚くほど簡単なコードで実現可能です。
また、理論的に無限の（ ）に対応できます。
再帰を使わずにやれと言われたら、悩んでしまいます。

プログラムを非常に簡潔化できますが、No.1さんのおっしゃる通り、知らず知らずに膨大なスタックを消費してしまう危険性があります。

回答No.2

Dxak

「再帰アルゴリズム」と対を成すのは「反復アルゴリズム」

すべての反復アルゴリズムは、再帰アルゴリズムにすることが可能
すべての再帰アルゴリズムは、反復アルゴリズムにすることが可能

再帰アルゴリズムの必要性は・・・タスクの分散化が、主な目的です
クイックソートだと、そのメリットが判りやすいのでは無いでしょうか？

Ａ～Ｂの部分をＣＰＵ１、Ｂ～ＣをＣＰＵ２で処理することが可能になってきます
反復であれば、Ａ～Ｂ～Ｃまで、ＣＰＵ１で処理することになり、ＣＰＵ２へ分散させることがコード上難しくなります

これにより、メモリ、ＣＰＵなど消費が大きくなる一方、より早い結果を出すことが可能になると言うことです
マルチコア、マルチプロセスが、一般化し始めた、今なら、分散化の意味がありますが・・・
一昔前の、シングルコアじゃ・・・意味を成さないので、反復アルゴリズムで、資源を小さく組んだ方が良かったと言う話

回答No.1

denbee

再帰呼出のメリット、デメリットについては以下に説明があります。
簡単に言うと、コードが直感的で簡略にできる場合があることがメリットで、
スタックに大量のメモリを消費してしまうのがデメリットです。

参考URL：

http://itpro.nikkeibp.co.jp/article/COLUMN/20061115/253812/