再帰関数とは、自分自身を呼び出す関数のことです。例えば、階乗を求める関数は、次のように再帰関数で書くことができます。
階乗を求める再帰関数のコード例:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
再帰関数の基本的な考え方は、問題を小さな問題に分割して、分割した問題を自分自身に渡すことです。また、再帰関数には必ず終了条件が必要です。終了条件とは、再帰呼び出しを止めるための条件のことです。2 上記の例では、n == 0が終了条件になっています。
Pythonでは、再帰関数を使って順列や組合せなどの列挙もできます。順列とは、ある集合からn個の要素を選んで並べる方法のことです。 組合せとは、ある集合からn個の要素を選ぶ方法のことです。例えば、{a, b, c}から2個の要素を選んで並べる順列は、ab, ac, ba, bc, ca, cbの6通りです。 同じ集合から2個の要素を選ぶ組合せは、ab, ac, bcの3通りです。
順列や組合せを求める再帰関数のコードは以下のようになります。
順列や組合せを求める再帰関数のコード例:
# 順列
def permutations(lst, n):
if n == 0:
return [[]]
else:
result = []
for i in range(len(lst)):
rest = lst[:i] + lst[i+1:]
for p in permutations(rest, n-1):
result.append([lst[i]] + p)
return result
lst = ["a", "b", "c"]
n = 2
print(permutations(lst, n))
# 組合せ
def combinations(lst, n):
if n == 0:
return [[]]
elif len(lst) < n:
return []
else:
result = []
for i in range(len(lst)):
rest = lst[i+1:]
for c in combinations(rest, n-1):
result.append([lst[i]] + c)
return result
lst = ["a", "b", "c"]
n = 2
print(combinations(lst, n))
