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


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

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

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

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2018/02/19 12:21:26
  • 終了:2018/02/24 16:35:03

ベストアンサー

id:grankoyan2 No.2

グラン只里予☆迂舞某回答回数88ベストアンサー獲得回数242018/02/19 22:34:14

ポイント60pt

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

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

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

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

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

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

長くなりました。

id:lionfan2

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

2018/02/19 23:10:12

その他の回答(3件)

id:salon_hiyake No.1

サロン日焼け回答回数6ベストアンサー獲得回数22018/02/19 12:48:06スマートフォンから投稿

ポイント30pt

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

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

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

id:lionfan2

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

2018/02/19 20:59:04
id:grankoyan2 No.2

グラン只里予☆迂舞某回答回数88ベストアンサー獲得回数242018/02/19 22:34:14ここでベストアンサー

ポイント60pt

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

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

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

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

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

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

長くなりました。

id:lionfan2

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

2018/02/19 23:10:12
id:pyopyopyo No.3

pyopyopyo回答回数361ベストアンサー獲得回数902018/02/19 23:39:29

ポイント25pt

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

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

id:lionfan2

pyopyopyo様、了解です。参考になります!!

2018/02/20 00:31:36
id:kaoato No.4

kaoato回答回数147ベストアンサー獲得回数622018/02/20 03:03:30

ポイント60pt

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


再帰呼び出しを含む手続きの処理の難しさ
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

id:lionfan2

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

2018/02/20 08:54:59
  • id:takejin
    単純に、”再帰が怖い”のではないかと思います。
    再帰の代表例として、フラクタル図形があります。あれ、なんだか怖くありません?
    際限なく小さい構造が、さらに小さい構造で覆い尽くされていく。自分の立ち位置が侵されて、さらに小さな領域へと連れて行かれる。その”際限なく続く手続き”が怖いのではないかと。
    存在するれ

    「私、今回で何回目の呼び出しなの?」
    「もう、わからないんだけど」
    「え、戻れるの私たち」
    「一応そのはずなんだけど」
    「ボクはもう一つ先に行くね」
  • id:lionfan2
    takejin様

    たしかにフラクタル図形は、もやっとする気持ち悪さを感じます。
    あと、入れ子構造が、人間にはあまり向いていないような気もします。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません