Processing math: 0%
ホーム / 旧ブログ /

Python(17)再帰関数の例を非再帰にする:まとめ編

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

旧ブログ

t f B! P L

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


再帰関数を再帰を使わずwhile文で書く方法は習得できました。1回の再帰で使用する変数をすべて同じスタックに入れてしまえばよいようです。いままでやった例をすべてこの方法で再帰を除去します。

ユークリッドの互除法


Python(9)再帰のお勉強:ユークリッドの互除法でやったものです。

漸化式
gcd(x,y)={x(y=0)gcd(y,xmod 再帰関数
1
2
3
4
5
6
def gcd(x, y):
                if y == 0:
                                return x
                else:
                                return gcd(y, x % y)
print(gcd(24, 9))
while文
1
2
3
4
5
6
7
8
def gcd(x, y):
                stack = [x, y]
                while stack[-1] > 0:
                                x, y = stack[-2:]
                                del stack[-2:]
                                stack.extend([y, x % y])
                return stack[-2]
print(gcd(24, 9))
ループの次に行く間にスタックから2個取り出して2個追加しているのでスタックに貯めておくものはなく、スタックは除去できます。
1
2
3
4
5
def gcd(x, y):
                while y > 0:
                                x, y = y, x % y
                return x
print(gcd(24, 9))

自然数の階乗


Python(10)再帰のお勉強:自然数の階乗でやったものです。

漸化式 {\rm factorial}(n) = \begin{cases}  1& (n=1) \\  n\times{\rm factorial}(n-1)& (n>1) \end{cases} 再帰関数
1
2
3
4
5
6
def factorial(n):
                if n == 1:
                                return 1
                else:
                                return n * factorial(n-1)
print(factorial(4))
while文
1
2
3
4
5
6
7
8
def factorial(n):
                stack = [n, n]
                while stack[-2] > 1:
                                n, r = stack[-2:]
                                del stack[-2:]
                                stack.extend([n - 1, r * (n - 1)])
                return stack[-1]
print(factorial(4))
これもループの次に行く間に2個追加して2個削除しているのでスタックを除去できます。
1
2
3
4
5
6
def factorial(n):
                r = n
                while n > 1:
                                n, r = n - 1, r * (n - 1)
                return r
print(factorial(4))

フィボナッチの数列


Python(11)再帰のお勉強:フィボナッチの数列でやったものです。

漸化式  {F}_{n}=\begin{cases} 1 &(n = 0 \text{ or } n = 1)     \\ {F}_{n-1}+{F}_{n-2}&(n > 1)   \end{cases} 再帰関数
1
2
3
4
5
6
def fib(n):
                if n > 1:
                                return fib(n-1) + fib(n-2)
                else:
                                return 1
print(fib(4))
while文
1
2
3
4
5
6
7
8
def fib(n):
                stack = [n, 1, 1]
                while stack[-3] > 1:
                                n, x, y = stack[-3:]
                                del stack[-3:]
                                stack.extend([n - 1, y, x + y])
                return stack[-1]
print(fib(4))
これもいままでと同じく次のループに持ち越すスタックの内容がないのでスタックが除去できます。

4行目のスタックから取り出したものと6行目のスタックに入れるものを=でつなげばいいだけですね。
1
2
3
4
5
6
def fib(n):
                x, y = 1, 1
                while n > 1:
                                n, x, y = n - 1, y, x + y
                return y
print(fib(4))
複数同時の代入 (multiple assignment)(3.2. プログラミングへの第一歩)の作り方がよくわからなかったのですが、このやり方だと機械的に代入式が作れますね。

ハノイの塔


Python(16)ハノイの塔の再帰を除去するでやったものです。

漸化式 {\rm hanoi}(n, x, y, z)=\begin{cases} x\rightarrow z&(n = 1)     \\ \begin{pmatrix} {\rm hanoi}(n-1, x, z, y)\\ {\rm hanoi}(1, x, y, z)\quad\quad\\ {\rm hanoi}(n-1, y, x, z)\end{pmatrix}&(n > 1)   \end{cases} 再帰関数
1
2
3
4
5
6
7
8
9
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
                if n == 1:
                                print("{}→{}".format(x, z))
                else:
                                hanoi(n-1, x, z, y)
                                hanoi(1, x, y, z)
                                hanoi(n-1, y, x, z)
hanoi(3, "A", "B", "C")
4行目の"→"でUTF-8の文字列を使っているので1行目のエンコードの指定をしています。

このエンコードの指定は実行には必要ありませんが、これがないとPyCharm3.4でブレークポイントを設定してデバッグするときにエラーになります。

while文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding: utf-8 -*-
def hanoi(n, x, y, z):
                stack = [n, x, y, z]
                while stack:
                                n, x, y, z = stack[-4:]
                                if n > 2:
                                                stack.extend([n-1, x, z, y])
                                elif n == 2:
                                                print("{}→{}".format(x, y))
                                                print("{}→{}".format(x, z))
                                                print("{}→{}".format(y, z))
                                                del stack[-4:]
                                                if stack:
                                                                x, y, z = stack[-3:]
                                                                stack.extend([1, x, y, z ])
                                elif n == 1:
                                                print("{}→{}".format(x, z))
                                                if len(stack) > 4:
                                                                n = stack[-8]
                                                                del stack[-8:]
                                                                stack.extend([n-1, y, x, z])
                                                else:
                                                                del stack[-4:]
hanoi(4, "A", "B", "C")
これのスタックは除去できません。

アッカーマン関数


Python(15)アッカーマン関数の再帰を除去するでやったものです。

漸化式 ack(x, y)=\begin{cases} y+1& (x=0) \\ ack(x-1, 1)& (x>0かつy=0) \\ ack(x-1, ack(x, y-1))&(x>0かつy>0) \end{cases} 再帰関数
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))
while文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ack(x, y):
                stack = [x, y]
                while len(stack) > 1:
                                # print(stack)
                                x, y = stack[-2:]
                                del stack[-2:]
                                if x == 0:
                                                stack.append(y+1)
                                elif y == 0:
                                                stack.extend([x-1, 1])
                                else:
                                                stack.extend([x-1, x, y-1])
                return stack[0]
print(ack(3, 6))
4行目のコメントアウトをはずすとstackの変化がみれますが、ack(2, 2)ぐらいにとどめておかないと結果があふれて表示されません。

参考にしたサイト


3.2. プログラミングへの第一歩
Pythonの複数同時の代入 (multiple assignment)の解説があります。

次の関連記事:Python(18)リストから二分木を生成する

ブログ検索 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