python - 迭代到非尾递归方法的递归函数

Question

我正在尝试为以下递归程序编写迭代方法。我尝试了多种方法，但无济于事。

我也尝试使用谷歌搜索，但无法弄明白。有人可以告诉我如何处理它吗？

请注意我的函数是非尾递归的。在递归结束时我还有一些其他的事情要做

def rec(i,j):
  print "Inside funciton ", i, j
  if i == 3:
    return
  if j == 3:
     return
  rec(i+1,j)
  # Some code
  rec(i,j+1)
  # Some code

rec(0,0)

输出:

Inside funciton  0 0
Inside funciton  1 0
Inside funciton  2 0
Inside funciton  3 0
Inside funciton  2 1
Inside funciton  3 1
Inside funciton  2 2
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 1
Inside funciton  2 1
Inside funciton  3 1
Inside funciton  2 2
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 2
Inside funciton  2 2
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 3
Inside funciton  0 1
Inside funciton  1 1
Inside funciton  2 1
Inside funciton  3 1
Inside funciton  2 2
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 2
Inside funciton  2 2    
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 3
Inside funciton  0 2
Inside funciton  1 2    
Inside funciton  2 2
Inside funciton  3 2
Inside funciton  2 3
Inside funciton  1 3
Inside funciton  0 3

Answer 1

如果函数不是尾递归的，则需要处理显式堆栈...例如

todo = [(0, 0)]
while todo:
    i, j = todo.pop()
    print "processing ", i, j
    if i != 3 and j != 3:
        todo.append((i, j+1))
        todo.append((i+1, j))