再帰呼び出しはなぜ必要か？
プログラミングの授業で『関数の再帰呼び出し』を習うと思う。実例で言うと、先生が↓なコードを示した上で「こういう関数を作れば階乗(n!)が計算できます」と説明する。
int fact(int n) { if(n==0) return 1; return n*fact(n-1); }
しかし学生は↓なコードを書いて全く納得がいかないと言う。
int fact(int n) { int ans=1; for(int i=2;i<=n;i++) ans*=i; return ans; }
「ループで済むから再帰は必要なくね？」「てか再帰はスタックオーバーフローするから使いにくくね？」と感じるわけだ。ここで再帰の利点を明快に答えれる先生はそんなに多くない。
そこで今日はその明快な説明を頑張ってみる。まず↓のQ1を考えてみよう。
Q1. 3桁のルーレットがある。各桁は0〜9まである。桁の合計がtotalでアタリ！となる。アタリは何パターンあるか？。
簡単な探索問題だ。探索ビギナーにはちょうどよい練習問題だと思うのでぜひ挑戦してみて。・・・で、オレは↓のコードを書きました。
int search(int total) { int ans=0; for(int i=0;i<10;i++) for(int j=0;j<10;j++) for(int k=0;k<10;k++) if(i+j+k==total) ans++; return ans; }
3桁だから3重ループで全部調べ上げれば良い。これといって特に難しいところはないね。・・・じゃあ↓はどうでしょう。
Q2. r桁のルーレットがある。各桁は0〜9まである。桁の合計がtotalでアタリ！となる。アタリは何パターンあるか？。
さっきと一文字しか変わってない。しかし少し考えると、r重ループを簡単には作れないことに気づくはず。・・・でお分かりのように、ここで再帰がダダーン！と登場するわけだ。
int search(int r,int total) { if(r==0)//全ての桁を処理し終わった { if(total==0)//ちょうどtotal分消化してるからパターンとしてカウント return 1; return 0; } int ans=0; for(int i=0;i<10;i++) ans+=search(r-1,total-i);//☆再帰呼び出し return ans; }
コードが少し難しくなった。再帰を理解するうえで大事なのは、関数の中身を最初は考えずに何を渡すと何を返すのか？（引数と返値）だけに注目すること。例えば search(r,total) なら「r桁のルーレットで合計がtotalになるパターン数を取得できる」とだけ理解する。同様に search(r-1,total-i) なら「r-1桁のルーレットで合計がtotal-iになるパターン数を取得できる」と考える。自動販売機で中がどう動いてるか考えて使ってないでしょ？。それと同じで、「何を入れると何が出てくるのか」だけ考えよう。☆部のsearch()の中身を追っかけてはダメね。ビギナーが陥りがちなのが「えーと、ここでsearch()が再び呼ばれて、関数の頭に戻って、下のreturnで戻るときに、前のsearch()のfor文の中に戻るので・・・あれ？このansってどのans？」ってなる（笑）から、関数の中身を一行一行追わないことが凄く大事。
というわけでまとめですが、ループが何重になるか不明な場合に再帰が便利と覚えておきましょう。*1
