快捷導(dǎo)航

python如何實(shí)現(xiàn)遞歸轉(zhuǎn)非遞歸

更新時(shí)間：2021年02月25日 09:33:42 作者：鄒雷

這篇文章主要介紹了python如何實(shí)現(xiàn)遞歸轉(zhuǎn)非遞歸，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下

先說(shuō)總結(jié)，這種方案總的來(lái)說(shuō)就是機(jī)械化的強(qiáng)轉(zhuǎn)，時(shí)間復(fù)雜度和空間復(fù)雜度沒(méi)什么變化，唯二的優(yōu)點(diǎn)可能是1. 不會(huì)爆棧，2. 節(jié)省了函數(shù)調(diào)用的開(kāi)銷

而且最終產(chǎn)出的代碼效果不那么美觀，比較冗長(zhǎng)

思路是：當(dāng)發(fā)生遞歸調(diào)用時(shí)，模擬函數(shù)調(diào)用的壓棧。并處理入?yún)?和返回值和記錄返回到當(dāng)前棧的時(shí)候該繼續(xù)從哪里執(zhí)行

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

def f(n):
 if n <= 2:
  return n
 return f(n - 1) + f(n - 2)

第一步：

將涉及到遞歸調(diào)用的，單獨(dú)變成最簡(jiǎn)單的一行

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)前棧的時(shí)候需要知道從哪里繼續(xù)執(zhí)行，所以需要一個(gè)flag標(biāo)記，開(kāi)始的時(shí)候?yàn)?，我們先手工標(biāo)記一下，再后序轉(zhuǎn)換的時(shí)候可以方便查看

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)?，接收遞歸調(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í)接收函數(shù)返回的時(shí)候?yàn)槭裁词且粋€(gè)字典，并且調(diào)用參數(shù)的時(shí)候傳參多了一個(gè)'a'，因?yàn)楹瘮?shù)被遞歸調(diào)用了兩次，分別得到一個(gè)a和b, 所以在返回的時(shí)候需要知道返回是給a還是給b，如果只遞歸調(diào)用了一次，那么就不需要帶上'a'，返回的時(shí)候也不用是字典了，最后整個(gè)函數(shù)執(zhí)行完成之后，base_frame里面就是最終的答案

第四步：

填充骨架，記住兩點(diǎn)就可以了

函數(shù)調(diào)用的時(shí)候，先將當(dāng)前棧的flag修改(等再次執(zhí)行到當(dāng)前棧的時(shí)候知道從哪里繼續(xù)執(zhí)行)
發(fā)生 return 的時(shí)候 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ù)編程語(yǔ)言，能將所有的遞歸調(diào)用轉(zhuǎn)化成尾調(diào)用(非尾遞歸)，這樣就不會(huì)發(fā)生爆棧的問(wèn)題，但是目前流行的大多數(shù)語(yǔ)言都是沒(méi)有這個(gè)功能的

附加練習(xí)

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

二叉樹(shù)中序遍歷

遞歸版本

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)非遞歸的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: