【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
第5章 再帰的アルゴリズム
再帰とは
自身を含んだり、自身を用いて定義されていたりする場合、再帰的であると言われます。
再帰の考え方を利用すると自然数は、
・1は自然数である。
・ある自然数の直後の整数も自然数である
という再帰的な定義ができます。(再帰は第6章、第9章で利用する)
階乗値
再帰を用いるプログラム例として最初に取り上げるのは、非負の整数値の階乗値を求める問題です。
非負の整数nの階乗は、
0! = 1
n > 0 ならば n! = n x (n - 1)!
と定義されます。
#非負の整数の階乗値を求める
def factorial(n: int) -> int:
"""非負の整数nの階乗を再帰的に求める"""
if n > 0:
return n * factorial(n - 1)
else:
return 1
if __name__ == '__main__':
n = int(input('何の階乗：'))
print(f'{n}の階乗は{factorial(n)}です。')
| コラム5-1 math.factorial関数 |
|---|
math.factorial(x)は、整数xの階乗値を返却します。xが負、非整数であればValueError例外を送出します。
再帰呼び出し
関数factorialは、n-1の階乗を求めるために関数factorialを呼び出します。これが再帰呼び出しです。
直接的な再帰と間接的な再帰
関数factorialのように、その内部で関数factorialを呼び出すのが直接的な再帰で、関数aが関数bを呼び出しあう構造が間接的な再帰です。
再帰的アルゴリズムが適しているのは得べき問題や計算すべき関数あるいは処理すべきデータ構造が再帰的に定義されている場合です。
そのため、再帰的手続きによって階乗値を求めることはあくまで一例で現実的には適切ではありません。
ユークリッド互除法
二つの整数値の最大公約数を再帰的に求める方法を考えます。二つの整数値を長方形の2辺の長さと考えると二つの整数値を求める問題は次のような問題になります。
長方形を正方形だけで埋め尽くすとき、正方形の最大の辺の長さを求めよ。(埋め尽くせない場合は埋め尽くすことができるまで繰り返す)
これを式に直します。
二つの整数x, y
最大公約数 gcd(x, y)
としたとき、
x = az
y = bz
を満たす整数a,bが存在するとき
最大の整数 z = gcd(x, y)
となります。つまり、
y が 0 であれば…x
そうでなければ…gcd(y, x % y)
となり、これをユークリッドの互除法と呼びます。
#ユークリッドの互除法によって最大公約数を求める
def gcd(x: int, y: int) -> int:
"""整数値xとyの最大公約数を求めて返却"""
if y == 0:
return x
else:
return gcd(y, x % y)
if __name__ == '__main__':
print('二つの整数の最大公約数を求めます。')
x = int(input('整数：'))
y = int(input('整数：'))
print(f'最大公約数は{gcd(x, y)}です。')
| コラム5-2 math.gcd関数 |
|---|
math.gcd(a, b)はaとbの最大公約数を返却する、mathモジュールのgcd関数です。gcd(0, 0)のときは0を返します。
5-2 再帰アルゴリズムの解析
#真に再帰的な関数
def recur(n: int) -> int:
"""真に再帰的な関数recur"""
if n > 0:
recur(n - 1)
print(n, end='')
recur(n - 2)
x = int(input('整数を入力せよ：'))
recur(x)
このように再帰呼び出しを複数回行う関数を真に再帰的であるとよばれ、挙動が複雑になります。
ここで、関数recurをトップダウン解析とボトムアップ解析を手法として解析します。
トップダウン解析
上流に位置する呼び出し側から始めて、段階的に詳細に調べる解析手法
list5-3ではrecur(4)のとき、recur(3)を実行、4を出力、recur(2)を実行という順で行われます。この時recur(3)ではさらにrecur(2)、3を出力、recur(1)となります。このようにてっぺんから解析すると下流に同様の解析が複数個存在するため効率的ではないです。
ボトムアップ解析
トップダウンとは対照的に、下流側から積み上げて解析をします。
list5-3では、(n > 0のため)1から順にrecur(n)へ代入していきます。
再帰アルゴリズムの非再帰的表現
関数recurを非再帰的に実現する方法を考えます。
def recur(n: int) -> int:
"""末尾再帰を除去した関数recur"""
while n > 0:
recur(n - 1)
print(n)
n = n - 2
list5-3 のrecur(n - 2)をn = n - 2とすることで、末尾再帰は容易に除去できます。
再帰の除去
一方で、先頭側の再帰呼び出しの除去は容易ではありません。
recur(4)のとき、recur(3)の処理が完了するまで4を保存する必要があります。そのため、nの値をn - 1に更新して、関数の先頭に戻るというものの事前に現在のn値を一時的に保存しておくという処理が必要になります。さらに、保存していたnを取り出して、その値を表示する手順も必要になります。
そこで、スタックを使います。(以前作成したものを使います。)
from stack import Stack
def recur(n: int) -> int:
"""再帰を除去した関数recur"""
s = Stack(n)
while True:
if n > 0:
s.push(n) #nの値をプッシュ
n = n - 1
continue
if not s.is_empty(): #スタックが空でなければ
n = s.pop() #保存していた値をnにポップ
print(n)
n = n - 2
continue
break
5-3 ハノイの塔
ハノイの塔は、小さいものが上に、大きいものが下になるように重ねられた円盤を3本の柱のあいだで移動する問題です。
これを実現するプログラムがlist5-6になります。
# ハノイの塔
def move(no: int, x: int, y: int) -> None:
"""no枚の円盤をx軸からy軸へ移動"""
if no > 1:
move(no - 1, x, 6 - x - y) #再帰呼び出し
print(f'円盤[{no}]を{x}軸から{y}軸へ移動')
if no > 1:
move(no - 1, 6 - x - y, y) #再帰呼び出し
print('ハノイの塔')
n = int(input('円盤の枚数：'))
move(n, 1, 3) #第1軸に積まれたn枚を第3軸に移動
関数moveは、no枚の円盤の移動を次のように行います。
1.底の円盤を除いたグループ(円盤[1]～円盤[no - 1])を開始軸から中間軸へ移動
2.底の円盤noを開始軸から目的軸へ移動した旨を表示
3.底の円盤を除いたグループ(円盤[1]～円盤[no - 1])を中間軸から目的軸へ移動
| コラム5-3 ハノイの塔 |
|---|
ハノイの塔は、フィボナッチ数の研究者でもあった、フランスの数学者フランソワ・エドゥアール・アナトール・リュカが1883年に発売したゲームパズルの一種です。
本日は以上です。ありがとうございました。