avoid tail recursion python for DP

Question

I have written in Python the following recursive function for computing a solution within a DP algorithm for a weighted interval scheduling problem where the intervals are "sorted_operations". I am following the "Algorithm Design" book by Kleinberg and Tardos, and OPT and p_list have been already calculated. It seems to work for relatively small instances, but as soon as my size of the problem increases I exceed the "maximum recursion depth" and I get an error. Since increasing the sys.setrecursionlimit crashes my kernel, I am wondering if there are other ways to write this function.

solution_set = []
def compute_solution(j):
    if j<=0:
       pass
    else:
        if sorted_operations[j]['weight'] + OPT[p_list[j]] > OPT[j - 1]:
            solution_set.append(sorted_operations[j])
            print(j)
            compute_solution(p_list[j])
        else:
            compute_solution(j - 1)

compute_solution(len(sorted_operations) - 1)

the code is a bit confusing, but you can use iterations instead of recursion. — blueheart
– blueheart, Commented Oct 5, 2018 at 0:27
Without seeing p_list, sorted_operations (or at least a subset of it) and OPT I can't really offer a recommendation or solution. Also, what do you mean when you say the "size of your problem increases"? What is it increasing from and what to? If len(sorted_operations) ~ 1,000 then I'd say you have a problem but if len(sorted_operations) ~ 1,000,000 maybe not. — Woody1193
– Woody1193, Commented Oct 5, 2018 at 15:06

Woody1193 · Accepted Answer · 2018-10-05 17:04:33Z

1

Without knowing more about your code, I can't really offer a detailed solution. However, one part of your algorithm did stick out in my mind: compute_solution(j - 1). Since j is an integer, calling the algorithm again with j - 1 fits a loop better than a method call, especially since these tend to be somewhat expensive in Python. So, I would modify your algorithm like this:

solution_set = []
def compute_solution(j):
    while (j > 0):
        if sorted_operations[j]['weight'] + OPT[p_list[j]] > OPT[j - 1]:
            solution_set.append(sorted_operations[j])
            print(j)
            compute_solution(p_list[j])
            return
        else:
            j = j - 1

compute_solution(len(sorted_operations) - 1)

Depending on how often that else statement is run, this could be a major benefit.

edited Oct 5, 2018 at 17:04

answered Oct 5, 2018 at 15:11

Woody1193

8,2029 gold badges65 silver badges129 bronze badges

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

2 Comments

Mike Over a year ago

Thank you @Woody. I gave it a try and it seems to work for larger instances (e.g. 10,000 intervals). However, it is not very clear why the usage of the <break> in the if statement.

Woody1193 Over a year ago

@Michele If you don't use the break then you'll get stuck in an infinite-loop as the value of j is only updated in the else and it's unclear whether or not the if would evaluate to the same result on subsequent calls. Note that a return statement would work equally well if you want to use that as your base case but I was unsure as to whether or not other code existed after the code you had in your question

Collectives™ on Stack Overflow

avoid tail recursion python for DP

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related