まず,単純な例として,最大値の発見を再帰関数(再帰アルゴリズム)で表現してみる. ちなみにPythonには最大値を返す関数maxが用意されているので,実用的な意味は全く無い.
def max_recursive(X):
if len(X) == 1:
return X[0]
else:
return max(max_recursive(X[:-1]), X[-1])
上記の定義において,標準関数maxを使ってしまっているが,あまり深く考えないことにする.
次に10以上99以下の整数を10個ランダムに用意する.
import random
X = [random.randint(10, 99) for i in range(10)]
X
[30, 79, 38, 59, 48, 45, 94, 60, 20, 67]
この整数の集合を引数として,先程定義した再帰関数max_recursiveを実行してみる.
max_recursive(X)
94
確かに最大値が返された.
次に,再帰版ユークリッドの互除法を定義してみる. 「動作観察用」とある行は,動作の様子を見るためだけの命令であり,アルゴリズムの本質とは関係ない.
def euclid_recursive(x, y):
if y == 0:
print('euclid_recursive(%d, %d) returns %d' % (x, y, x)) # 動作観察用
return x
else:
print('euclid_recursive(%d, %d) calls euclid_recursive(%d, %d)' % (x, y, y, x % y)) # 動作観察用
return euclid_recursive(y, x % y)
関数を定義したので,具体的な引数を与えて試してみる.
euclid_recursive(10807, 10403)
euclid_recursive(10807, 10403) calls euclid_recursive(10403, 404) euclid_recursive(10403, 404) calls euclid_recursive(404, 303) euclid_recursive(404, 303) calls euclid_recursive(303, 101) euclid_recursive(303, 101) calls euclid_recursive(101, 0) euclid_recursive(101, 0) returns 101
101
最大公約数が見つかった. そして,再帰的に関数をよびだしている様子もわかった.
マージソートを実装するため,まず,ソート済みの2つの数値列を引数として受け取り,合わせてソート済みの数値列を返す関数mergeを定義する.
def merge(X, Y, chatty=False):
if len(X) == 0:
if chatty: print('%s, %s --> %s' % (str(X), str(Y), str(Y))) # 動作観察用
return Y
elif len(Y) == 0:
if chatty: print('%s, %s --> %s' % (str(X), str(Y), str(X))) # 動作観察用
return X
elif X[0] < Y[0]:
if chatty: print('%s, %s --> %s + merge(%s, %s)' % (str(X), str(Y), str(X[0:1]), str(X[1:]), str(Y))) # 動作観察用
Z = X[0:1] + merge(X[1:], Y, chatty)
if chatty: print('%s + merge(%s, %s) --> %s' % (str(X[0:1]), str(X[1:]), str(Y), str(Z))) # 動作観察用
return Z
else:
if chatty: print('%s, %s --> %s + merge(%s, %s)' % (str(X), str(Y), str(Y[0:1]), str(X), str(Y[1:]))) # 動作観察用
Z = Y[0:1] + merge(X, Y[1:], chatty)
if chatty: print('%s + merge(%s, %s) --> %s' % (str(Y[0:1]), str(X), str(Y[1:]), str(Z))) # 動作観察用
return Z
X = [random.randint(0, 9) for i in range(2)]
Y = [random.randint(0, 9) for i in range(2)]
X.sort()
Y.sort()
print(X, Y)
[2, 8] [3, 7]
動作観察用の表示ありで実行してみる.
merge(X, Y, True)
[2, 8], [3, 7] --> [2] + merge([8], [3, 7]) [8], [3, 7] --> [3] + merge([8], [7]) [8], [7] --> [7] + merge([8], []) [8], [] --> [8] [7] + merge([8], []) --> [7, 8] [3] + merge([8], [7]) --> [3, 7, 8] [2] + merge([8], [3, 7]) --> [2, 3, 7, 8]
[2, 3, 7, 8]
def merge_sort(X, chatty=False):
if len(X) == 1:
if chatty: print('%s --> %s' % (X, X)) # 動作観察用
return X
else:
half = len(X) // 2
print('%s --> merge_sort(%s), merge_sort(%s)' % (X, X[:half], X[half:])) # 動作観察用
merged1 = merge_sort(X[:half], True)
merged2 = merge_sort(X[half:], True)
Z = merge(merged1, merged2)
print('merge %s and %s --> %s' % (merged1, merged2, Z)) # 動作観察用
return Z
X = [random.randint(0,9) for i in range(4)]
X
[7, 3, 4, 6]
merge_sort(X)
[7, 3, 4, 6] --> merge_sort([7, 3]), merge_sort([4, 6]) [7, 3] --> merge_sort([7]), merge_sort([3]) [7] --> [7] [3] --> [3] merge [7] and [3] --> [3, 7] [4, 6] --> merge_sort([4]), merge_sort([6]) [4] --> [4] [6] --> [6] merge [4] and [6] --> [4, 6] merge [3, 7] and [4, 6] --> [3, 4, 6, 7]
[3, 4, 6, 7]