再帰を使えば、複雑な問題も単純な再帰的なコードで解くことができます。
この記事では、再帰を使って10進数から2進数、8進数、16進数にコードを作る方法について説明します。
再帰関数の基本については、次の記事を参照してください。
再帰とは
再帰は、ある問題を小さい問題に分割していき、その問題を解決する方法です。
通常、再帰は自分自身を呼び出します。再帰を使えば、非常に複雑なコードをシンプルに書くことができたりします。
リストの合計を計算する
次のコードは、リストの合計を計算するコードです。
def list_sum(list):
total = 0
for i in list:
total += i
return total
a = [1, 2, 3, 4, 5]
print(list_sum(a)) # => 15変数 total を使って、リスト内のすべての値を合計しています。
再帰的に考える
先ほどのコードでは、繰り返しを使って解きました。
これを再帰的に考えてみます。
次の式を見てください。
((((1+2)+3)+4)+5)
括弧を逆にしたものでも同じです。
(1+(2+(3+(4+5))))
２つの値を足して、その足した値にさらに値を足して行きます。
total = (1+(2+(3+(4+5))))
total = (1+(2+(3+9)))
total = (1+(2+12))
total = (1+14)
total = 15
これを Python のコードにするには、どうすればいいでしょうか？
リストで考えると、最初の要素と2番目以降の要素の合計の和になります。
Pythonだと最初の要素は list[0] で、2番目以降の要素は list[1:] になります。
これを式の形にすると次のようになります。
list_sum(list) = list[0] + list_sum(list[1:])
コードにしたのものが次です。
def list_sum(list):
if len(list) == 1:
return list[0]
return list[0] + list_sum(list[1:])
a = [1, 2, 3, 4, 5]
print(list_sum(a)) # => 152行目で、リストの要素の数が１であるかを確認しています。
このチェックは非常に重要で、これがない場合はエラーになってしまします。
このような再帰処理をせずに return するものをベースケースと言います。
5行目の list_sum(list[1:]) で再び自分自身を呼び出しています。
list の要素数は、自分自身を呼び出すたびに減っていきます。
このように、リストの値を合計するという問題を分割して、2つの値を足すという小さな問題に分割して、最終的に問題を解きます。
次のコードでも解くことができます。
引数をリストのインデックスに変更しています。
def list_sum(i):
if i == len(a) - 1:
return a[i]
return a[i] + list_sum(i + 1)
a = [1, 2, 3, 4, 5]
print(list_sum(0)) # => 15再帰の基本
再帰は基本的な次の３つから構成されます。
- ベースケースが必要
- 状態を変化させて、ベースケースに変化していく
- 自分自身を再帰的に呼び出す
ベースケースが再帰を停止させる条件になります。
先ほどのコードでは、リストの要素が１のときがベースケースになります。
def list_sum(list):
# ベースケース
if len(list) == 1:
return list[0]
return list[0] + list_sum(list[1:])
a = [1, 2, 3, 4, 5]
print(list_sum(a)) # => 15ベースケースに向かって変化していくために、再帰関数を呼び出すためにリストのサイズが１つずつ減っていきます。
そのリストのサイズが減った状態で、自分自身を呼び出します。
10進数の整数を2進数に変換する
10進数の整数を2進数に変換するプログラムを作成してみます。
10進数の数値を「0」になるまで 2 で割っていき、その余りを並べることで2進数に変換できます。
たとえば、10進数の 6 という整数は、2進数で表すと 110 になります。
6 ÷ 2 = 3 余り 0
3 ÷ 2 = 1 余り 1
1 ÷ 2 = 0 余り 1
これを順番に並べると2進数になります。
これをコードにしたのが次のものです。
def decimal_to_binary(n):
# ベースケース
if n < 2:
return str(n % 2)
return decimal_to_binary(n // 2) + str(n % 2)
print(decimal_to_binary(6)) # => 110次のコードによって、現在の n の値の余りを末尾につけて、次の n について再帰的に求めていきます。
decimal_to_binary(n // 2) + str(n % 2)10進数から8進数や16進数に変換する
先ほどは2進数のみへの変換でしたが、8進数や16進数に変換できるようにしてみましょう。
変換する基数（8進数なら8、16進数なら16）を引数として渡すことで、汎用的に変換できるようにします。
def decimal_to_base(n, base):
# ベースケース
if n < base:
return str(n % base)
return decimal_to_base(n // base, base) + str(n % base)
print(decimal_to_base(6, 2)) # => 110
print(decimal_to_base(6, 8)) # => 6
print(decimal_to_base(6, 16)) # => 6問題なさそうに思えますが、10進数の 10 を16進数に変換してみましょう。
10 を16進数に変換すれば A になりますが、次のコードでは 10 で表示されてしまします。
def decimal_to_base(n, base):
# ベースケース
if n < base:
return str(n % base)
return decimal_to_base(n // base, base) + str(n % base)
print(decimal_to_base(10, 16)) # => 10これを改善するために、次のような変数を導入します。
digit_chars = '0123456789ABCDEF'こうすれば問題なく16進数に変換することができます。
digit_chars = '0123456789ABCDEF'
print(digit_chars[5]) # => 5
print(digit_chars[10]) # => A
print(digit_chars[15]) # => Fこれを使って、先ほどのコードを改善します。
def decimal_to_base(n, base):
digit_chars = '0123456789ABCDEF'
# ベースケース
if n < base:
return digit_chars[n % base]
return decimal_to_base(n // base, base) + digit_chars[n % base]
print(decimal_to_base(10, 16)) # => A
print(decimal_to_base(15, 16)) # => F
print(decimal_to_base(255, 16)) # => FF
問題なく、変換できました。
まとめ
再帰関数の基本的な考え方は、次のようになります。
- 問題を小さな問題に分割する。
- 分割した問題を自分自身に渡す。
- １と２を再帰的に繰り返して、最終的な答えを求める。
再帰関数を実装するには、ベースケースという再帰を終了する条件が必要です。
- ベースケースが必要
- 状態を変化させて、ベースケースに変化していく
- 自分自身を再帰的に呼び出す
16進数の英字への変換には、専用の文字列を準備することで簡単に実装することができます。
def decimal_to_base(n, base):
digit_chars = '0123456789ABCDEF'
# ベースケース
if n < base:
return digit_chars[n % base]
return decimal_to_base(n // base, base) + digit_chars[n % base]
