Advertisement
Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.
https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.

Python..a simple recursion function

  • 12-07-2020 09:20PM
    #1
    Registered Users, Registered Users 2 Posts: 816 ✭✭✭


    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!


Comments

  • Registered Users, Registered Users 2 Posts: 106 ✭✭done4now


    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.


  • Registered Users, Registered Users 2 Posts: 2,062 ✭✭✭Colonel Panic


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

    Edit: beaten to it!


  • Registered Users, Registered Users 2 Posts: 816 ✭✭✭dixiedan


    Thanks for the clarification guys!

    I obviously still have a lot to learn!


Advertisement