Python(12)二重再帰の再帰を除去する

前の関連記事：Python(11)再帰のお勉強:フィボナッチの数列

フィボナッチの数列の項を求める再帰のプログラムの再帰の除去をします。自分自身を2回呼び出しているので線形再帰のように簡単にはいきません。

非線形再帰をwhile文で書き換えるのは難しい

この二重再帰の除去はなかなかわかりませんでした。

とりあえず線形再帰のときと同様に上図の矢印の部分を追って繰り返し部分をwhile文にします。

# -*- coding: utf-8 -*-
def fib(n):  # n < 6
    stack_n = list()  # 1回目の再帰呼び出しの後も使うnの値をスタックに取得。
    while n > 1:
        n -= 1
        stack_n.append(n)
    else:
        p = 1  # 1回目の再帰呼び出しのf(1)の戻り値を取得。
    while stack_n:  # スタックに収納したnの値を取り出していく。
        n = stack_n.pop()
        n -= 1
        if not n > 1:
            q = 1  # 2回目の再帰呼び出しのf(0)とf(1)の戻り値を取得。
        else:
            stack_n2 = list()  # 2回目の再帰呼び出しのf(n)の引数がn>1のとき、1回目と同様にnの値をスタックに取得。
            while n > 1:
                n -= 1
                stack_n2.append(n)
            else:
                p2 = 1
            while stack_n2:
                n2 = stack_n2.pop()
                n2 -= 1
                if not n2 > 1:
                    q2 = 1
                else:
                    pass  # n>5のときはここに繰り返しのコードを追加しないといけない。
                p2 += q2
                q = p2
        p += q
    return p
print(fib(5))

これでf(0)からf(5)までは求まります。

f(6)以上のときは27行目のところでまたf(2)の値を求めないといけません。

ということで繰り返し部分は関数にしてしまいます。

def fib(n):
    stack_n = list()
    while n > 1:
        n -= 1
        stack_n.append(n)
    else:
        p = 1
    while stack_n:
        n = stack_n.pop()
        n -= 1
        if not n > 1:
            q = 1
        else:
            q = fib(n)
        p += q
    return p
print(fib(7))

整理したら再帰呼び出しになっていました、、、なにをしているんだか。

fib(n)が1回しかでてこないので、二重再帰を線形再帰に変換したことになったのか、と思ったのですが、while文の中に入っているので何回も呼び出されることになります。

二重線形のときよりも多く呼び出されるような気がします、、、

案の定f(40)を計算するとすご～く待たされます。

非線形再帰は線形再帰のように簡単にはwhile文には置き換えできないようです。

かなり時間を費やしたのでもう汎用的に再帰を除去する方法について考えるのは諦めます。

1回計算した結果をリストに取得して再利用する

一回計算したf(n)の戻り値をリストに取得しておいて再利用することにしました。

そうすればn > 1のときはそのリストの要素を使い回せばf(n)が取得できます。

以下先入れ後出しに使用しているリストはとくにスタックと呼んでいます。

またf(n)は上図のように二重再帰呼び出しのときに呼び出されるもののことです。

CODE_AとかCONDITION_Aと書いてあるのはPython(8)線形再帰を非再帰に変換する方法でみた線形再帰を除去する型に相当する部分を表しています。

# -*- coding: utf-8 -*-
def fib(n):
    stack_n = list()  # 最初の折り返しまでのnを収納するスタック。
    list_m = list()  # fib(n)の値を収納するリスト。nは要素番号に一致。
    while n > 1:  # CONDITION_A
        n -= 1  # CODE_B
        stack_n.append(n)  # 行きのnの値を取得。
    else:  # n = 1のとき
        p = 1  # fib(1)の戻り値1をpに取得。CODE_D
        list_m.append(p)  # fib(0)の値をスタックに取得。(上図の通りだとf(1))  再帰の結果をリストに保存しておく。
        list_m.append(1)  # fib(1)の値をスタックに取得。(上図の通りだとf(0))
    while stack_n:  # 1,2,3,,,がstack_n.pop()で得られる。
        n = stack_n.pop()  # 1回目の再帰の帰りのnを取り出す。
        n -= 1  # 2回目の再帰のCODE_B
        q = list_m[n]
        p += q  # fib(n+2)の値を取得。
        list_m.append(p)  # fib(n+2)の値をスタックに取得。
    return list_m[-1]
print(fib(40))

まずは一回目の再帰呼び出しをみてみます。

f(1)のreturn 1までが一回目の再帰の往路になります。

nの値は二回目の再帰の呼び出しのときに使っているので一回目の再帰の往路にスタックstack_nに収納しておきます。

一回目の再帰の戻り値pもあとで使うのでこれもスタックに収納したいのですが、一回目の再帰の往路の時点ではまだ値が確定していないので収納できません。

ということで一回目の再帰の往路はnの値だけスタックに収納します。

それで一回目の再帰の復路にpの値を取得したいところですが、一回目の再帰の復路でもまだpの値が確定していないので収納できません。

そこでwhile n > 1: 〜 else: 〜文でn > 1がFalseのときの処理をしてしまいます。

つまりf(2)の呼び出しの中の再帰呼び出しはすべてn > 1がFalseなので10行目と11行目でf(0)とf(1)の戻り値をリストlst_mに取得しています。

f(2)以降の戻り値はこのlst_mからqを取得してpに加えて得ます。

ということでn > 1 のときはf(n)が呼び出されたときpにはf(n-1)が入っており、lst_m[n-2]からf(n-2)の戻り値qを得てそれにpを加えてf(n)の戻り値にしています。

lst_mにはフィボナッチの数列が入ることになります。

再帰のときと違って同じ計算を繰り返さないのでf(40)でもすぐに結果がでます。

    return list_m

18行目をこのように書き換えるとフィボナッチの数列のリストが返ってきます。

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141]
これはf(40)の結果です。

途中の結果をキューに取得する

nの値は再帰の復路で使うために先入れ後出しのスタックに収納しましたが、lst_mの要素は一回しか使わないのでリストに全値を持っておく必要はありません。

f(n-2)の値を取得したあとそれを使うまでにf(n-1)を取得して、そのあとに先に取得していたf(n-2)の値を使用することになります。

これは先入れ先出しになるのでqの値をキューに取得します。

先日購入したPython Cookbook第3版の1.3. Keeping the Last N Itemsで紹介されていたclass collections.deque([iterable[, maxlen]])を使います。
これでも動くのですけど、よくみてみると6行目のwhile文で取得しているnのスタックは13行目のwhile文では単にカウンタとして使っているだけなのでもう不要ですね。

from collections import deque
def fib(n):
    d = deque(maxlen=2)
    p = 1
    d.append(1)
    d.append(p)
    while n > 1:
        n -= 1
        q = d.popleft()
        p += q
        d.append(p)
    return d.pop()  
print(fib(40))

stack_nを省きました。

さらにキューを生成するときは2個の要素とも1なので1行にまとめてしまいます。

from collections import deque
def fib(n):
    d = deque([1, 1], maxlen=2)
    p = 1
    while n > 1:
        n -= 1
        q = d.popleft()
        p += q
        d.append(p)
    return d.pop()
print(fib(40))

リストの内包表記でフィボナッチの数列のリストを表現する

もうキューなんかも使わずコードの意味を考えてリストで書き直すともっと簡単になります。

def fib(n):
    lst = [1, 1]
    for i in range(1, n-1):
        lst = lst[1], sum(lst)
    return sum(lst)
print(fib(40))

for文だけで表現できるといえばリストの内包表記です。

LibreOffice(50)オブジェクトから継承図をたどってメソッド一覧を得るで多重ループの内包表記は一番内側の中身を先頭にもってくるだけ、と学習したのでまずはfor文でループを作ります。

リストの内包表記の中ではif文は使えますが、代入文が使えません。

またfor文の中に書けるのは1文だけです。

この制約のなかでfor文が書ければリストの内包表記にできます。

代入文が使えないという制約のために初期値の[1, 1]をどう代入するかでいきなりつまずきました。

「フィボナッチの数列、内包表記」で検索するとPythonのリスト内包表記で色々な数列を作ってみた - アジャイルSEを目指すブログがみつかりました。

フィボナッチの数列をリストの内包表記で表現する方法も載っています。

内包表記はいきなりみてもよくわからないのでfor文に分解してみます。

リストに出力する部分はprint()で出力します。

n = 5
for i in [[1, 1]]:
    for j in range(n+1):
        print([i[-2], i.append(i[-2]+i[-1])][0])

1, 1, 2, 3, 5, 8が得られます。

2行目でfor文を使ってリストをiに代入しています。

代入したいのはリストなのでそのリストをリストにいれてイテレータにしてinで取り出していますね。

初期値を代入したiには前2項を加算した新たな要素を追加しないといけません。

ここでも代入文が使えないので4行目でappend()を使ってiに新たに前2項の和の要素を追加しています。

append()の戻り値はNoneなのですけどそれをリストの要素にしてしまっています。

ですので[i[-2], i.append(i[-2]+i[-1])]のリストの要素番号2の要素に新たな要素が追加されるのではなくこのリストは単にi[-2]とi.append()を同時に実行させるためのものです。

つまり1文しか実行できないところをリストにまとめて1文にして実行しています。

あとはそれをn+1回繰り返してn = 0 のときからn = 5 のときまでの値を出力しています。

うーん、とても巧みな技ですね。

これをリストの内包表記にするには最後のfor文の中身を先頭にもってきて[]で囲むだけです。

n = 5
print([[i[-2], i.append(i[-2]+i[-1])][0] for i in [[1, 1]] for j in range(n+1)])

これで[1, 1, 2, 3, 5, 8]が出力されます。

このときリストiにもフィボナッチの数列が生成されています。

iを2項のキューとして使ってみます。

n = 5
for i in [[1, 1]]:
    for j in range(n+1):
        print([i.append(sum(i)), i.pop(0)][1])

これで同じ結果が得られます。

4行目でiの全要素の和をiの最終要素に追加し、次のi.pop(0)で先頭の要素を取り出しています。

iは先入れ先出しのキューになっています。

i.pop(0)はdequeのpopleft()と同じことをしているのですが、それより効率が悪いそうです。

n = 5
print([[i.append(sum(i)), i.pop(0)][1] for i in [[1, 1]] for j in range(n+1)])

for文の中身を先頭にもってきてつなげるとリストの内包表記になります。

これでリストの内包表記の使い方の幅が広がりそうですね。

参考にしたサイト

class collections.deque([iterable[, maxlen]])
リストと違ってデックはappendleft()とpopleft()で左側からappendとpopができます。

Pythonのリスト内包表記で色々な数列を作ってみた - アジャイルSEを目指すブログ
フィボナッチの数列をリストの内包表記で表現する方法も載っています。

次の関連記事:Python(13)ハノイの塔