再帰
プログラムを書くとき、特定の作業をするためにさまざまな関数を呼び出すことが多いです。たとえば、数値の平方根を計算するために
sqrt を呼び出したり、数値の最大・最小を求めるために max や min を呼び出したりします。再帰（Recursion）とは、自分自身の関数を再び呼び出すプロセスのことです。つまり、もし f という名前の関数を定義して、その関数の本体の中で再び f を呼び出していれば（通常は違う引数で呼び出します）、それは再帰呼び出しになります。def f(n): # fという名前の関数を定義
print(f'f() called with argument {n}') # 呼び出しのたびにprintする（デモ用）
if n <= 0: # nが0以下の場合は再帰を止める
print('Let\'s stop here...')
else: # そうでなければ、より小さい数でfを呼び出す
f(n - 1)
f(10)This is what the program would print
f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...これは、ごく基本的な再帰関数の実装を示すおもちゃの例です。実際のプログラムでは、単にメッセージを表示するだけではなく、関数の中で何らかの計算を行い、その結果を返すことがほとんどです。
アルゴリズムの問題では、グラフの扱いや高度なソートアルゴリズム、さらには後で学習するバックトラッキングなどで再帰が非常に役立つことがあります。再帰を使う問題は一般的で、場合によってはループを使った反復的な実装よりも再帰の方がはるかに実装しやすいことがあります。
大きな問題を、最も小さく・簡単な部分問題に分解していく手順は「再帰的飛躍の考え方（recursive leap of faith）」と呼ばれるコンセプトで理解するとわかりやすいです。
Recursive Leap of Faith
再帰的な解法を実装する際は、通常、あるタイミングで自分自身を呼び出す関数を作ります。この自分自身を呼び出す部分が再帰呼び出しです。
再帰のすばらしいところは、ある単純な引数で呼び出したときに正しく動くと「仮定」できることにあります。そこから、より複雑な引数について正しく動作させるように実装を進めるのです。ちょうど
sqrt や max, abs など別の関数を呼び出すのと同じように、いくつかの小さい・単純な引数に対して“正しく動くはず”とみなして、それを利用して今の計算結果を導きます。💡
ただし、必ずベースケース（最も簡単なケース）に到達できるようにする必要があります。そうでないと、再帰呼び出しが終わらなくなり、StackOverflow を起こしてしまいます！
再帰関数の中で何らかの計算を行う例として、与えられた数
n について 0, 1, 2, …, n の合計を求める処理を考えてみましょう。関数
sum を段階的に実装してみます。まず最初のステップとして、n が 0 や 1 のときに正しく合計を返すようにしましょう（n=0 や n=1 の合計を適切に求められるようにする）:def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # nが0の場合 => 合計は0
return 0 # ここで関数実行を止める
if n == 1: # nが1の場合 => 合計は1
return 1 # ここで関数実行を止める
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None（この部分はまだ実装していない）この実装があれば、
sum(0) はいつでも正しく 0 を返し、sum(1) はいつでも 1 を返すので、さらに先で sum(0) や sum(1) を再帰呼び出ししても正しく動作します。次に、
n = 2 や n = 3 のときの合計を、すでに実装した sum(1) と sum(0) を用いて書いてみます。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # nが2のときは sum(1) の結果に2を足す
return n + sum(1) # または n + sum(n - 1)
if n == 3: # nが3のときは sum(2) の結果に3を足す
return n + sum(2) # または n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None（まだ実装していない）このように、
n が 0, 1, 2, 3 の場合については、正しく結果を返すようになりました。これを踏まえて、
n が 4 や 5、6 のようにもっと大きな値の場合の合計を求めるには、sum(3) までの結果が正しいと“仮定”して、そこに 4 を足したり、5 を足したりして結果を得ます。つまり、n が 4 以上では、 sum(n - 1) に n を足す実装をすればよいのです。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# それ以外（4, 5, 6, ...）の場合
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...再帰関数では重要なポイントが次の2つです：
- ベースケース：再帰を止める条件。これがないと関数は無限に呼び出され、ループから抜けられません。
ここでは
n == 0やn == 1がベースケースです。
- 再帰ステップ：関数が（通常は異なる引数で）再び自分自身を呼び出す部分。
ここでは
sum(n - 1)がそれに当たります。
また、
n == 1、n == 2、n == 3 のような呼び出し結果は、n == 4、n == 5 などと同じ形になるため、ベースケースを 1 つ（たとえば n == 0 のみ）に簡略化することもできます。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...このように、再帰的飛躍の考え方で「小さい・簡単なケースで正しく動く」と信じ、その部分を土台として大きな問題を解決していきます。再帰関数の仕組みや実装手順を理解するうえで、この考え方が非常に役に立ちます。
💡
再帰呼び出しをするということは、実質的には“別の関数”を呼び出していると考えて構わないということです。その関数が与えられた引数で確実に正しく動くと信じられればOKです。
Challenge
再帰的な方法で
n! を計算し、それを で割った余りを求める関数を実装してください。入力
入力として整数
n（1 ≤ n ≤ 1000） が与えられます。出力
n! を で割った際の結果を出力してください。Examples
Input | Output |
5 | 120 |
10 | 3628800 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB