Python チュートリアル - 再帰関数
胡金庫
2023年1月30日
このセクションでは、Python の再帰関数について学習します。
Python 再帰関数とは
再帰関数はそれ自体を呼び出す関数であり、このプロセスは関数再帰と呼ばれます。
たとえば、数値の階乗を計算してみましょう（例： 6）。
6 * 5 * 4 * 3 * 2 * 1
次のコードでは、数値の階乗を見つける再帰関数が作成されます。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
a = 6
print("Factorial of", a, "=", fact(a))
Factorial of 6 = 720
関数 fact(n) は再帰的な関数です。fact 関数は、数値が 1 になるまで引数 n-1 で自分自身を呼び出します。これが階乗の計算方法です。つまり、数値に 1 より小さい階乗を掛けます。
この再帰関数には、数値が 1 になり、1 が返され、このようにして再帰呼び出しが有限になるという基本条件があります。
再帰関数を作成する場合、その再帰呼び出しを終了するための基本条件が必要です。
再帰の制限
お気づきのように、関数がそれ自体を呼び出すたびに、いくつかの中間値を格納するためのメモリが必要です。したがって、再帰関数は通常の非再帰関数よりも多くのメモリを消費します。Python は再帰呼び出しの制限を 3000 に設定します。
>>> import sys
>>> sys.getrecursionlimit()
3000
再帰が 3000 を超えると、RecursionError が発生します。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
Traceback (most recent call last):
File "<pyshell#2>", line 1, in <module>
print(factorial(4000))
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
[Previous line repeated 989 more times]
File "<pyshell#1>", line 2, in factorial
if n == 1:
RecursionError: maximum recursion depth exceeded in comparison
再帰制限を削除するソリューション
再帰制限を、必要な再帰よりも大きい数値に設定することで、再帰制限を解決できます。
import sys
sys.setrecursionlimit(5000)
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
再帰の利点
- 再帰関数を使用して、問題をサブ問題に分割し、簡単に解決できます。
- コードはすっきりときれいになります。
再帰の欠点
- 再帰関数のロジックをたどることが難しい場合があります。
- 各サブ問題を解決するには時間がかかるため、再帰関数は非効率的です。
