Issue with recursive function in python

Question

I have an issue with defining this function recursively. My goal is for the function to return the maximal income from a given n. n (in meters) here is the amount of cloth. The h list is the profit when selling a rug that is n meters long. For example, h[2]=5 is the profit when making a 2 meters long carpet which is for simplicity 5 dollars, and h[0]=0 since no cloth is available and no product produced. So the h list is just the market value of rugs of different lengths. I want the function to return the maximum profit if I have n meters of cloth. The prices are only defined for carpets up to 4 m, hence why the h list is what it is. The recursion for n=2 for example calculates the value of making a rug 2 m big and compares the profit with making two 1 m carpets and so on.

The recursion is loosely stated as:

income(0) = 0
income(n) = max(h[i]+income(n-i)) for 1<=i<=n

As of now, by the code below, I'm getting a recursion limit exceeded. Which I don't find weird as I have no condition for limiting the loop but the issue is I don't know how to proceed and define some sort of constraint. I realize the description here might be very confusing but please ask and I'll try to explain more extensively.

def income(n):
    h = [0,2,5,6,9]
    for i in range(n):
        return max(h[i]+income(n-i))

EDIT: This is my solution I came up with.

def income(n):
    """Returns maximum profit by a given n."""
    h = [2,5,6,9,0]
    m = []
    if n == 0:
        return 0
    else:
        for i in range(n):
            m.append(h[i]+income(n-i-1))
    return max(m)

With cache:

def memoize(f):

    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

income = memoize(income)

Your infinite recursion has to do with the first value in your list, you can always do an infinite number of free things that give you no profit. Probably you should skip over that case, as it doesn't do you any good to do nothing. This looks to be a version of the unbounded knapsack problem, which is very hard to solve efficiently, but not too hard to brute force for small cases. — Blckknght
– Blckknght, Commented May 8, 2020 at 0:18
You never stop recursion because you never use the fact that income(0) = 0. The first thing every recursive function should do is to check for the recursion termination condition. — 9000
– 9000, Commented May 8, 2020 at 3:22
Also, what your teacher meant by the second condition is max(h[i]+income(n-i) for i in range(1, n+1)); read about list comprehensions and generator expressions to understand this. — 9000
– 9000, Commented May 8, 2020 at 3:27

Blckknght · Accepted Answer · 2020-05-08 07:08:03Z

The problem you're trying to solve is a version of the unbounded knapsack problem. Instead of trying to maximize the value you can fit into a pack, you're trying to maximize the value the rugs you can make with your cloth. Instead of caring about item weight, you care about how much of your cloth gets used in the rug. But it works out the same. In any case, that's a very hard problem to solve efficiently for arbitrary inputs, but you can brute force it pretty easily for small n values.

You correctly identified that your recursion continues forever (or rather until the recursion limit) because you've not written a base case. It's actually a bit worse than that, since the first recursion is with i equal to 0, which calls the function again with the exact same n you were already trying to solve (since n-i is n when i==0).

You really don't want to recurse when i is zero, since you won't have reduced the scope of the problem at all. The simplest approach is probably just to modify your range to start i at 1, and increase from there. You also need some logic to prevent the loop from going past index 4, since you don't have any more values in the list for longer lengths.

def income(n):
    if n == 0:         # base case
        return 0
    h = [0,2,5,6,9]
    return max(h[i]+income(n-i) for i in range(1, min(n+1, len(h))))  # recursive case

In addition to adding a base case for n==0 and fixing the range, I also replaced the loop with a generator expression that does the recursion. This is necessary because max expects either several arguments (which it compares against each other), or a single iterable argument (who's values get compared). You were passing just a single value, which doesn't work.

The version above works just fine for small n values, up to about 15. But going higher than that begins to take longer and longer times because the recursion gets very deep and broad, and you end up calculating a lot of values over and over. This is what I meant when I said the knapsack problem is hard!

One trick that will speed things up a whole lot is to cache the results of each computation the first time you figure it out, and use the cached value if its needed again later.

_cache = {0: 0}   # the cache is pre-seeded to handle our base case of n=0
def income(n):
    if n not in _cache:
        h = [0,2,5,6,9]
        _cache[n] = max(h[i]+income(n-i) for i in range(1, min(n+1, len(h))))
    return _cache[n]

I'd further note that for your specific h list, it looks like it is always best to make as many 2 meter rugs as you can, plus up to one 1 meter rug to use up the last meter of cloth if you started with an odd n. So if you're willing to hard code this optimal solution to the very specific problem in your example, you could skip the recursion and just do:

def income(n):
   return n//2 * 5 + n%2 * 2

Thank you for input, I've added the solution I came up with. Feel free to comment whether it's resonable. I also added my version of a cache but i'm not sure it's working.

Collectives™ on Stack Overflow

Issue with recursive function in python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related