#はじめに
この記事は、競技プログラミングの解説を多数書かれているけんちょんさんの書籍、**問題解決力を鍛える！ アルゴリズムとデータ構造（けんちょんさん本）**について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。
このページでは、第４章掲載分について紹介します！
バグ等ありましたらご容赦ください。
他の章へのリンクは以下のページをご覧ください。
【目次ページ】
https://qiita.com/KevinST/items/002676619a583754bf76
#code4.1 1からNまでの総和を計算する再帰関数
基本的な再帰です。
def func(N):
if N == 0:
return 0
return N + func(n-1)
関数部分だけ作ってあるので、入出力はありません。
#code4.2 1からNまでの総和を計算する再帰関数
code4.1の使用例です（N=5）
#pythonは再帰が制限されている（1000回等、環境によって異なる）
#これを十分大きい値（今回は10の9乗）に変更
import sys
sys.setrecursionlimit(10**9)
def func(N):
#再帰関数を呼び出したことを報告する
print("func({})を呼び出しました".format(N))
#ベースケース
if N == 0:
return 0
#ベースケースでない場合、再帰的に答えを求める
result = N + func(N-1)
print("{}までの和 = {}".format(N, result))
return result
func(5)
【出力例】
func(5)を呼び出しました
func(4)を呼び出しました
func(3)を呼び出しました
func(2)を呼び出しました
func(1)を呼び出しました
func(0)を呼び出しました
1までの和 = 1
2までの和 = 3
3までの和 = 6
4までの和 = 10
5までの和 = 15
お作法として、再帰上限の回数を増やしています。
Pythonでは再帰上限がデフォルトだと1000回程度にセットされていることが多いので、
競プロ等で再帰を使用する際は変更されるとよいと思います。
（今回のケースでは必要ないが、念のため）
※以降は必要ない場合省略します。
#code4.3 再帰呼び出しが止まらない再帰関数
#危険！ 実行は自己責任でお願いします
def func(N):
if N == 0:
return 0
return N + func(N+1)
TLE間違いなし。
#code4.4 ユークリッドの互除法によって最大公約数を求める
おなじみのユークリッドの互除法です。
Q: 51と15の最大公約数は？
- 51÷15 = 3 あまり6
- 15÷6 = 2あまり3
- 6÷3 = 2あまり0
A: ３！！
というやつですね。
再帰関数で書いてみましょう。
def GCD(m, n):
#ベースケース
if n == 0:
return m
#再帰呼び出し
return GCD(n, m % n)
print(GCD(51, 15)) #3が出力される
print(GCD(15, 51)) #3が出力される
【出力例】
3
3
ちなみに計算量は$O(log(n))$です。
GCDは高速！！！！
#code4.5 フィボナッチ数列を求める再帰関数
こちらもおなじみのやつです。
1 1 2 3 5 8 13 21 34 ...
def fibo(N):
#ベースケース
if N == 0:
return 0
elif N == 1:
return 1
#再帰呼び出し
return fibo(N-1) + fibo(N-2)
print(fibo(5))
【出力例】
5
原本にはありませんが、動作確認のため出力もつけておきました。
詳細な動作は、次のcode4.6で確認しましょう。
#code4.6 部分和問題に対するビットを用いる全探索手法
code4.5の具体的な使用例です。
内部の状態を確認できるように、出力が付いています。
def fibo(N):
#再帰関数を呼び出したことを報告する
print("fibo({})を呼び出しました".format(N))
#ベースケース
if N == 0:
return 0
elif N == 1:
return 1
#再帰的に答えを求めて出力する
result = fibo(N-1) + fibo(N-2)
print("{}項目 = {}".format(N, result))
return result
fibo(6)
【出力例】
fibo(6)を呼び出しました
fibo(5)を呼び出しました
fibo(4)を呼び出しました
fibo(3)を呼び出しました
fibo(2)を呼び出しました
fibo(1)を呼び出しました
fibo(0)を呼び出しました
2項目 = 1
fibo(1)を呼び出しました
3項目 = 2
fibo(2)を呼び出しました
fibo(1)を呼び出しました
fibo(0)を呼び出しました
2項目 = 1
4項目 = 3
fibo(3)を呼び出しました
fibo(2)を呼び出しました
fibo(1)を呼び出しました
fibo(0)を呼び出しました
2項目 = 1
fibo(1)を呼び出しました
3項目 = 2
5項目 = 5
fibo(4)を呼び出しました
fibo(3)を呼び出しました
fibo(2)を呼び出しました
fibo(1)を呼び出しました
fibo(0)を呼び出しました
2項目 = 1
fibo(1)を呼び出しました
3項目 = 2
fibo(2)を呼び出しました
fibo(1)を呼び出しました
fibo(0)を呼び出しました
2項目 = 1
4項目 = 3
6項目 = 8
N=6と比較的小さい数にも関わらず、多数の関数呼び出しがかかっていますね。
次の次のコード（code4.8）では、この改善を試みます。
#code4.7 フィボナッチ数列をfor文による反復で求める
一度再帰を離れ、for文と配列で実装するとどうなるか、という試みです。
F = [None] * 50
F[0], F[1] = 0, 1
for N in range(2, 50):
F[N] = F[N-1] + F[N-2]
print("{}項目 : {}".format(N, F[N]))
【出力例】
2項目 : 1
3項目 : 2
4項目 : 3
5項目 : 5
6項目 : 8
7項目 : 13
8項目 : 21
9項目 : 34
10項目 : 55
11項目 : 89
12項目 : 144
13項目 : 233
14項目 : 377
15項目 : 610
16項目 : 987
17項目 : 1597
18項目 : 2584
19項目 : 4181
20項目 : 6765
21項目 : 10946
22項目 : 17711
23項目 : 28657
24項目 : 46368
25項目 : 75025
26項目 : 121393
27項目 : 196418
28項目 : 317811
29項目 : 514229
30項目 : 832040
31項目 : 1346269
32項目 : 2178309
33項目 : 3524578
34項目 : 5702887
35項目 : 9227465
36項目 : 14930352
37項目 : 24157817
38項目 : 39088169
39項目 : 63245986
40項目 : 102334155
41項目 : 165580141
42項目 : 267914296
43項目 : 433494437
44項目 : 701408733
45項目 : 1134903170
46項目 : 1836311903
47項目 : 2971215073
48項目 : 4807526976
49項目 : 7778742049
計算量$O(N)$で実装できています。
#code4.8 フィボナッチ数列を求める再帰関数をメモ化
配列をうまく使えば、同じ計算を省略して、プログラムを高速化できます。
これを再帰にも取り入れてみましょう（＝メモ化）。
#fibo[N]の結果をメモする配列
memo = [-1] * 50
def fibo(N):
#ベースケース
if N == 0:
return 0
elif N == 1:
return 1
#メモをチェック
if memo[N] != -1:
return memo[N]
#答えをメモ化しながら、再帰呼び出し
memo[N] = fibo(N-1) + fibo(N-2)
return memo[N]
fibo(49)
for N in range(2, 50):
print("{}項目 : {}".format(N, memo[N]))
【出力例】
2項目 : 1
3項目 : 2
4項目 : 3
5項目 : 5
6項目 : 8
7項目 : 13
8項目 : 21
9項目 : 34
10項目 : 55
11項目 : 89
12項目 : 144
13項目 : 233
14項目 : 377
15項目 : 610
16項目 : 987
17項目 : 1597
18項目 : 2584
19項目 : 4181
20項目 : 6765
21項目 : 10946
22項目 : 17711
23項目 : 28657
24項目 : 46368
25項目 : 75025
26項目 : 121393
27項目 : 196418
28項目 : 317811
29項目 : 514229
30項目 : 832040
31項目 : 1346269
32項目 : 2178309
33項目 : 3524578
34項目 : 5702887
35項目 : 9227465
36項目 : 14930352
37項目 : 24157817
38項目 : 39088169
39項目 : 63245986
40項目 : 102334155
41項目 : 165580141
42項目 : 267914296
43項目 : 433494437
44項目 : 701408733
45項目 : 1134903170
46項目 : 1836311903
47項目 : 2971215073
48項目 : 4807526976
49項目 : 7778742049
こちらも計算量$O(N)$で実装できました。
#code4.9 部分和問題を再帰関数を用いる全探索で解く
前章code3.6と同じ問題を、再帰関数を使って解きます。
一度メモ化は忘れ、シンプルな再帰で実装します。
def func(i, w, a):
#ベースケース
if i == 0:
if w == 0:
return True
else:
return False
#a[i-1]を選ばない場合
if func(i-1, w, a):
return True
#a[i-1]を選ぶ場合
if func(i-1, w-a[i-1], a):
return True
#どちらもFalseの場合
return False
N, W = map(int, input().split())
a = list(map(int, input().split()))
if func(N, W, a):
print("Yes")
else:
print("No")
【入力例】
4 10
1 9 100 200
【出力例】
Yes
このコードは計算量$O(2^N)$です。
（詳細はけんちょんさん本をご覧ください）
興味がある方は、これもメモ化してみましょう！（章末問題4.6）
第５章はこちら
（完成次第追加）