-4

I'm writing a basic recursion function that takes an integer, n, and returns the sum of the first n reciprocals. Inputting 2 should result in 1.5, and inputting 0 should return 0.

sum_to(2) = (1 + 1/2) = 1.5

Here's what I have:

def sum_to(n):
    if n>0:
        return sum_to(1+1/n) # Not sure if this is correct
    return 0

But all I'm getting is a Maximum recursion depth exceeded. I know I could lists to solve this, but recursion is really intriguing and I want to find a solution using it.

Improve this question
5
  • "Not sure if this is correct" You should. According to your program sum_to(1) is the same as 1 + sum_to(1). Aren't you sure if that's correct? Commented Mar 22, 2016 at 19:12
  • is this related to your question by chance? stackoverflow.com/questions/31323495/… Commented Mar 22, 2016 at 19:14
  • If you keep adding 1, will n ever equal to 0? Commented Mar 22, 2016 at 19:16
  • 1
    return sum_to(n-1) + 1 / n if n > 0 else 0 Commented Mar 22, 2016 at 19:32
  • 1
    Don't change your return 0 to print 0; now when n reaches 0 your function will return None and the addition will fail. You need to return a number from each condition. (so just undo that edit :) ) Commented Mar 22, 2016 at 19:35

2 Answers 2

Reset to default
1

From the question, it seems that you want to compute

\sum_{i=1}^{n} 1/i

If the input is 0, then returns 0.

Remember that in a recursive function, you need to define a base case and an inductive clause.

In your question, the inductive clause is:

1.0 / i + sum_of_reciprocals(i-1)

while the base case can be set to 0 when i=0.

Given this formulation, the function with an example looks like:

def sum_to(n):
    if n > 0:
        return sum_to(n-1) + 1.0 / n
    else:
        return 0

if __name__ == '__main__':
    print(sum_to(3))

and the result is 1.83333333333.

For more information about recursive functions, you can start from the related wikipedia page.

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

1 Comment

Thank you very much. Short and concise. The linked wiki page is appreciated, it will certainly help me when I create a few more practice recursions right now.
1

Trace through it to see if you ever reach your end condition:

(PS: at the time I wrote this the question's code was return 1 + sum_to(1/n))

sum_to(2):
    n is 2, which is > 0
    call sum_to(1/2)
        n is .5, which is > 0
        call sum_to(1/.5)
            n is 2, which is > 0
            call sum_to(1/2)
...

Your function never returns. The result would be infinite if you had infinite time and space to finish the calculation, since there is no end to the algorithm.

For your example, just write it this way:

def sum_to(n):
    return 1 + 1/n

What is the expected result when n > 2? That will determine how to approach organizing working code.

Improve this answer

2 Comments

Thanks, I see the error now. The expected result should be the sum of n reciprocals. ex. sum_to(2) = (1 + 1/2), where as sum_to(3) = (1 + 1/2 + 1/3). My mistake for wording the question wrong. I basically want to find the reciprocals up to the point that the reciprocal is 1/n, and stop there.
So any given term at position x the value is 1/x. For the first term 1/1 == 1, the second 1/2, the third 1/3. So you want return 1/n + sum_to(n-1) since each term has a successive position. This is explained better in albertoql's answer now.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.