Python..a simple recursion function

dixiedan · 12-07-2020 9:20pm #1

I am trying to learn some python and an exercise asks to write a recursive function to sum the first n natural numbers. I came up with the following:

def sum_numbers(n):
if n == 1:
return n
elif n == 2:
return n+1
else:
return n + sum_numbers(n-1)

This seems to work, but only for n up to 995 ie

print(sum_numbers(995))

For greater than 995, an error occurs.

I can't figure out the issue.

Any ideas appreciated, thanks!

done4now · 12-07-2020 10:01pm

You've hit the max recursion depth which is set as a default of 1000 in Python. So each time you call sum_numbers(n-1) you are adding to the stack.

So your stack will look like something like this

# File "my-stack.py", line 10, in <module>
sum_numbers(996)
sum_numbers(995)
.
.
.
sum_numbers(n-1)

And none of this is processed until you reach your base case of n = 1 or 2.

https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it

Use memoization for better optimisation
https://towardsdatascience.com/memoization-in-python-57c0a738179a

On a personal note I find using iterative approach much better than recursion as its easier to read what is actually going on. I only find recursion helpful when dealing with Trees Data Structures as you don't have to write a lot of code.

Colonel Panic · 12-07-2020 10:01pm

What’s the error? Recursion can lead to stack overflow errors.

Edit: beaten to it!

dixiedan · 13-07-2020 1:11pm

Thanks for the clarification guys!

I obviously still have a lot to learn!

Python..a simple recursion function

Comments