Recursion code in python

Question

I'm new to python and trying to solve my homework... I'm trying to create a recursion function that takes a list of numbers [a, b, c....] and turns it to this list: [a, a+b, a+b+c, ....].

This is my code:

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    new_list=numbers
    last=new_list[-1]
    if numbers==[]:
         return numbers
    if len(numbers) == 1:
         return numbers[0]
    new_list.remove(last)
    rec= rec_cumsum(new_list)
    new_list.append(rec+last)
    return last+rec

this works but because I used return for last+rec, I can't use return to get the list back (new_list). Please explain to me what did I do wrong... thanks!

You'll have to fix your indentation first, this is not valid Python code as it stands. — Martijn Pieters
– Martijn Pieters, Commented Nov 18, 2012 at 12:28
I don't know why it copied my code like that but the indentation is correct in the code itself. — Yarden
– Yarden, Commented Nov 18, 2012 at 12:30
Then you are mixing tabs and spaces. Don't do that. Stick to spaces instead, configure your editor to convert tabs to spaces. — Martijn Pieters
– Martijn Pieters, Commented Nov 18, 2012 at 12:32
@Pearsonartphoto: way ahead of you. Not weird, SO uses 4 spaces for tabs when displaying, 8 when editing.. — Martijn Pieters
– Martijn Pieters, Commented Nov 18, 2012 at 12:33

unutbu · Accepted Answer · 2012-11-18 13:48:57Z

Let's write some test cases and practice some test-driven development:

tests = [[],         # Desired answer: []
         [1],        # [1]
         [1,2],      # [1, 3] 
         [1,2,3],    # [1, 3, 6]
         [1,2,1,3]]  # [1, 3, 4, 7]
for t in tests:
    print(rec_cumsum(t))

If we add this to your code and run it, we get:

    last=new_list[-1]
IndexError: list index out of range

Why is this? Apparently -1 is an out-of-range index. Why wouldn't new_list have a -1 index?

Aha. That happens if new_list is empty. So we need to address the base case first. While we're at it, let's also use @MartijnPieters' suggestion:

if len(numbers) <= 1:
     return numbers

to obtain

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers
    last=new_list[-1]
    new_list.remove(last)
    rec = rec_cumsum(new_list)
    new_list.append(rec[-1]+last)
    return last+rec

Now run the test again. This time we get

    return last+rec
TypeError: unsupported operand type(s) for +: 'int' and 'list'

So now Python is saying last is an int and rec is a list, and we can not add the two together.

Okay, rec should be a list since it is the return value of rec_cumsum(new_list). What should replace last+rec?

Let's think in terms of a concrete example. If rec is [a, a+b] then we want to return [a, a+b, a+b+c]. How do we form a+b+c?

How about adding the last element in rec with the last element of numbers:

rec[-1]+last

We want to append this to the end of rec:

rec.append(rec[-1]+last)

Let's make that change and see what happens. But while we're editing, let's also clean up some code we never use. We can delete new_list.append(rec[-1]+last):

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers
    last=new_list[-1]
    new_list.remove(last)
    rec = rec_cumsum(new_list)
    rec.append(rec[-1]+last)
    return rec

Now our program returns

[]
[1]
[1, 3]
[1, 3, 6]
[2, 3, 4, 7]

Hurray, our program runs without errors. But wait... it returns the wrong results. Look at the last line.

rec_cumsum([1,2,1,3]) is returning [2,3,4,7] whereas the correct answer is [1,3,4,7]. Why is the first number wrong?

It has to do with new_list.remove(last). This command removes the first occurrence of last from new_list. We want to remove the last occurrence.

So instead, let's use

new_list = numbers[:-1]

So the program becomes:

def rec_cumsum(numbers):
    ''' Input: numbers - a list of numbers,
            Output: a list of cumulative sums of the numbers'''
    if len(numbers) <= 1:
         return numbers
    new_list=numbers[:-1]
    last=numbers[-1]
    rec = rec_cumsum(new_list)
    rec.append(rec[-1]+last)
    return rec

Run the tests. It works! Now it is a good practice to look back at our solution and see how it can be tightened up and made more elegant. I see we used new_list and last as temporary variables. Do we really need them?

def rec_cumsum(numbers):
    if len(numbers)<=1:
        return numbers
    result = rec_cumsum(numbers[:-1])
    result.append(result[-1]+numbers[-1])
    return result

Martijn Pieters · Accepted Answer · 2012-11-18 13:16:37Z

Your function should always return a list; for the empty list case, an empty list, and for the case where there is only one element, a list with only one element.

But your code returns the one element, not a list with one element:

if len(numbers) == 1:
     return numbers[0]

Change that to returning just numbers:

if len(numbers) == 1:
     return numbers

You can combine this with the other end-state test:

if len(numbers) < 2:
     return numbers

Next problem is that you are not creating a copy of a list when you create the variable new_list; you create a reference to the same list, you'd have to use a slice or create an explicit new list:

new_list = numbers[:]

If you are going to remove a value from that list anyway, you may as well adjust the slice a little, and put this after testing numbers (why do the work otherwise):

if len(numbers) < 2:
     return numbers
new_list = numbers[:-1]
last = numbers[-1]

Nowhere in your code do you actually compute a sum; nothing is added to your numbers. You never add a to b, c, etc. Moreover, you seem to be focusing on the last number, while your assignment states you needed to sum the first value to the rest of the list.

And there is a pattern there. Not only do you add a to b, but the sum of a + b is added to c, and that sum is then added to d, etc. Let's make use of that:

def rec_cumsum(numbers, culmulated_sum=0):
    if len(numbers) < 1:
        return numbers
    sum = numbers[0] + culmulated_sum
    return [sum] + rec_cumsum(numbers[1:], sum)

Note that I don't even bother storing a copy of numbers now; may as well just pass it to the next recursion as a slice of everything but the first element. We also use the first element from numbers to create our sum (numbers[0]).

Also, we now pass along the culmulative sum so far, starting at 0; and that means we need to change the end condition of the recursive function; we are essentially adding [0] to the start of the list, and we want to make sure we sum that with the next element always.

This now does what you need:

>>> rec_cumsum([5, 1, 10, 2, 3])
[5, 6, 16, 18, 21]

Collectives™ on Stack Overflow

Recursion code in python

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related