なぜ？
という点に置いては、例に上がった簡単な奴、
・階乗
・フィボナッチ数列
が逆に何故、わかりやすいのか？ ということを考えると、
『終了条件』にスポットが当たると思います。私的には。
階乗は、１で終れますし、フィボナッチ数列（n番目の数を出力）だと、０、１の組み合わせになったら終わりというのがわかりやすいです。
クイックソートは、どこで終わるの？ というのが見えなくて、パニックになりそうです。
というか、実際に大分にプログラムからブランクがあってちょっとお酒飲んで頭が回らない状態で、ウィキペディアのクイックソートの項目を読むと理解に苦しみました。
クイックソートの再帰がややこしいのは、配列があって、ピボットがあって、分割があってと、扱うデータが沢山あるのも理由かもと思いました。
わかりやすい≒直線的な何かを再帰するパターン、わかりにくい≒階層が深まると二次元的な広がりを見せる のようなイメージですかね。
・再帰の戻って来るタイミングがわかりづらい
・扱うデータ（の概念というか条件？）が多い
・分割など一直線ではない処理
などで、再帰が理解困難になってると思います。
ここからは蛇足なんですが、素人に近い学生なようなこにプログラミングを教える時、ポインタやら再帰やら（もっと言えばループ処理やら）で躓くのは、そのこにとって、ビジョンが浮かんでいないからなんだろーなと思うことが多々ありました。
条件分岐などは、分岐の数がわかって、条件がわかるから理解できるのですが、アドレスを持ちこむと、迷子になるのです。そういう時は図にしたら理解できたりもしますよね。
再帰って一直線に（なんていうかわかりませんが）潜って行く時には、グラフィカルに感じ取れるんですが、クイックソートみたいに分岐が発生しだすと、想像しづらい、追いきれない、追いつかないからギブアップという流れになってそうです。特にクイックソートは分岐条件がわかりづらい。
っていうかそもそもクイックソートが難しいんですよー。
バブルソートで再帰するとかしたら、一回目のソートで最高の数字が右端に行くので次の再帰呼び出しは、要素数を一つ減らして右端は無視して……と結局一直線での理解になると思います。（簡単だからこそ多重ループで片が付くのでしょうけれど）
バブルソートや選択ソートで再帰を組むとしたら、わかりやすくなる理由は、直感的に理解しやすい『次の再帰では要素数が減っている』からなんだろうなと思います。
結局、前と後の再帰条件の違いがわかりにくく、分岐するのがわかりにくい原因なのだろうと。
【人類の思考法とは本質的に相性が悪い】
扱うデータが増えると理解しづらいですし、一直線ではない処理は追いにくいです。
ここからはさらに脱線するんですが、
・データ量増
・分岐の数
で考えると、人類の思考云々に関わらず、予測や対策が難しくなります。
高校生の大学入試だけで言えば、過去問、学習範囲という限られた中で予測、対策が取れますが、特定の職業に就きたい、とある企業に就職したいとかになると、考えることが増えますから。
多分、再帰自体に罪は無いんです。
再帰で躓く人は、他でも躓きますから。
イメージ力というか想像力の個人の限界を超えてしまうことに問題があるんだと思います。
わたしは、むかし趣味でプログラミングしてた時に、再帰プログラムの美しさに惹かれて、意味があったかなかったかはわかりませんが、むやみに再帰処理を組んでた時期がありました。
でも、今思うと、分岐については導入してなかったなぁと。
分岐しだすとややこしくなり過ぎるっていう自分の能力の限界と、読む人がいればすごくわかりづらくなるんだろうなーっていう後悔があります。
駄文
