前の関連記事：Python(7)二分木(Binary Tree)の勉強資料を求めて本屋へ
先日購入した教養のコンピュータアルゴリズムを教科書として第4章に載っているJavaScriptの例をPythonでこねくり回しているうちにwhile文で書いたことが再帰関数で書けるのではないかと思いました。
再帰関数を非再帰に書き換える方法の解説を発見
やりたいこととは逆なのですが、「再帰関数 while文」で検索していると、再帰関数を非再帰に書き換えるという解説を発見しました。
Cの例ですけど。
ex13-2.dvi - ex13-2.pdf
これは名古屋大学の２００４年度・計算機数学１・第１３回実習（その２）の授業の資料のようです。
URLをみると名大の授業 (NU OCW)にたどり着きますが講義のビデオは発見できませんでした。
講義資料 | 数理解析・計算機数学 I | 多元数理科学研究科 | 名大の授業 (NU OCW)
この講座ですかね。
最終更新日：2006年12月18日になっていますが、すでに内容が変わっているようです。
そういう方法があるとわかったので「非再帰 変換」で検索してみると再帰を非再帰にする例がみつかりました。
各種典型再帰関数を非再帰に変換する - 競技プログラミング+αなブログ
ハノイの塔の非再帰の例もあります。Cの例。
メソッド (3)
再帰関数の働き方を図にして表現してあります。Javaの例。
非再帰で解くハノイの塔(Ｃ言語版): たった1.2人の独立戦争記
これもハノイの塔の非再帰で書く例。Cの例。
なんにもない (です): 【非再帰】ハノイの塔を解くプログラム
ハノイの塔のPythonの例。
Pythonクックブック - Google ブックス
入れ子になったシークエンスの平滑化のPythonの例。
このPythonクックブックによると非再帰版は再帰限度に縛られないのでより深い入れ子を平滑化できるそうです。
でも期待に反して非再帰版は再帰版より10%遅いそうです。
再帰を使うとその言語の再帰の限界に制約されるので、非再帰の方が汎用性が高いようです。
非再帰の方が速度が遅い理由はよくわかりません。
それはこのシークエンスの平滑化に限った話かもしれません。
ex13-2.dvi - ex13-2.pdfには再帰にした方が一般的に遅くなると書いてあります。
線形再帰の除去方法
とりあえずex13-2.dvi - ex13-2.pdfに載っているCの例をPythonで考えてみます。
def foo(n):
CODE_A
if CONDITION_A:
CODE_B
foo(n)
CODE_C
CODE_D
この関数foo()を呼び出すとまずCODE_Aが実行され、CONDITION_AがTrueの間はCODE_Bが実行されたあと、スタックにその状態が保持されたままfoo()が呼ばれ続けます。CONDITION_AがFalseになるとCODE_AのあとにCODE_Dが実行され、今度はスタックされていたところからCODE_Cが実行され続けます。
スタックの最後までCODE_Cが実行され終わるとCODE_Dが実行されて関数foo()が終了します。
このように自分自身を1回しか呼び出さない再帰をとくに「線形再帰」といいます。
コードが呼ばれる順番を図にするとよくわかりますね。
CONDITION_AがFalseになるとCODE_Aが呼ばれたあとにCODE_Dが呼ばれます。
するといままで途中で止められていたCODE_Cが次々呼ばれてもとのfoo(n)まで返ってきます。
この関数を途中で止めておく数には限界があってPythonクックブックには数千以内と書いてあります。
while文にするときはこの関数を途中で止めた状態を後入れ先出しできるリストに保存しておくことになります。
def foo(n):
CODE A
stack = list() # 次の処理をする間、途中の状態を保存するリスト。
while CONDITION A: # CONDITION_AがTrueの間実行。
CODE_B
stack.append() # この状態の何かをスタックに積む。
CODE_A
CODE_D # CONDITION_AがFalseになったら実行。
while stack: # スタックが空になるまで実行。
stack.pop() # スタックを後に入れた順から取り出す。
CODE_C
CODE_D
これで上の再帰関数と同じになると思うのですけどex13-2.dvi - ex13-2.pdfだとCODE_Dの前にif CONDITION A:が入っています。def foo(n):
CODE A
stack = list() # 次の処理をする間、途中の状態を保存するリスト。
while CONDITION A: # CONDITION_AがTrueの間実行。
CODE_B
stack.append() # この状態の何かをスタックに積む。
CODE_A
CODE_D # CONDITION_AがFalseになったら実行。
while stack: # スタックが空になるまで実行。
stack.pop() # スタックを後に入れた順から取り出す。
CODE_C
if CONDITION_A:
CODE_D
12行目のif文がどうして必要なのかどうかがわかりません。上の図でCODE_Dを実行しないときはないはずですし、4行目でCONDITION_AがFalseになったからこそwhile文を抜けているので9行目のCODE_Dか11行目のCODE_CでCONDITION_AをTrueに変更しないと、12行目ではCONDITION_AはFalseのままで13行目のCODE_Dが実行されなくなってしまいます。
ちょっといまのところよくわかりません。
再帰関数ではCODE_CのあとにCONDTION_Aを評価する機会がないのでCODITION_Aを変更するコードはCODE_Cには含まれていないはずですし。
末尾再帰を非再帰にする方法
「末尾再帰」とは自分自身を呼び出した後には何もしない再帰のことです。
なのでこれは当然に線形再帰となります。
具体的には上の線形再帰関数foo()のうちCODE_CとCODE_Dがないものです。
def foo(n):
CODE_A
if CONDITION_A:
CODE_B
foo(m)
def foo(n):
CODE A
stack = list() # 次の処理をする間、途中の状態を保存するリスト。
while CONDITION A: # CONDITION_AがTrueの間実行。
CODE_B
stack.append() # この状態の何かをスタックに積む。
CODE_A
while stack: # スタックが空になるまで実行。
stack.pop() # スタックを後に入れた順から取り出す。
線形再帰を非再帰にしたものから単にCODE_CとCODE_Dを除くとこのようになります。帰りは寄り道なしなので行きの状態を保存しておく必要もないのでスタックはすべての場合に不必要になると思いましたが、ex13-2.dvi - ex13-2.pdfではそうでもないように書いてあります。
早速整数の階乗の例でやってみるとスタックが必要でした。
returnで式を返している再帰のときはあとでスタックから値を取り出して処理が必要でした。
んー、でもこれは戻り値を計算しないといけないので末尾再帰とはいえないような気がしますね。
returnされるところで計算していない末尾再帰の非再帰は以下のようになります。
def foo(n):
CODE A
while CONDITION A: # CONDITION_AがTrueの間実行。
CODE_B
CODE_A
参考にしたサイト
ex13-2.dvi - ex13-2.pdf
Cで再帰関数の除去方法が解説されています。
講義資料 | 数理解析・計算機数学 I | 多元数理科学研究科 | 名大の授業 (NU OCW)
上の資料はこの講座の昔の資料ではないかと思います。
各種典型再帰関数を非再帰に変換する - 競技プログラミング+αなブログ
ハノイの塔の非再帰の例もあります。Cの例。
メソッド (3)
再帰関数の働き方を図にして表現してあります。Javaの例。
非再帰で解くハノイの塔(Ｃ言語版): たった1.2人の独立戦争記
これもハノイの塔の非再帰で書く例。Cの例。
なんにもない (です): 【非再帰】ハノイの塔を解くプログラム
ハノイの塔のPythonの例。
Pythonクックブック - Google ブックス
入れ子になったシークエンスの平滑化のPythonの例。
0 件のコメント:
コメントを投稿