ホーム / 旧ブログ /

Python(15)アッカーマン関数の再帰を除去する

公開日: 2014年06月19日 更新日: 2019年05月11日

旧ブログ

t f B! P L

前の関連記事：Python(14)アッカーマン関数のお勉強


前回お勉強したアッカーマン関数の再帰を除去します、、、自力ではどうしても解決できませんでした。

原始帰納的関数ではないから再帰の除去は難しい？


そうなのかどうかはわかりませんがとりあえず自分で頭をひねっても全然答えをだせませんでした。

とりあえずPythonで再帰で書いてみます。
1
2
3
4
5
6
7
8
def ack(x, y):
                if x == 0:
                                return y + 1
                elif y == 0:
                                return ack(x-1, 1)
                else:
                                return ack(x-1, ack(x, y-1))
print(ack(3,6))
漸化式で定義されているので再帰で書くのはとても簡単ですね。

これを実行すると509が返ってきます。

再帰の引数でしている計算を外に出します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ack(x, y):
                if x == 0:
                                y += 1
                                return y
                elif y == 0:
                                x -= 1
                                y += 1
                                return ack(x, y)
                else:
                                y -= 1
                                y = ack(x, y)
                                x -= 1
                                return ack(x, y)
print(ack(2, 2))
これは7が返ってきます。

6行目はy = 1と同じことなのですが計算していることをはっきりさせるため0に1を加算しています。

8行目、11行目、13行目にack(x, y)がでてきますがxの場合わけとyの場合わけを別にして重複部分をまとめます
1
2
3
4
5
6
7
8
9
10
11
12
13
def ack(x, y):
                if x == 0:
                                y += 1
                                return y
                else:
                                if y == 0:
                                                y += 1
                                else:
                                                y -= 1
                                                y = ack(x, y)
                                x -= 1
                                return ack(x, y)
print(ack(2, 2))
これでack(x, y)が2箇所になりました。

フィボナッチのときやハノイの塔のときと同じように二重再帰になっていますね。

このack(2, 2)の動きを図にしました。
ack(1, 1), ack(1, 2)が2回目にでてくるあとは省略しています。

またack(0, 4), ack(0, 5), ack(0, 6)もそれぞれy+1が返ってくるだけなので省略しています。

この図を睨めっこするとまずyが0まで減ってそうするとxが1減ることがわかります。

x > 0の間のyは0まで減っても1に復活します。

xが0になると再帰呼び出しが折り返しそのときのyに1を加えたものが戻り値で返ります。

yのループをxのループの中でy == 0のときのxの値をスタックに取得しながら回してx == 0でyの値を返して、スタックを取り出しながら2回目の再帰をまた実行すればよい、と思いました。

ところがどうがんばってもキリがないのですよ。

でもここまではPython(12)二重再帰の再帰を除去するのフィボナッチのときと同じ悩みです。

そこでフィボナッチのときと同じように確定した戻り値をリストに取得する方法をしようとしたのですけど、これもうまくいかないのです。

例えばack(0, 2)=3が求まったときx, yの値を1段階ずつもどってx+1, y-1としてack(1, 1)=3も決定できるのですが、同じく値が決まったはずのack(2, 0）のxは求まってもyを求める方法が思いつきません。

仕方なく1段階だけ戻ったところの戻り値を取得しておいて再利用しようとしたのですが、今度は汎用的に書く方法が思いつきませんでした。

Google検索でアッカーマン関数の非再帰の例を探す


ネットで検索してもなかなか答えが見つかりません、、、と書いて英語で検索し直すと答えが一発が出てきましたね。

java - How to rewrite Ackermann function in non-recursive style? - Stack Overflow
1
2
3
4
5
6
7
8
9
10
11
12
13
def ack(x, y):
                stack = list()
                stack.append(x)
                while stack:
                                x = stack.pop()
                                if x == 0 or y == 0:
                                                y += x + 1
                                else:
                                                stack.append(x-1)
                                                stack.append(x)
                                                y -= 1
                return y
print(ack(2, 2))
これでちゃんと答えが求まりました。あっさりと、、、

これが何をしているのかは巨大数：アッカーマン関数のC++実装 - clock-up-blogの解説がわかりやすいです。

再帰呼び出しの引数に着目して計算しています。

「アッカーマンの呪い」問題解説～進撃の巨人みたいに爆発的な大きな数字は案外簡単な式で実現できます #ackermann #python｜CodeIQ MAGAZINEで引数を入れて手で計算した結果が載っていましたので引用させていただきました。

ack(x, y)をA(x, y)と表現されてます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
A(2,2)
=A(1,A(2,1))
=A(1,A(1,A(2,0)))
=A(1,A(1,A(1,1)))
=A(1,A(1,A(0,A(1,0)))
=A(1,A(1,A(0,A(0,1))))
=A(1,A(1,A(0,2)))
=A(1,A(1,3))
=A(1,A(0,A(1,2)))
=A(1,A(0,A(0,A(1,1))))
=A(1,A(0,A(0,A(0,A(1,0)))))
=A(1,A(0,A(0,A(0,A(0,1)))))
=A(1,A(0,A(0,A(0,2))))
=A(1,A(0,A(0,3)))
=A(1,A(0,4))
=A(1,5)
=A(0,A(1,4))
=A(0,A(0,A(1,3)))
=A(0,A(0,A(0,A(1,2))))
=A(0,A(0,A(0,A(0,A(1,1)))))
=A(0,A(0,A(0,A(0,A(0,A(1,0))))))
=A(0,A(0,A(0,A(0,A(0,A(0,1))))))
=A(0,A(0,A(0,A(0,A(0,2)))))
=A(0,A(0,A(0,A(0,3))))
=A(0,A(0,A(0,4)))
=A(0,A(0,5))
=A(0,6)
=7
これから数字だけ抜き出してリストにします。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
[2, 2]
[1, 2, 1]
[1, 1, 2, 0]
[1, 1, 1, 1]
[1, 1, 0, 1, 0]
[1, 1, 0, 0, 1]
[1, 1, 0, 2]
[1, 1, 3]
[1, 0, 1, 2]
[1, 0, 0, 1, 1]
[1, 0, 0, 0, 1, 0]
[1, 0, 0, 0, 0, 1]
[1, 0, 0, 0, 2]
[1, 0, 0, 3]
[1, 0, 4]
[1, 5]
[0, 1, 4]
[0, 0, 1, 3]
[0, 0, 0, 1, 2]
[0, 0, 0, 0, 1, 1]
[0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 3]
[0, 0, 0, 4]
[0, 0, 5]
[0, 6]
7
各リストの最後の2つの要素をx, yとしてack(x, y)を適応していけば答えがでてしまいます。

先ほどのPythonの例では一番最後の要素をyに保持し、それより前のxの値はスタックに収納する替わりにリストの要素で保持しています。

この手法は他にも応用できそうですね。目からうろこです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def ack(x, y):
                lst = [x, y]
                while len(lst) > 1:
                                print(lst)
                                if lst[-2] == 0:
                                                lst[-1] = lst.pop() + 1
                                elif lst[-1] == 0:
                                                lst[-2] -= 1
                                                lst[-1] = 1
                                else:
                                                lst.append(lst[-1]-1)
                                                lst[-2] = lst[-3]
                                                lst[-3] -= 1
                return lst[0]
print(ack(2, 2))
yも含めてリストに入れた場合です。

4行目で各段階の引数のリストを出力しています。

計算結果を保存しておいて途中の計算を省略する


再帰は同じ計算が繰り返されるもののようです。

最初の図を見ながら同じ値になる結果を同じ色にしてみます。

下線があるところで結果が確定しています。

するとその上行にある同じ色の斜体になっているところの値も確定したことになります。

つまりA(0, y)の値が決定するとA(1, y-1)も必ず同じ値になります。

他にも上行に同じ値になるところがあるのですが、最初に書いたようにyの値を決定するする方法がわかりません。

とりあえずA(1, y-1)だけでも保存しておいて、次にでてきたとき(上図で青囲み線)に再利用すれば計算を少し省略できます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def ack(x, y):
                lst = [x, y]
                dic = dict()
                while len(lst) > 1:
                                print(lst)
                                if lst[-2] == 0:
                                                key = (1, lst[-1]-1)
                                                lst[-1] = lst.pop() + 1
                                                dic[key] = lst[-1]
                                elif lst[-1] == 0:
                                                lst[-2] -= 1
                                                lst[-1] = 1
                                else:
                                                key = (lst[-2], lst[-1])
                                                if key in dic:
                                                                lst.pop()
                                                                lst[-1] = dic[key]
                                                else:
                                                                lst.append(lst[-1]-1)
                                                                lst[-2] = lst[-3]
                                                                lst[-3] -= 1
                return lst[0]
print(ack(2, 2))
結果を引数の組み合わせのタプルをキーとする辞書dicに収納してあとで使っています。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
[2, 2]
[1, 2, 1]
[1, 1, 2, 0]
[1, 1, 1, 1]
[1, 1, 0, 1, 0]
[1, 1, 0, 0, 1]
[1, 1, 0, 2]
[1, 1, 3]
[1, 0, 1, 2]
[1, 0, 0, 1, 1]
[1, 0, 0, 3]
[1, 0, 4]
[1, 5]
[0, 1, 4]
[0, 0, 1, 3]
[0, 0, 5]
[0, 6]
7
28行だった出力結果が18行に減りましたね。

この省略ありのコードでack(3, 6)を実行してみるとPyCharmでエラーを吐かずに全部出力できました。

山が連なっているみたいで面白いです。

全部で2011行でした。

1244行目と1245行目にピークがありリストの要素数は255でした。

省略なしの場合はtoo much output to processと言われて全部出力はできませんでした。

リストの要素の書き換えをやめてpopとappendだけで見やすく書き直す


リストの要素を直接いじるとコードが汚くみえるのでxとyを取り出して操作するように書き換えてみました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def ack(x, y):
                lst = [x, y]
                while len(lst) > 1:
                                print(lst)
                                y = lst.pop()
                                x = lst.pop()
                                if x == 0:
                                                lst.append(y+1)
                                elif y == 0:
                                                lst.append(x-1)
                                                lst.append(1)
                                else:
                                                lst.append(x-1)
                                                lst.append(x)
                                                lst.append(y-1)
                return lst[0]
print(ack(2, 2))
省略版を書き直したものは以下です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ack(x, y):
                lst = [x, y]
                dic = dict()
                while len(lst) > 1:
                                print(lst)
                                y = lst.pop()
                                x = lst.pop()
                                if x == 0:
                                                lst.append(y+1)
                                                dic[(1, y-1)] = y + 1
                                elif y == 0:
                                                lst.append(x-1)
                                                lst.append(1)
                                else:
                                                if (x, y) in dic:
                                                                lst.append(dic[(x, y)])
                                                else:
                                                                lst.append(x-1)
                                                                lst.append(x)
                                                                lst.append(y-1)
                return lst[0]
print(ack(2, 2))

公式を使ってさらに計算時間を短縮する


x = 3までは公式がありますのでそれも取り入れてみます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def ack(x, y):
                lst = [x, y]
                dic = dict()
                while len(lst) > 1:
                                print(lst)
                                y = lst.pop()
                                x = lst.pop()
                                if x == 0:
                                                lst.append(y+1)
                                                dic[(1, y-1)] = y + 1
                                elif x == 1:
                                                lst.append(y+2)
                                elif x == 2:
                                                lst.append(2*y+3)
                                elif x == 3:
                                                lst.append(2**(y+3)-3)
                                elif y == 0:
                                                lst.append(x-1)
                                                lst.append(1)
                                else:
                                                if (x, y) in dic:
                                                                lst.append(dic[(x, y)])
                                                else:
                                                                lst.append(x-1)
                                                                lst.append(x)
                                                                lst.append(y-1)
                return lst[0]
print(ack(4, 2))
このack(4, 2)でもすぐに結果がでます。

最後の出力結果はすごい数字になっていますので転載は略します。
1
2
3
4
5
6
7
[4, 2]
[3, 4, 1]
[3, 3, 4, 0]
[3, 3, 3, 1]
[3, 3, 13]
[3, 65533]
略
これをみればわかるように最初の引数のxが3以上のときは3より小さなxが出現することはないのでack(4, 2)を求めるプログラムはx=3より小さいときのif文は省略できます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def ack(x, y):  # x > 2
                lst = [x, y]
                dic = dict()
                while len(lst) > 1:
                                print(lst)
                                y = lst.pop()
                                x = lst.pop()
                                if x == 3:
                                                lst.append(2**(y+3)-3)
                                elif y == 0:
                                                lst.append(x-1)
                                                lst.append(1)
                                else:
                                                if (x, y) in dic:
                                                                lst.append(dic[(x, y)])
                                                else:
                                                                lst.append(x-1)
                                                                lst.append(x)
                                                                lst.append(y-1)
                return lst[0]
print(ack(4, 2))

参考にしたサイト


java - How to rewrite Ackermann function in non-recursive style? - Stack Overflow
アッカーマン関数非再帰版。Javaの例。

巨大数：アッカーマン関数のC++実装 - clock-up-blog
アッカーマン関数を非再帰で求める方法の解説がわかりやすいです。

アッカーマン関数 (Ackermann function) Ack(4,2) の 19729 桁: nouse
A(4, 2)の戻り値が載っています。x=3までの公式も載っています。

「アッカーマンの呪い」問題解説～進撃の巨人みたいに爆発的な大きな数字は案外簡単な式で実現できます #ackermann #python｜CodeIQ MAGAZINE
手計算の結果を使わせて頂きました。

次の関連記事:Python(16)ハノイの塔の再帰を除去する

ブログ検索 by Blogger

Translate

全記事

«
Jun. 2014
»
Sun
Mon
Tue
Wed
Thu
Fri
Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Created by Calendar Gadget

QooQ