累乗（再帰）
2 の 3 乗は 8、3 の 4 乗は 81。累乗を再帰で書きます。ここまでと違うのは、引数が 2 つあることです。2 つあると「どちらを縮めるか」を取り違えやすくなります。
縮める引数を間違えると、止まらない
引数を 2 つ取る再帰を書いてみます。止まる条件は b を見ていて、縮めているのは a です。
Python
def f(a, b):
if b == 0:
return 1
return f(a - 1, b)f(5, 3) を呼ぶと、a は 5, 4, 3, 2, 1, 0, -1 と減っていきますが、b はずっと 3 のままです。b == 0 に永遠に届かないので止まりません。
動かしている引数と、止まる条件が見ている引数が食い違っているのが原因です。止まる条件が見ている引数を縮める。引数が何個あっても、確かめることはこれだけです。
残りの引数はそのまま渡す
正しく縮めた形も見ておきます。文字列を指定回数だけ表示する関数です。
Python
def repeatMessage(text, times):
if times == 0:
return
print(text)
repeatMessage(text, times - 1)text は毎回そのまま渡し、times だけを 1 減らします。呼び出しはこう並びます。
プレーンテキスト
repeatMessage("hi", 3)
repeatMessage("hi", 2)
repeatMessage("hi", 1)
repeatMessage("hi", 0) -> ここで止まる左の引数は 4 回とも同じで、右の引数だけが 0 へ向かっています。累乗も同じ形で、底は最後まで変わらず、指数だけが減っていきます。
引数が 2 つ並んでいると、つい両方を動かしたくなります。動かすのは片方だけ、と決めてから書き始めてください。呼び出しを 3 段ぶん紙に書き出して、変わらない引数と減っていく引数を指差せるなら、その再帰は止まります。
指数が 1 で止めると、0 乗に答えられない
もう一つの落とし穴が、止める位置です。「1 乗なら底そのもの」と考えて指数が 1 のところで止めたくなりますが、これだと指数 0 で呼ばれたときに条件を素通りして、-1, -2 と降り続けます。
数学では、どんな数でも 0 乗は 1 と決まっています。0 をこれ以上分解できない最小のケースとして扱えば、指数が 0 のときも 1 以上のときも、同じ 1 本の関数で処理できます。テストにも 5 の 0 乗が入っているので、ここを取り違えると 1 件だけ落ちます。
「1 個手前で止めたほうが分かりやすいのでは」と感じたときは、その 1 個手前より小さい入力が来ないかを必ず確かめてください。最小のケースは、思っているより一段下にあることが多いです。止める位置を一段下げておくほうが、たいていの場合は安全です。
引数が増えたら、関数の 1 行目に「止まる条件が見ているのはどの引数か」をコメントで書いておくと、後から読み返したときに迷いません。
要件
- 関数
power(base, exp)を実装し、整数値を返す - for / while を使わず、必ず再帰で実装する
- 基底ケースは exp == 0 のとき 1 を返す
入出力例
power(2, 3) → 8
power(5, 0) → 1
power(0, 5) → 0
power(3, 4) → 81
power(2, 10) → 1024
power(1, 7) → 1ヒント
