Issue with recursive function in python

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)

Answer

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