再帰を教えてもらった話

※だいたい実話です。師匠がた、ありがとうございました。

35歳無職ワイ

ワイ「今日もやる事ないわ〜」

ガチャッ。

師匠（26歳）「就職活動は進んどるんか」

ワイ「！？」
ワイ「はい！quizaという、プログラミングのテストを受けてそのランクを元に企業からスカウトが来るサイトで頑張ってます〜！」
ワイ「（酒飲まん日はな）」

師匠「ほんまか。ああいったサイトで問題を解くなら再帰を使えるようにしておくとすんなり解けることがあるで」

ワイ「はあ、そうでっか」

師匠「再帰は知っとるか」

ワイ「ワイがまた働き始めることでっか」

師匠「それは再起や」

ワイ「はい」

師匠「再帰いうんは、関数の中でその関数自身を使うことや」
師匠「正しくは再帰呼出しやな」

ワイ「そんな事したら無限ループになりまへんか」
ワイ「自分自身に手紙を書いて、その中に・・・」

前へ一歩進め。
そのあと、この手紙を初めから読み直せ。

ワイ「・・・って書いてあるようなもんやないですか」
ワイ「永遠に歩き続けなあきませんやん」

師匠「お前、意外と頭ええな」
師匠「せやから、終了条件を決めておかなあかん」

ワイ「はあ」

試しにやってみる

師匠「ほな試しに階乗を求める関数を書いてみい」

ワイ「階乗・・・5×4×3×2×1みたいなやつですか」

師匠「せや。言語はRubyでな」

def kaijo(n)
  #処理内容
end

puts kaijo(5)

師匠「こんな感じで使えるやつを書いてみるんや」

ワイ「ほなfor文でiを1ずつ増やすか減らすかしながら掛けていく感じですか」

師匠「それやと再帰呼出しをせえへんやろ」
師匠「再帰を使ってやってみるんや」

ワイ「ええと、kaijoっていう関数の中でkaijoを呼ぶと、そのkaijoの中でもkaijoが呼ばれるから・・・」
ワイ「アカン。夢の中の夢の中の夢の中の・・・みたいになって想像できまへん」

師匠「それが意外と簡単なんや」
師匠「5の階乗いうんは、5に対して4の階乗を掛ければ求まるんや」

ワイ「まあ、それが階乗ですから」

師匠「そしてその4の階乗いうんは、4に対して3の階乗を掛ければ求まるんや」

ワイ「はあ」

師匠「つまり階乗いうんは、元の数字に対して（元の数字-1）の階乗を掛けたもんなんや」
師匠「それが階乗の定義や」

ワイ「階乗を定義するのに階乗って言葉を使ってますやん」
ワイ「せやから、定義自体が再帰してますやんwww」

師匠「せや」

ワイ「えっ」

師匠「それが再帰のコツや！」
師匠「それをそのまま書くだけや」

def kaijo(n)
  return n * kaijo(n - 1)
end

puts kaijo(5)

師匠「基本はこれだけや」
師匠「5の階乗を求めるために、関数kaijoはさっきの定義どおり5 * (4の階乗)を返すんや」

ワイ「kaijoが完成してないのに、kaijoの中でkaijoを使うんでっか」

師匠「せや、自分自身を使う事でkaijoは完成するんや」
師匠「せやけど、さっきも言うた通り終了条件を決めておかんと無限ループになってまう」
師匠「階乗の終了条件は何やと思う？」

ワイ「5×4×3×2×1やから、1が来た時が終了ポイントですわ」

師匠「そうや」
師匠「せやから、こうや」

def kaijo(n)
  if n == 1
    # nが1の時は、再帰せずそのまま1を返す
    return n
  end
  # それ以外は再帰呼出しをする
  return n * kaijo(n - 1)
end

puts kaijo(5)

ワイ「ちょっとスマホアプリのどこでもRubyで試してみますわ」
ワイ「どこでもRuby〜！」
ワイ「実行、と」

どこでもRuby「実行結果：120」

ワイ「ホンマや！合ってるわ！（知らんけど）」

まとめ

師匠「まず5の階乗を求めるのに、4の階乗を求める」
師匠「その4の階乗を求めるのに、3の階乗を求める」
師匠「その3の階乗を求めるのに、2の階乗を求める」
師匠「その2の階乗を求めるのに、1の階乗を求める」
師匠「1の階乗は1って決まっとるからそのまま1を返す」

kaijo(5)
# ↓↓↓
5 * kaijo(4)
# ↓↓↓
5 * 4 * kaijo(3)
# ↓↓↓
5 * 4 * 3 * kaijo(2)
# ↓↓↓
5 * 4 * 3 * 2 * kaijo(1)
# ↓↓↓
5 * 4 * 3 * 2 * 1

師匠「こんな感じで、返す値の後ろのほうが段々と変身していく感じや」

ワイ「おお〜、再帰してますやん」

師匠「再帰を使うと一見複雑なゲームが一瞬で解けたりもするで」
師匠「なんてったって定義をそのまま関数に書くだけやからな」
師匠「合計の数を変数に入れて覚えておく必要すらあらへん」

ワイ「ホンマや。変数使ってへん」

師匠「あとは終了条件をif文で書くだけや」
師匠「（ホンマはもう少し別のパターンもあるけどな）」

ワイ「分かりました！」
ワイ「なんか感動しましたわ」
ワイ「再帰ってカッコエエ・・・再帰ハンパないわ・・・」

師匠「ええからおまえも早く再起せぇや」