再帰呼び出しを使いますか？

質問

趣味でプログラムをかじる程度なのですが、今まで自分はプログラムを作っていて再帰呼び出しを使ったことがありませんが、みなさんは良く使うのでしょうか？

なかなか再帰呼び出しを考えるのが難しく自分のプログラムで適用すると良いところなど思い浮かびません。
再帰呼び出しをすると何か利点とかあるのでしょうか？
再帰呼び出しで無いと作るのが難しいプログラムなど今までありましたか？あればどんな処理だったかなど教えてください。

回答No.8

sawya · ベストアンサー

すでにいっぱい回答がついていますが、わたしもつられてしまいました。
思うに、「1つ処理するごとに処理対象が減っていく」ものはループがとくいで、
- 処理対象全体をつかめない
- 1つ処理すると、残りの処理対象が増えたりする
- しかも増えた分は、元のものと構造が似ている
という場合に再帰呼び出しの方が簡単にかけるんだと思います。
みなさんが挙げている階層フォルダみたいなツリー構造は、まさにこの典型例ですね。

お礼

回答ありがとうございます。
とても、わかりやすい。
自分は再帰呼び出しをどういうところで適用するのか、適用するべきなのかということがわかっていませんでした。
挙げてもらったことを頭に入れておくとよさそうですね。勉強になります！

回答No.7

jacta

よく使うとはいえませんが、使うことはそれなりにあります。

再帰を使わなくても難なく書けるようなことに、わざわざ再帰を使う必要はありません。よく再帰の例に出てくる階乗の計算などは、単なるループか表引きにした方がよいので、再帰を使う必要はまったくありませんね。

逆に、再帰でなければ書けないか、無理をして再帰を使わずに書いても著しく煩雑になったりする場合は、迷わず再帰を使います。
具体的には、構文解析（Interpreterパターンの実装には不可欠です）とか、ディレクトリ等の階層構造の処理、マルチウィンドウの描画、テンプレートメタプログラミングにおけるメタ関数の実装（これは静的な再帰ですので、他の例とは別格です）などです。

お礼

回答ありがとうございます。
再帰呼び出しちゃんと理解して使えるようになる必要ありそうですね。
いくつか練習プログラム作って勉強したいとおもいます。

回答No.6

Quant

簡単なツール程度では使いますが、仕事で使ったことはありません。
利点はソースや実行ファイルがコンパクトになる。ソースもわかりやすい(再帰が理解できていれば)。
欠点は関数のオーバーヘッドで非効率になったり、ネストが深くなりすぎてスタックオーバーフローなどの問題が出る場合がある。

補足

回答ありがとうございます。
再帰自体あまり使われることないのでしょうかね。
わかりやすいコードはいいですね。再帰理解できるようになります！

関数のオーバーヘッドということは良く耳にしますが。
関数を呼ぶと実際どういうことで遅くなるんでしょうかね？
引数を多く渡すためにPUSH命令やPOP命令が出てくるからなんでしょうか？
スタックオーバーフロー聞いたことあってもどういう状況ででるのか知りませんでした。Wikipediaで調べて納得です。

回答No.5

asuncion

問題自身が再帰的に表現してある場合、
再帰的なコードを書くことがあります。
ただし、そうすることで、非再帰的なコードを書いた場合より
実行時の効率が落ちることがあるので注意が必要です。

例）フィボナッチ数列を求める場合、再帰的に書けば楽ですが、
実行時の効率は非再帰的なコードの方が上です。

補足

回答ありがとうございます。
再帰呼び出しのほうが実行時の効率が悪いんですね。
CALL命令とJMP命令の差でしょうか？
アセンブラなどでよくコードを見ているのですが、どちらの命令のほうが早いのかなどまったくわからないのでそういったことを調べる方法ってあるんですかね。

回答No.4

cametan_42

＞みなさんは良く使うのでしょうか？

う～～ん。「何からプログラミングをはじめた」からによって随分変わるとは思いますがね。
Lispなんかでプログラミングをはじめると割に難なく再帰書くと思いますよ。
逆にCのような「手続き型」ではじめるとそんなに馴染みが無い、とは思います。

＞なかなか再帰呼び出しを考えるのが難しく自分のプログラムで適用すると良いところなど思い浮かびません。

再帰って簡単だと思うんですけど(笑)。
まあ、「慣れ」もあるでしょうが、根本的に「再帰の方が考え方として自然」です。言い方変えると「プログラミング初心者の方が思いつきそうな」直球的な方法論だと思いますね。「繰り返しする為に作ってる最中のプログラムを呼び出す」なんてのは至極単純な方法論です。
要するに、再帰なんてのは単なる「繰り返し」の一形式ですし、むしろプログラミング初心者が一番難しい、って感じるのがfor文なんかの特殊な「繰り返し構文」なんですよ。もう「その時の感情」を覚えてないかもしれませんが(笑)。
典型的なfor文なんかで「ガリガリ書く」練習するから、再帰が「馴染みがなくて」「難しい」と感じるだけ、なんだと思います。やっぱり「慣れの」問題なのです。

＞再帰呼び出しをすると何か利点とかあるのでしょうか？

利点は無い、です(笑)。と言うかプログラミング言語や実装次第、でしょう。
例えば、C言語でもgccなんかの処理系では、最適化指定に依っては末尾再帰を見るとjunp構文に自動に変換してくれて効率的なコードを生成してくれるようですが、当然言語仕様じゃないわけです。
一般に、上記のような「末尾再帰最適化」してくれる仕様を持った言語の数は少ないんで、そう言う意味では特にメリットは無い、と思います。
別に、例えばHaskellのような関数型言語だと再帰は必須でしょうね。これも言語次第、です。一般論で言うと難しいです。

＞再帰呼び出しで無いと作るのが難しいプログラムなど今までありましたか？あればどんな処理だったかなど教えてください。

クイックソートとか?
他には数値計算でも数式の流れなんかは再帰用いた方が「翻訳」はラクですね。いずれにせよ、#1さんが仰ってる通り、ピュアなアルゴリズムに「より近い」場合に「再帰の方が書くのがラク」って現象はあると思います。「繰り返し構文」に翻訳するのがメンド臭かったりして(笑)。

いずれにせよ、再帰は「繰り返しを実現する為の一形式に過ぎない」んで、あんま考え込む必要って無いですよ(笑)。

お礼

回答ありがとうございます。
for文より再帰呼び出しのほうが簡単？！
自分は再帰呼び出しのコードなど見ると、結果がどうなるのか考えるがとても大変です。しかもそれを自分で作れと言われるともうお手上げです。
再帰呼び出しは繰り返しの一形式！いいこと聞きました。

回答No.3

nda23

リカーシブコールでよくあるパターンとしては以下のパターンです。
(1)A地点からZ地点まで順路を示す。
(2)サブフォルダ内の全ファイルを検索する。
(3)つり銭を求める。（実際は有価証券で手持ち分から必要数を得る）
例えば、以下はVBScriptで、フォルダ内の全ファイル名を列挙します。
Dim FSO
Set FSO = CreateObject("Scripting.FileSystemObject")
Recursive FSO.GetFolder("C:\") '再帰処理にフォルダを渡す
'***フォルダ内の処理（再帰処理）***'
Sub Recursive(Folder) 'パラメータのFolderを処理するDim OBJ
For Each OBJ In Folder.SubFolders 'フォルダ内のフォルダ（複数）を１個ずつ処理する
　　　　Recursive OBJ 'サブフォルダの１つを処理する（自身を呼び出す）
Next
For Earch OBJ In Folder.Files 'フォルダ内のファイル（複数）を１個ずつ処理する
　　　　WScript.Echo OBJ.Path 'ファイルのパス名を表示する
Next
End Sub

何重にもネストしたフォルダの最深部まで検索するという命題に、
「再帰処理を使わずに」という条件が付いた場合、かなり面倒な
コードになると思います。
次につり銭問題ですが、1000円で300円の買い物をした場合のおつりは
700円ですね。常識的には100円硬貨7枚より、500円と100円×2の方が
良い訳です。でも、手持ち硬貨に100円が１枚しかなかったら？
「じゃあ50円×2」となります。でも、50円も１枚だったら、今度は
10円×5ですね。このようなことは人間には瞬時に分かることなので、
詳しく掘り下げないのですが、コンピュータはそうはいきません。
こういう考え方の手順を整理すると、どうなるでしょうか？

再帰処理はコードを簡潔にするという意味があり、バグ発生比率、
保守性という面で効果があります。上記の命題も再帰処理を使わ
なくても結果を出せると思いますが、他人がみても分からないような
コードになるでしょう。
実際、何人かの面倒を見なければならない上級SEにとって、他人の
コードを追うという任務があります。どっちが楽かは言うまでも
ありませんね。

お礼

回答ありがとうございます。
再帰処理でコードを簡素になるんですね。
これからうまく再帰処理を適用できる場面で適用できるようになりたいです。

回答No.2

buriburi3

Tree構造のデータを辿るような場合には普通に使います。
よく知られる例だとクイックソートとか、#1の人が書いてるディレクトリー検索とか。
階層構造を持つオブジェクトのシリアライズなども普通に書くと再帰呼び出しになります。
再帰呼び出しを使わずに書くと、自前でなんちゃってスタックを作らなければならなくて面倒くさい(難しい訳ではない)です。

再帰呼び出しには欠点もありますし、必要も無いのに無理に使うものでもないです。
必要があれば自然に再帰呼び出しになってると思います。

お礼

回答ありがとうございます。
必要があれば自然に再帰呼び出しになっているとはすごいですね。
再帰呼び出しを自然に使えるよう練習したいと思います。

回答No.1

kkk1024

こんばんは。３０代男偽ＳＥです。
面白いタイトルですね。つられちゃいました。（＾＾）
多分検索すればいくつか出てくると思いますのでそちらも参考になさってください。

さて、再帰呼び出しですが、私が見たことがあるのはディレクトリ、ファイル検索などの階層構造を検索するロジックですね。
他に使われているものも、恐らく親子関係があって不特定多数の階層構造があるようなものが多いのではないでしょうか。
利点はコーディング量が減るぐらいだと私は思います。

私も自分でわざわざ再帰呼び出しを適用すると良いところは思いつきません。
利点よりも逆に後で参照した時に分かり辛いのではないかという欠点の方が気になりますね。
どうしてもコード的に量を減らさなければならない状態でなければ使わないでしょう。
まあ、質問者様は職業でなされている訳ではないと思いますので、試みに使うのには良い材料だとは思います。

私の場合、部下がわざわざ使おうとしていたので、再帰を利用しない形にもできると指導したことがあります。
まあ、私が後で見てわからないというのが大きな理由ですが（＾＾）

再帰を多用しようとする人の傾向として、アルゴリズム至上主義というか「如何に複雑なアルゴリズムを選定して利用したか？」を強調したい人が多いように思います。そんな方は「それぐらいのアルゴリズム知っていて当然！」という思想の方が多いため、当然コメントもほとんどありません。（＾＾）
だから、後で見るとそれが再帰なのかを判断しなくてはならないというコストがかかってしまいます。
という経緯もありまして私の場合は使わないように指導しております。

まあ、何にしても質問者様が職業プログラマを目指しているのであれば、コードは皆が読むものであること、将来に再利用されること、横の広がりや未来への広がりを意識し、できるだけコストがかからないコーディングをなされると良いと思います。
読み易くシンプルで良いコードは将来に再利用される可能性が高いでしょう。

あまり参考にならないかもしれませんが、経験談のようなものを書いてみました。
眠れないためこんな時間に書いております。乱文ご容赦ください。ありゃ、書いている間に空が白んできましたね。それでは。

お礼

回答ありがとうございます。
親子関係ですか。とても良いヒントになりそうです。
再帰呼び出しを使ってプログラムを書きたいというのではなく、再帰呼び出しを使うとシンプルになるという理由で使うものなんですね。

再帰呼び出しを使うと良い場所などまだ頭が働いてズバットと使えそうにないのでいくつか自分で作って再帰呼び出しが使える頭になろうと思いました。
再帰呼び出しを下手に使うと可読性悪くなるのはだめですね。

参考になりました。