Iterative to recursion function for non-tail recursive methods

Question

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

Why? (since there are 2 recursive invocations you'd have to use some complicated enough code, maybe with stack to mimic that recursion)... Maybe you are looking for memoization ? — Alexei Levenkov
– Alexei Levenkov, Commented Jan 4, 2016 at 8:55
Thanks yes memoization works too but when should i store the result ?...after both recursive call ? ie after rec(i+1,j) and as well as after rec(i,j+1) or just at the last would be good enough ?(ie after rec(i,j+1))? — Hipster1206
– Hipster1206, Commented Jan 4, 2016 at 10:51

6502 · Accepted Answer · 2016-01-04 08:58:18Z

5

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

answered Jan 4, 2016 at 8:58

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Iterative to recursion function for non-tail recursive methods

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related