先說總結，這種方案總的來說就是機械化的強轉，時間復雜度和空間復雜度沒什么變化，唯二的優點可能是1. 不會爆棧，2. 節省了函數調用的開銷

而且最終產出的代碼效果不那么美觀，比較冗長

思路是：當發生遞歸調用時，模擬函數調用的 壓棧 。并處理 入參 和 返回值 和 記錄返回到當前棧的時候該繼續從哪里執行

以如下遞歸( leetcode爬樓梯 )為例

def f(n): if n <= 2: return n return f(n - 1) + f(n - 2)第一步：

將涉及到遞歸調用的，單獨變成最簡單的一行

def f(n): if n <= 2: return n a = f(n - 1) b = f(n - 2) return a + b第二步:

我們需要模擬遞歸棧調用，當執行完遞歸回到當前棧的時候需要知道從哪里繼續執行，所以需要一個flag標記，開始的時候為0，我們先手工標記一下，再后序轉換的時候可以方便查看

def f(n): if n <= 2: return n a = f(n - 1) # flag1 b = f(n - 2) # flag2 return a + b第三步:

構建解題模版

def f_iter(n): stack = [] # 入參，接收遞歸調用的(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] 注意此時接收函數返回的時候為什么是一個字典，并且調用參數的時候傳參多了一個’a’，因為函數被遞歸調用了兩次，分別得到一個a和b, 所以在返回的時候需要知道返回是給a還是給b， 如果只遞歸調用了一次，那么就不需要帶上’a’，返回的時候也不用是字典了，最后整個函數執行完成之后，base_frame里面就是最終的答案

填充骨架，記住兩點就可以了

函數調用的時候，先將當前棧的flag修改(等再次執行到當前棧的時候知道從哪里繼續執行)發生 return 的時候 stack.pop 出棧后，將結果寫入棧頂的結果字典其他照抄就行

def f_iter(n): stack = [] # 入參，局部變量(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’]

完結，撒花:tada:

另外：有一些函數編程語言，能將所有的遞歸調用轉化成尾調用(非尾遞歸)，這樣就不會發生爆棧的問題，但是目前流行的大多數語言都是沒有這個功能的

有興趣可以自己按步驟試一試, 如有見解，歡迎探討:clap:

二叉樹中序遍歷

遞歸版本

class Node: def __init__(self, val): self.val = val self.left = None self.right = Nonedef 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 rootdef 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 = Nonedef 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如何實現遞歸轉非遞歸的詳細內容，更多關于python 遞歸轉非遞歸的資料請關注好吧啦網其它相關文章！