▲再帰¶

再帰について説明します。

関数の再帰呼び出しとは、定義しようとしている関数を、その定義の中で呼び出すことです。定義の中で直接呼び出す場合に限らず、他の関数を経由して間接的に呼び出す場合も、再帰呼び出しに含まれます。再帰呼び出しを行う関数を、再帰関数といいます。

再帰関数は、分割統治アルゴリズムの記述に適しています。分割統治とは、問題を容易に解ける小さな粒度まで分割していき、個々の小さな問題を解いて、その部分解を合成することで問題全体を解くような方法を指します。分割統治の考え方は、関数型プログラミングにおいてもよく用いられます。再帰関数による分割統治の典型的な形は、次の通りです。

def recursive_function(...):
    if 問題粒度の判定:
        再帰呼び出しを含まない基本処理
    else:
        再帰呼び出しを含む処理（問題の分割や部分解の合成を行う）

以下で、再帰関数を使った処理の例をいくつか見ていきましょう。

再帰関数の例：接頭辞リストと接尾辞リスト¶

[1]:

# 入力の文字列の接頭辞リストを返す関数prefixes
def prefixes(s):
    if s == '':
        return []
    else:
        return [s] + prefixes(s[:-1])

prefixes('aabcc')

[1]:

['aabcc', 'aabc', 'aab', 'aa', 'a']

[2]:

# 入力の文字列の接尾辞リストを返す関数suffixes
def suffixes(s):
    if s == '':
        return []
    else:
        return [s] + suffixes(s[1:])

suffixes('aabcc')

[2]:

['aabcc', 'abcc', 'bcc', 'cc', 'c']

再帰関数の例：べき乗の計算¶

[3]:

# 入力の底baseと冪指数exptからべき乗を計算する関数power
def power(base, expt):
    if expt == 0:
        # exptが0ならば1を返す
        return 1
    else:
        # exptを1つずつ減らしながらpowerに渡し、再帰的にべき乗を計算
        # (2*(2*(2*....*1)))
        return base * power(base, expt - 1)

power(2,10)

[3]:

一般に、再帰処理は、繰り返し処理としても書くことができます。

[4]:

# べき乗の計算を繰り返し処理で行った例
def power(base, expt):
    e = 1
    for i in range(expt):
        e *= base
    return e

power(2,10)

[4]:

単純な処理においては、繰り返しの方が効率的に計算できることが多いですが、特に複雑な処理になってくると、再帰的に定義した方が読みやすいコードで効率的なアルゴリズムを記述できることもあります。たとえば、次に示すべき乗計算は、上記よりも高速なアルゴリズムですが、計算の見通しは明快です。

[5]:

# べき乗を計算する高速なアルゴリズム
def power(base, expt):
    if expt == 0:
        return 1
    elif expt % 2 == 0:
        return power(base * base, expt // 2) # x**(2m) == (x*x)**m
    else:
        return base * power(base, expt - 1)

power(2,10)

[5]:

再帰関数の例：マージソート¶

マージソートは、典型的な分割統治アルゴリズムで、以下のように再帰関数で実装することができます。

[6]:

# マージソートを行い、比較回数 n を返す
def merge_sort_rec(data, l, r, work):
    n = 0
    if r - l <= 1:
        return n
    m = l + (r - l) // 2
    n1 = merge_sort_rec(data, l, m, work)
    n2 = merge_sort_rec(data, m, r, work)
    i1 = l
    i2 = m
    for i in range(l, r):
        from1 = False
        if i2 >= r:
            from1 = True
        elif i1 < m:
            n = n + 1
            if data[i1] <= data[i2]:
                from1 = True
        if from1:
            work[i] = data[i1]
            i1 = i1 + 1
        else:
            work[i] = data[i2]
            i2 = i2 + 1
    for i in range(l, r):
        data[i] = work[i]
    return n1 + n2 + n

def merge_sort(data):
    return merge_sort_rec(data, 0, len(data), [0]*len(data))

merge_sort は、与えられた配列をインプレースでソートするとともに、比較の回数を返します。 merge_sort は、再帰関数 merge_sort_rec を呼び出します。

merge_sort_rec(data, l, r, work) は、配列 data のインデックスが l 以上で r より小さいところをソートします。

要素が1つかないときは何もしません。
そうでなければ、l から　r までの要素を半分にしてそれぞれを再帰的にソートします。
その結果を作業用の配列 work に順序を保ちながらコピーします。この操作はマージ（併合）と呼ばれます。
最後に、work から data に要素を戻します。

merge_sort_rec は自分自身を2回呼び出していますので、繰り返しでは容易には実装できません。

[7]:

import random
a = [random.randint(1,10000) for i in range(100)]
merge_sort(a)

[7]:

[8]:

[8]:

[ ]:

▲再帰¶

再帰関数の例：接頭辞リストと接尾辞リスト¶

再帰関数の例：べき乗の計算¶

再帰関数の例：マージソート¶

Pythonプログラミング入門

Navigation

Related Topics