はじめに
再帰関数の話題を書いてみます。
再帰関数をStackを使って再帰関数を使わない記述に書き換える方法をまとめてみます。
AtCoderのABC394Fで再帰関数を使った記述がきっかけです。
AtCoderでPyPyを使う人は、bootstrap と呼ばれる、デコレータを使って再帰を解消する方法をよく使ってるようですが、この記事では、最初から、再帰を使わない方法で記述することを行ってみます。
再帰を使った場合
サンプルにする再帰関数は、ABC394Fで、[MLE（メモリが上限を超えた）で不正解]となった深さ優先探索をするプログラムです。
ans = 0
def dfs(s,parent):
global ans
result = []
for next in g[s]:
if next == parent:
continue
x = dfs(next,s)
result.append(x)
result.sort(reverse=True)
if len(result)>=3:
ret = sum(result[:3])+1
else:
ret = 1
if len(result)>=4:
ans = max(ans,sum(result[:4])+1)
if len(result)>0:
ans = max(ans,result[0]+1)
# print(s+1,ret,ans,result)
return ret
再帰を使わない場合（行きがけ）
再帰では、自分自身を呼び出して、潜っていく段階（行きがけ）と、再帰関数からリターンして戻る段階（帰りがけ）があります。
行きがけを繰り返して、そのあと帰りがけを繰り返して戻るような単純な場合もありますが、行きがけ、帰りがけを繰り返すような場合もあります。
まずはこのうちの行きがけの処理だけをstackを使って書いてみます。
stack = [(0,None)]
order = []
while stack:
s,parent = stack.pop()
order.append((s,parent))
for next in g[s]:
if next == parent:
continue
stack.append((next,s))
元の関数の引数にしていたものをstackに保存するものにします。
ここでは、元のプログラムでは、s,parentの二つがあるので、タプルにして、
stack = [(0,None)]とします
stackから引数の値をとりだす。
↓
次の値を求める
↓
次の値をstackに保存する
↓
最初に戻る
この繰り返しで、再帰関数が呼ばれる時の引数を再現できます。
これで行きがけの動作を再現することができました。
この引数をorderリストに保存しておきます。
この値を次の処理で使用します。
再帰を使わない場合（帰りがけ）
再帰の帰りがけの処理は、行きがけで一番奥まで潜ったところから逆順に行う必要があります。
行きがけで保存したorderを逆順にしたも順に行えばよいことになります。
orderの逆順にしたものを１つづつ取り出して、帰りがけの処理を行います。
この時、再帰関数の場合は、呼び出し元に値を返す処理と、呼び出された関数から値を得る処理の記述があります。
再帰の場合は、これが自動的に接続されますが、再帰を使わない場合、仲介する仕組みが必要になります。
dpという配列用意してこれに保存してみます。
| 再帰の場合 | 再帰を使わない場合 | |
|---|---|---|
| 呼び出し元に値を返す | return ret | dp[s] = ret |
| 呼び出した関数から値を得る | x = dfs(next,s) | x = dp[next] |
dp = [[0] for _ in range(N)]
for s,parent in order[::-1]:
result = []
for next in g[s]:
if next == parent:
continue
x = dp[next]
result.append(x)
result.sort(reverse=True)
if len(result)>=3:
ret = sum(result[:3])+1
else:
ret = 1
if len(result)>=4:
ans = max(ans,sum(result[:4])+1)
if len(result)>0:
ans = max(ans,result[0]+1
)
dp[s] = ret
まとめ
- 再帰の処理は行きがけだけであれば、Stackに引数の値を積み繰り返すことで実現できる
- 帰りがけの処理は、行きがけの処理順を求めて、逆順に行う事で実現できる
宿題
今回は、再帰を使わない場合は、引数と結果の対を保存するテーブル（dp）を用意した。
しかし、再帰の場合は、リターンする値もスタックに保存されて、dpのような纏まった領域は必要としていません。
再帰を使わない場合もリターン値をStackに保存する方法を検討してみる