目錄
- 第一步：
- 第二步:
- 第三步:
- 第四步：
- 附加練習(xí)
先說總結(jié)，這種方案總的來說就是機(jī)械化的強(qiáng)轉(zhuǎn)，時間復(fù)雜度和空間復(fù)雜度沒什么變化，唯二的優(yōu)點(diǎn)可能是1. 不會爆棧，2. 節(jié)省了函數(shù)調(diào)用的開銷
而且最終產(chǎn)出的代碼效果不那么美觀，比較冗長
思路是：當(dāng)發(fā)生遞歸調(diào)用時，模擬函數(shù)調(diào)用的 壓棧 。并處理 入?yún)?和 返回值 和 記錄返回到當(dāng)前棧的時候該繼續(xù)從哪里執(zhí)行
以如下遞歸( leetcode爬樓梯 )為例
def f(n):
if n = 2:
return n
return f(n - 1) + f(n - 2)
第一步：
將涉及到遞歸調(diào)用的，單獨(dú)變成最簡單的一行
def f(n):
if n = 2:
return n
a = f(n - 1)
b = f(n - 2)
return a + b
第二步:
我們需要模擬遞歸棧調(diào)用，當(dāng)執(zhí)行完遞歸回到當(dāng)前棧的時候需要知道從哪里繼續(xù)執(zhí)行，所以需要一個flag標(biāo)記，開始的時候?yàn)?，我們先手工標(biāo)記一下，再后序轉(zhuǎn)換的時候可以方便查看
def f(n):
if n = 2:
return n
a = f(n - 1)
# flag1
b = f(n - 2)
# flag2
return a + b
第三步:
構(gòu)建解題模版
def f_iter(n):
stack = []
# 入?yún)ⅲ邮者f歸調(diào)用的(a,b), flag
base_frame = [None, {'a': None, 'b': None}, 0]
first_frame = [(n, 'a'), {}, 0]
stack.append(base_frame)
stack.append(first_frame)
while len(stack) > 1:
arg, local, flag = stack[-1]
arg, aorb = arg
if flag == 0:
pass
elif flag == 1:
pass
elif flag == 2:
pass
return stack[0][-2]['a']
first_frame = [(n, 'a'), {}, 0] 注意此時接收函數(shù)返回的時候?yàn)槭裁词且粋€字典，并且調(diào)用參數(shù)的時候傳參多了一個'a'，因?yàn)楹瘮?shù)被遞歸調(diào)用了兩次，分別得到一個a和b, 所以在返回的時候需要知道返回是給a還是給b， 如果只遞歸調(diào)用了一次，那么就不需要帶上'a'，返回的時候也不用是字典了，最后整個函數(shù)執(zhí)行完成之后，base_frame里面就是最終的答案
第四步：
填充骨架，記住兩點(diǎn)就可以了
函數(shù)調(diào)用的時候，先將當(dāng)前棧的flag修改(等再次執(zhí)行到當(dāng)前棧的時候知道從哪里繼續(xù)執(zhí)行)
發(fā)生 return 的時候 stack.pop 出棧后，將結(jié)果寫入棧頂?shù)慕Y(jié)果字典
其他照抄就行
def f_iter(n):
stack = []
# 入?yún)?，局部變?a,b), flag
base_frame = [None, {'a': None, 'b': None}, 0]
first_frame = [(n, 'a'), {}, 0]
stack.append(base_frame)
stack.append(first_frame)
while len(stack) > 1:
arg, local, flag = stack[-1]
arg, aorb = arg
if flag == 0:
if arg = 2:
stack.pop()
stack[-1][-2][aorb] = arg
else:
stack[-1][-1] = 1
new_frame = [(arg - 1, 'a'), {}, 0]
stack.append(new_frame)
elif flag == 1:
stack[-1][-1] = 2
new_frame = [(arg - 2, 'b'), {}, 0]
stack.append(new_frame)
elif flag == 2:
a, b = local['a'], local['b']
stack.pop()
stack[-1][-2][aorb] = a + b
return stack[0][-2]['a']
完結(jié)，撒花:tada:
另外：有一些函數(shù)編程語言，能將所有的遞歸調(diào)用轉(zhuǎn)化成尾調(diào)用(非尾遞歸)，這樣就不會發(fā)生爆棧的問題，但是目前流行的大多數(shù)語言都是沒有這個功能的
附加練習(xí)
有興趣可以自己按步驟試一試, 如有見解，歡迎探討:clap:
二叉樹中序遍歷
遞歸版本
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def list2tree(l):
if len(l) == 1:
return Node(l[0])
mid = (len(l) - 1) >> 1
root = Node(l[mid])
root.left = list2tree(l[:mid])
root.right = list2tree(l[mid + 1:])
return root
def inorder_recursive(root):
if not root:
return []
return inorder_recursive(root.left) + [root.val] + inorder_recursive(root.right)
l = list(range(1, 2 2))
tree = list2tree(l)
c = inorder_recursive(tree)
print(c)
非遞歸版本
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def list2tree(l):
stack = []
# (root, left_right), {'a':,'b':}, flag
base_frame = [None, {}, 0]
first_frame = [(l, 'a'), {}, 0]
stack.append(base_frame)
stack.append(first_frame)
while len(stack) >1:
cur = stack[-1]
arg, local, flag = cur
arg, aorb = arg
mid = (len(arg) - 1) >> 1
if flag == 0:
if len(arg) == 1:
stack.pop()
stack[-1][-2][aorb] = Node(arg[0])
else:
stack[-1][-1] = 1
new_frame = [(arg[:mid],'a'), {}, 0]
stack.append(new_frame)
elif flag == 1:
stack[-1][-1] = 2
new_frame = [(arg[mid+1:],'b'),{}, 0]
stack.append(new_frame)
elif flag == 2:
left, right = local['a'], local['b']
root = Node(arg[mid])
root.left = left
root.right = right
stack.pop()
stack[-1][-2][aorb] = root
return stack[0][-2]['a']
def inorder_recursive(root):
stack = []
base_frame = [None, {}, 0]
first_frame = [(root, 'a'), {'a': None, 'c': None}, 0]
stack.append(base_frame)
stack.append(first_frame)
while len(stack) > 1:
cur = stack[-1]
arg, local, flag = cur
arg, left_right = arg
if flag == 0:
if not arg:
stack.pop()
stack[-1][-2][left_right] = []
else:
stack[-1][-1] = 1
new_frame = [(arg.left, 'a'), {}, 0]
stack.append(new_frame)
elif flag == 1:
stack[-1][-1] = 2
new_frame = [(arg.right, 'c'), {}, 0]
stack.append(new_frame)
elif flag == 2:
b = [arg.val]
ret = local['a'] + b + local['c']
stack.pop()
stack[-1][-2][left_right] = ret
return stack[0][-2]['a']
l = list(range(1, 2 2))
tree = list2tree(l)
c = inorder_recursive(tree)
print(c)
以上就是python如何實(shí)現(xiàn)遞歸轉(zhuǎn)非遞歸的詳細(xì)內(nèi)容，更多關(guān)于python 遞歸轉(zhuǎn)非遞歸的資料請關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:- 10張動圖學(xué)會python循環(huán)與遞歸問題
- Python非單向遞歸函數(shù)如何返回全部結(jié)果
- python遞歸函數(shù)用法詳解
- Python尾遞歸優(yōu)化實(shí)現(xiàn)代碼及原理詳解
- python如何停止遞歸
- python利用遞歸方法實(shí)現(xiàn)求集合的冪集
- Python函數(shù)遞歸調(diào)用實(shí)現(xiàn)原理實(shí)例解析
- python實(shí)現(xiàn)文法左遞歸的消除方法
- python filecmp.dircmp實(shí)現(xiàn)遞歸比對兩個目錄的方法
- python遞歸函數(shù)求n的階乘,優(yōu)缺點(diǎn)及遞歸次數(shù)設(shè)置方式
- python 遞歸相關(guān)知識總結(jié)
