CODEWITHSUNDEEP
recursion
John Smith
John Smith

Reputation: 12236

Need to make this recursive algorithm iterative due to stack overflow

Basically I have this huge function in Python (which I've simplified to the bare basics)

def rec(a,b):
  if stoppingCondition==True: return 1

  key=(a,b)
  if key in memo: return memo[key]

  if b==side condition:
       memo[key]=rec(a+1,b)   #RECURSIVE CALL
       return memo[key]

  total=0
  for d in D:
      if condition1==True:
          b=some process 1
          total+=rec(a+1,b)   #RECURSIVE CALL
      elif condition2==True:
          for x,y in d:
              if (some break condition==True): break
          else: #only gets called if break didnt happen
              b=some process 2
              total+=rec(a+1,b)   #RECURSIVE CALL
   memo[key]=total
   return memo[key]

And I am having a heck of a time making it iterative because it blows up for deeper recursive levels. I've already read up other threads about converting to loops and stacks and whatnot but I just can't get any of it working.

Upvotes: 1

Views: 99

Answers (1)

Gustav Larsson
Gustav Larsson

Reputation: 8487

You can always calculate rec(a, b) for all b, starting at the highest a and decreasing in a simple loop without recursion. Now, this solution is not viable if the traversal of all possible calls to rec() is sparse, since it will introduce a lot of unnecessary calculations.

Another solution is to try to implement tail-call optimization in Python. I haven't tried it, but you might want to test this decorator.

A less elegant solution is to increase the recursion limit to fit your need:

import sys
sys.setrecursionlimit(10000)

Upvotes: 1

Related Questions