recursive cumulative sums

Question

I need to write a program that compute cumulative sums from a list of numbers with def but ONLY with recursion. I did it, but now I need to write the same program without using the method sum, but no success so far. Any idea?

my code:

def rec_cumsum(numbers):
        ''' Input: numbers - a list of numbers,
                Output: a list of cumulative sums of the numbers'''
        if len(numbers)==0: return numbers

        return rec_cumsum(numbers[:-1])+ [sum(numbers)]

input:

1 [1,2,3]

2 [2, 2, 2, 3]

output:

1 [1,3,6]

2 [2, 4, 6, 9]

my code without sum:

def rec_cumsum(numbers):
        ''' Input: numbers - a list of numbers,
                Output: a list of cumulative sums of the numbers'''
        if len(numbers) == 0: return numbers
        my_list=[]
        rec_cumsum(my_list + numbers)
        my_list[0]=numbers[0]
        rec_cumsum(my_list)
        temp_sum=my_list[0]+numbers[-1]
        my_list[0]=temp_sum
        return my_list

@user1816377.. Can you post an example showing what you want. Please post a sample input and expected output. — Rohit Jain, Nov 12 '12 at 16:40
your querstion is how to do it "without using the method sum"? — gefei, Nov 12 '12 at 16:52
you will need to keep a running total of the current sum somehow ... maybe pass it as an optional argument ;) — Joran Beasley, Nov 12 '12 at 16:52
Problems in your new code: - `1st` - You should pass `numbers` to your recursive call, not `my_list`. `2nd` you have declared your my_list inside your method only. Declare it ourside. — Rohit Jain, Nov 12 '12 at 17:40

go2 · Answer 1 · 2012-11-19T12:17:59.503

3

I would suggest something like this without adding additional arguments:

[UPDATED]

def rec(n):
    if len(n) < 2: return n
    n[1] = n[0] + n[1]
    return [n[0]] + rec(n[1:])


print rec([1,2,3,4])
[1, 3, 6, 10]

edited Nov 19 '12 at 12:17

answered Nov 12 '12 at 16:58

go2

378
4
14

a minor thing is that this might fail if you give empty list as an input, you may try what I did to avoid that. +1 for this clever solution.. – none Nov 16 '12 at 20:57

Rohit Jain · Accepted Answer · 2012-11-12T17:44:06.327

2

What you can do is: -

Create a temp list(an empty one).
Pass your original list and the empty list in your method.
Now, when you pass your list for the first time, just add the first element from your original list to it. And call the same method with the rest of the list. Starting from 1st element.
When your method is invoked after wards, you need to take a sum of last element of your temp list and first element of the original list that is now modified. And add the sum to your temp list as new element.
Finally, when the length of your original list becomes 0. Return your temp.

**Here's the code for the above steps. You can compare it with the one you have implemented, and see where you went wrong: -

def rec_cumsum(numbers):
    if len(numbers) == 0 : return temp

    # You need to check, if `temp` is empty, that means method is called first time.
    if not temp:   
        temp.extend([numbers[0]])   // Just add the first element to it.

    else:
        # Else, get the last element from `temp`, 
        # add it to `first elemt` in `numbers` and add it to `temp`.
        temp.extend([temp[-1] + numbers[0]])

    return rec_cumsum(numbers[1:])

my_list = [2, 2, 2, 3]
temp = []
print rec_cumsum(my_list)

edited Nov 12 '12 at 17:44

answered Nov 12 '12 at 16:34

Rohit Jain

209,639
45
409
525

@JoranBeasley.. Umm. I asked OP for further clarification. Let's see. If this is not what he wants, I'll update my answer. – Rohit Jain Nov 12 '12 at 16:41
@RohitJain My func has to get only 1 argument, I have to keep it that way. – user1816377 Nov 12 '12 at 16:52
@user1816377.. Then modify the code, and now its some steps, according to your need. Dont' pass your `temp` list in your method. Try it, it should work. – Rohit Jain Nov 12 '12 at 16:58
passing only a number as second value ... and you can make second value optional ... that way its not required and `my_func([1,2,3])` will still work – Joran Beasley Nov 12 '12 at 16:58
Exactly. It should work. You just need to do a little bit modification. That you should try out your self. – Rohit Jain Nov 12 '12 at 17:00
@user1816377.. Ok. So, how did you try to implement all the steps that I posted? Can you post it in OP? – Rohit Jain Nov 12 '12 at 17:30
@user1816377.. There are some problems with your code, that I have pointed out in comments. Also, I have posted the code. You can compare it with yours and see how it works. Good luck. :) – Rohit Jain Nov 12 '12 at 17:45
thank you so much! can I declare temp in the func? b/c I need to write the func and run it just as it is on some built-in tests I got, without define more var on my own. @RohitJain – user1816377 Nov 12 '12 at 18:03
@user1816377.. No. you can't declare it in function. Because that will be re-declared whenever you call that function in recursion. Another option is of course to pass it as parameter. But that you don't want. – Rohit Jain Nov 12 '12 at 18:04
let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/19444/discussion-between-user1816377-and-rohit-jain) – user1816377 Nov 12 '12 at 18:07

score 2 · Answer 3 · answered Nov 16 '12 at 20:55

2

yet another solution would be:

def rec(n):
    if len(n) < 2: return n
    rest = rec(n[:-1])
    return rest + [rest[-1] + n[-1]]

this one feels more intuitive to me..

answered Nov 16 '12 at 20:55

none

11,793
9
51
87

recursive cumulative sums

3 Answers3

Linked