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

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

ﾌﾟﾛｸﾞﾗﾏの数学､の再帰の6章
https://www.amazon.co.jp/exec/obidos/ASIN/4797395451/hyuki-22/

愚痴をﾌﾞﾛｸﾞで書いたので､回答としては簡潔にまとめるように努力しますが､

･そもそもｸｲｯｸｿｰﾄが難しい(分岐条件が理解しづらい)
･扱うﾃﾞｰﾀが多いからめんどい(挫折する
･一直線な(徐々に狭まっていく)再帰ではない

のが原因なのかなｰと思います｡
なぜ？ については上述の理由で｡

【人類の思考法とは本質的に相性が悪い】
については､本質的ではないだろうが､ｷｬﾊﾟを超えやすいという理由があるんだろうと思います｡

今､適当に検索したら､再帰処理ってﾙｰﾌﾟでも書けるという言説を読んだのですが､ﾙｰﾌﾟだと終了条件がわかりやすい､ﾙｰﾌﾟ毎の変化が直感的に捉えられる､分岐などしない(してもなんとなく理解しやすそう)というﾒﾘｯﾄがあるのに比べ､再帰だと､その辺りがもやｰんとするんだろうなｰって思いました｡

次のﾙｰﾌﾟに入る時の状態と､次の再帰に入る時の状態を考えると､ﾙｰﾌﾟの方がなんとなく理解しやすいだろう(だからﾙｰﾌﾟで書けるならﾙｰﾌﾟで書く)｡
そもそも再帰を利用すべきｹｰｽって結構限られているのかも知れないですね｡
ｿｰｽは洗練されたふうに見えますが､可読性はかなり落ちますし｡

長くなりました｡

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

私なら
1) 分割統治法の説明 (ここで再帰の説明)
2) 分割統治法をｿｰﾄに使ってみましょう
3) これをｸｲｯｸｿｰﾄと呼びます
という感じで説明します

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

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