人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

【なぜ再帰は難しいのか】

ソートのプログラミングを教えていると、「クイックソート」で苦労する学生が多いようです。自分も苦労しました。

再帰という考え方が、階乗やフィボナッチ数列よりも複雑なものになると、少なくとも自分は、とたんに理解に苦労してしまいます。

何か「再帰」には、人類の思考法とは本質的に相性が悪いといった、特別な理由があるのでしたら教えてください。

●質問者: lionfan2
●カテゴリ:コンピュータ 科学・統計資料
○ 状態 :終了
└ 回答数 : 4/4件

▽最新の回答へ

1 ● サロン日焼け
●30ポイント

自分も、再帰では苦労してきた口の人間です。再帰を使うときは、「再帰脳」とでも言うような特別な状態にならなければならないと感じます。(得意な人もいるので、人間一般の脳とは関係ないかも)自分がやる時は、ここを読み返して、「再帰脳」になってから始めます。

http://ylb.jp/2007b/proc/recursion/

プログラマの数学、の再帰の6章
https://www.amazon.co.jp/exec/obidos/ASIN/4797395451/hyuki-22/


lionfan2さんのコメント
salon_hiyake様、ご回答ありがとうございます。 自分と同じように感じていた方が他にもいらして嬉しいです。 結城先生の本は、自分もお気に入りです。ありがとうございます!!

2 ● グラン只里予☆迂舞某
●60ポイント ベストアンサー

愚痴をブログで書いたので、回答としては簡潔にまとめるように努力しますが、

・そもそもクイックソートが難しい(分岐条件が理解しづらい)
・扱うデータが多いからめんどい(挫折する
・一直線な(徐々に狭まっていく)再帰ではない

のが原因なのかなーと思います。
なぜ? については上述の理由で。

【人類の思考法とは本質的に相性が悪い】
については、本質的ではないだろうが、キャパを超えやすいという理由があるんだろうと思います。

今、適当に検索したら、再帰処理ってループでも書けるという言説を読んだのですが、ループだと終了条件がわかりやすい、ループ毎の変化が直感的に捉えられる、分岐などしない(してもなんとなく理解しやすそう)というメリットがあるのに比べ、再帰だと、その辺りがもやーんとするんだろうなーって思いました。

次のループに入る時の状態と、次の再帰に入る時の状態を考えると、ループの方がなんとなく理解しやすいだろう(だからループで書けるならループで書く)。
そもそも再帰を利用すべきケースって結構限られているのかも知れないですね。
ソースは洗練されたふうに見えますが、可読性はかなり落ちますし。

長くなりました。


lionfan2さんのコメント
grankoyan2様、ブログ拝読いたしました。素晴らしい。 たいへんい記事でした。BAの最有力候補です!!

3 ● pyopyopyo
●25ポイント

学生さんに分割統治法の説明はしましたか?
再帰を難しく感じるのは分割統治法を理解していないからだと思います

私なら
1) 分割統治法の説明 (ここで再帰の説明)
2) 分割統治法をソートに使ってみましょう
3) これをクイックソートと呼びます
という感じで説明します


lionfan2さんのコメント
pyopyopyo様、了解です。参考になります!!

4 ● kaoato
●60ポイント

>何か「再帰」には、人類の思考法とは本質的に相性が悪いといった、特別な理由があるのでしたら教えてください。


再帰呼び出しを含む手続きの処理の難しさ
http://www.jcss.gr.jp/journal/vol06/060403/060403.html

ところが,人間にとって再帰は困難な課題であることが多くの先行研究から報告されて いる[Anderson, Pirolli, FarrellAnderson et al.1988,谷川市川谷川市川1996].その理由を整理すると以下の2つが考えられる.

第1は,概念のわかりにくさである.つまり,手続きの途中でその手続き自身が呼び出 される「再帰呼び出し」構造の把握が困難なのである.第2は,処理の難しさである. 再帰呼び出しされると,その時点の環境 (変数状態,戻る位置) を保持しておき,再帰 呼び出しで処理された手続きを終えて,元の手続きに戻るときにその環境を取り出す 必要があるので,ワーキングメモリ (working memory) に負荷がかかるという点が あげられる.

http://www.jcss.gr.jp/journal/vol06/060403/node2.html#SECTION00022000000000000000


Java8であれば関数型インターフェースがあるのでそちらを使用したほうがもっとらしくかけるのかな?
あくまでここでは手続き型ではループで処理で状態変数を使用しているのに対し、関数型では再帰処理で状態変数を使わずに処理をしているよということを伝えたいので細かい部分は気にしないでください。

http://www.sassy-blog.com/entry/20171130/1512002019


lionfan2さんのコメント
kaoato様、今回の質問に、いちばん聞きたかったことへの回答でした。 ありがとうございます!!
関連質問

●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ