Recursive sum function in python?

Question

Essentially I am trying to create a function, r_sum(n), that will return the sum of the first "n" reciprocals: e.g. sum(5) = 1 + 1/2 + 1/3 + 1/4 + 1/5 .I am new to recursion and am having trouble with the implementation. Here is the code I have so far:

def r_sum(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return 1/n

I think I have created the base of the function, but I'm not sure where I would have the function call itself. As of now, I realize the function will only return the value of 1/n. How can I add to this so that I have the function call itself to calculate this sum?

def sum_to(n): return 0 if n == 0 else 1./n + sum_to(n-1) — »All too easy. Maybe you're not as strong as I thought.« — Alfe
– Alfe, Commented Mar 22, 2016 at 20:06
stackoverflow.com/questions/36163040/… Is this part of a course? — Padraic Cunningham
– Padraic Cunningham, Commented Mar 22, 2016 at 20:07
Well, a comment should remain which states that in Python 3 things like 1/n will create a float even if n is an integer. Since that is a uncommon thing for other programming languages (even Python 2 will return an int, 0 for most n), that comment still makes sense. — Alfe
– Alfe, Commented Mar 22, 2016 at 20:12
Where are you learning recursion from? Surely it should have examples that show how a function calls itself. — Barmar
– Barmar, Commented Mar 22, 2016 at 20:14
I realize this was a simple fix, and apologize if the question was redundant. Also, this was not a part of a course. — TheDarkHoarse
– TheDarkHoarse, Commented Mar 22, 2016 at 20:20

Dan D. · Accepted Answer · 2016-03-22 20:07:40Z

4

Think of:

sum(5) = 1 + 1/2 + 1/3 + 1/4 + 1/5

as:

sum(5) = 1/5 + sum(4)
sum(4) = 1/4 + sum(3)
sum(3) = 1/3 + sum(2)
sum(2) = 1/2 + sum(1)
sum(1) = 1

As such:

sum(x) = 1/x + sum(x-1)
sum(1) = 1

And thus the last case should be:

return 1/n + sum_to(n - 1)

answered Mar 22, 2016 at 20:07

Dan D.

75k15 gold badges111 silver badges129 bronze badges

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

Comments

ilim · Accepted Answer · 2016-03-22 20:06:14Z

3

Try to think of solving a piece of the problem so that the rest of it is another instance of the same problem, just for a smaller chunk.

def sum_to(n):
    if n == 0:
        return 0.0
    elif n == 1:
        return 1.0
    else:
        return 1.0/n + sum_to(n-1)

answered Mar 22, 2016 at 20:06

ilim

4,5477 gold badges30 silver badges50 bronze badges

Comments

Justin · Accepted Answer · 2016-03-22 20:08:29Z

1

These numbers are better known as Harmonic Numbers. It's worth noting that H₀ isn't usually defined, but that's beside the point.

What do you want sum_to(n) return? You probably expect 1/n + 1/(n-1) + ... right? So we shouldn't be simply returning 1/n. You should look at the rest of that expression and find where you can find sum_to(n - 1).

answered Mar 22, 2016 at 20:08

Justin

25.7k12 gold badges97 silver badges145 bronze badges

Comments

ThinkChaos · Accepted Answer · 2016-03-22 20:09:17Z

0

When you write a recursive function, you need two things:

a stop case
the other general case (which is recursively defined)

Here, your stop case is 0. We know sum_to(0) == 0.
The general case is: sum_to(n) == 1.0/n + sum_to(n - 1).

All that is left to do is join these in a function:

def sum_to(n):
    if n == 0:
        return 0

    return 1.0/n + sum_to(n - 1)

answered Mar 22, 2016 at 20:09

ThinkChaos

1,8932 gold badges13 silver badges22 bronze badges

Comments

Andrew Godbehere · Accepted Answer · 2016-03-23 04:44:51Z

Using generators is the Pythonic (as opposed to the pedantic) way to solve this problem.

def g_sum(n):
    """
    Solution using generators instead of recursion.
    Input validation suppressed for clarity.
    """
    return sum(1/x for x in range(1, n+1))

def r_sum(n):
    """
    Recursive solution proposed by @Alfe
    """
    return 0 if n == 0 else 1/n + r_sum(n-1)

Timing the function shows that the generator solution is approx. twice as fast:

Generator:
- %timeit -n 10000 v1 = g_sum(100)
- 10000 loops, best of 3: 9.94 µs per loop
Recursion:
- %timeit -n 10000 v2 = r_sum(100)
- 10000 loops, best of 3: 22 µs per loop

In addition, the recursive implementation will hit a recursion limit very quickly making it very impractical for real-world use.

Specifically: r_sum(1000) fails with RecursionError: maximum recursion depth exceeded in comparison

anjaneyulubatta505 · Accepted Answer · 2016-06-02 17:03:19Z

0

you can do this in two ways

def r_sum(n):
    if n == 1:
        return 1
    return (1/n) + r_sum(n-1)

or

def r_sum(n):
    return sum(map(lambda x:1.0/x, xrange(1, n+1)))

answered Jun 2, 2016 at 17:03

anjaneyulubatta505

11.9k1 gold badge61 silver badges68 bronze badges

Collectives™ on Stack Overflow

Recursive sum function in python?

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related