CODEWITHSUNDEEP
pythonpython-2.7recursion
BharatRam
BharatRam

Reputation: 111

Recursion depth error in simple Python program

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.

Upvotes: 0

Views: 145

Answers (3)

Arie Xiao
Arie Xiao

Reputation: 14082

At each recursion, make the following 2 decisions:

  1. 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)
  2. 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

Upvotes: 1

vkorchagin
vkorchagin

Reputation: 656

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.

Upvotes: 3

NPE
NPE

Reputation: 500247

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.

Upvotes: 1

Related Questions