How to Transform Recursive to Non recursive in python

Catalog Step 1: Step 2: Step 3: Step 4: Additional exercises

First of all, this scheme is a mechanized strong turn in general, and the time complexity and space complexity have no change. Only the advantages of 2 may be 1. No stack explosion, 2. Saving the overhead of function call

Moreover, the final output code effect is not so beautiful and lengthy

The idea is to simulate the stack of function calls when recursive calls occur. And handle where to continue when input and return values and records are returned to the current stack

Take the following recursion (leetcode climbing stairs) as an example

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

Step 1:

Turn the single line involving recursive calls into the simplest 1 line

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

Step 2:

We need to simulate the recursive stack call, when the recursive back to the current stack, we need to know where to continue the execution, so we need an flag mark, which is 0 at the beginning, we first manually mark 1, and then we can easily view it when we convert the order

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

Step 3:

Build a problem-solving template

def f_iter(n):
 stack = []
 #  Enter a parameter to receive a recursively called (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] Note why it is a dictionary when the receiving function returns at this time, And when calling parameters, one more 'a' is passed, Because the function is called recursively twice, and one a and one b are obtained respectively, it is necessary to know whether to return to a or b when returning. If it is called recursively only once, then it is not necessary to bring 'a', and it is not necessary to return a dictionary. Finally, after the whole function is executed, base_frame is the final answer

Step 4:

Fill the skeleton and remember two points

When calling a function, first modify the flag of the current stack (when you execute to the current stack again, you know where to continue execution)
When return occurs, after stack. pop is out of the stack, the result is written into the result dictionary at the top of the stack
Just copy the others

def f_iter(n):
 stack = []
 #  Input parameter, local variable (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']

End, sprinkle flowers: tada:

In addition, there are 1 functional programming languages that convert all recursive calls to tail calls (non-tail recursive), so that there is no problem of stack bursting, but most popular languages do not have this function at present

Additional exercises

If you are interested, you can try it step by step. If you have any opinions, please discuss it: clap:

Ordered traversal in 2-tree

Recursive version

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)

Non-recursive version

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)

The above is python how to achieve recursive to non-recursive details, more about python recursive to non-recursive information please pay attention to other related articles on this site!