Python 3 Recursion - Maximum Depth Exceeded

Question

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.

"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? — Stop harming Monica, Mar 22 '16 at 19:12
is this related to your question by chance? http://stackoverflow.com/questions/31323495/1-1-2-1-3-%C2%BC-finding-sum — DevLounge, Mar 22 '16 at 19:14
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 :) ) — dsh, Mar 22 '16 at 19:35

score 1 · Answer 1 · answered Mar 22 '16 at 19:18

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.

answered Mar 22 '16 at 19:18

dsh

12,037
3
33
51

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. – Saigo no Akuma Mar 22 '16 at 19:23
1

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. – dsh Mar 22 '16 at 19:34

albertoql · Accepted Answer · 2016-03-22T19:39:01.123

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.

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. — Saigo no Akuma, Mar 22 '16 at 19:34

Python 3 Recursion - Maximum Depth Exceeded

2 Answers2

Linked