CODEWITHSUNDEEP
pythonloopsrecursioniteration
Hipster1206
Hipster1206

Reputation: 421

Iterative to recursion function for non-tail recursive methods

I am trying to write an iterative method for the following recursion program. I tried multiple methods but that got me nowhere.

I tried Googling too but was not able to figure it out. Could someone give me some idea on how to deal with it?

Please note that my function is non-tail recursive. I have some other things to do at the end of the recursion

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)

Output:

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

Upvotes: 2

Views: 356

Answers (1)

6502
6502

Reputation: 114579

If the function is not tail-recursive you need to handle an explicit stack... for example

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))

Upvotes: 5

Related Questions