0

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?

TheDarkHoarse
  • 416
  • 4
  • 9
  • `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 Mar 22 '16 at 20:06
  • http://stackoverflow.com/questions/36163040/python-3-recursion-maximum-depth-exceeded Is this part of a course? – Padraic Cunningham Mar 22 '16 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 Mar 22 '16 at 20:12
  • Where are you learning recursion from? Surely it should have examples that show how a function calls itself. – Barmar Mar 22 '16 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 Mar 22 '16 at 20:20

6 Answers6

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)
Dan D.
  • 73,243
  • 15
  • 104
  • 123
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)
ilim
  • 4,477
  • 7
  • 27
  • 46
1

These numbers are better known as Harmonic Numbers. It's worth noting that H0 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).

Justin
  • 24,288
  • 12
  • 92
  • 142
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)
ThinkChaos
  • 1,803
  • 2
  • 13
  • 21
0

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

Andrew Godbehere
  • 11
  • 2
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)))
anjaneyulubatta505
  • 10,713
  • 1
  • 52
  • 62