Recursion depth error in simple Python program

Question

I am new to programming, and was trying to solve this problem on Project Euler using basic Python.

Essentially, I tried to use recursion based on the largest value chosen at every stage, and using a list to maintain possible options for future choices.

The code is short and is given below:

def func(n,l):
    if n<0:
        return 0
    if l==[1] or n==0:
        return 1
    else:
        j=0
        while l != []:
            j=j+func(n-l[0],l) 
            del l[0]
        return j

print func(200,[200,100,50,20,10,5,2,1])

For instance, if we have

func(5,[5,2,1])

the recursion splits it into

func(0,[5,2,1]) + func(3,[2,1]) + func(4,[1])

But the code never seems to go through. Either it says that there is a list-index-out-of-range error, or a maximum-recursion-depth error (even for very small toy instances). I am unable to find the mistake. Any help will be much appreciated.

vkorchagin · Accepted Answer · 2013-03-28 08:09:57Z

3

In Python lists are passed into functions by reference, but not by value. The simplest fix for your program is changing recursive call to func(n - l[0], l[:]). In this way list will be passed by value.

answered Mar 28, 2013 at 8:09

vkorchagin

6564 silver badges7 bronze badges

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

Comments

NPE · Accepted Answer · 2013-03-28 08:07:25Z

1

One thing you're failing to take into account is that the following:

j=j+func(n-l[0],l)

doesn't make a copy of l.

Therefore all recursive invocations of func operate on the same list. When the innermost invocation deletes the last element of l and returns, its caller will attempt to del l[0] and will get an IndexError.

answered Mar 28, 2013 at 8:07

NPE

503k114 gold badges970 silver badges1k bronze badges

1 Comment

BharatRam Over a year ago

I understand the problem now. Thanks!

Arie Xiao · Accepted Answer · 2013-03-28 08:27:28Z

1

At each recursion, make the following 2 decisions:

Take the first coin (say f) from available coin types, then check if we can made (n-f) from those coins. This results in a sub-problem func(n - f, l)
Ignore the first coin type, and check if we can make n from the remaining coin types. This results in a sub-problem func(n, l[1:])

The total number of combinations should be the sum of the two sub-problems. So the code goes:

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    return func(n - l[0], l) + func(n, l[1:])

Each recursion a copy of l is made by l[1:]. This can be omitted by pop element before next recursion and restore with append afterwards.

def func(n, l):
    if n == 0:
        return 1
    if n < 0 or len(l) == 0:
        return 0
    if l == [1] or n == 0:
        return 1

    full = func(n - l[-1], l)
    last = l.pop()
    partial = func(n, l)
    l.append(last)
    return full + partial

answered Mar 28, 2013 at 8:27

Arie Xiao

14.1k3 gold badges35 silver badges31 bronze badges

1 Comment

BharatRam Over a year ago

Yeah, I had used the same method as you suggested above, but the error arose from referring to the list, as was pointed out. The simple fix suggested in the previous answer (namely replacing j=j+func(n-l[0],l) with j=j+func(n-l[0],l[:]) resolved the problem. But thanks for your solution too!

Collectives™ on Stack Overflow

Recursion depth error in simple Python program

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related