Key Concepts

Review core concepts you need to learn to master this subject

Stack Overflow Error in Recursive Function

def myfunction(n): if n == 0: return n else: return myfunction(n-1) myfunction(1000) #results in stack overflow error

A recursive function that is called with an input that requires too many iterations will cause the call stack to get too large, resulting in a stack overflow error. In these cases, it is more appropriate to use an iterative solution. A recursive solution is only suited for a problem that does not exceed a certain number of recursive calls.

For example, myfunction() below throws a stack overflow error when an input of 1000 is used.

Recursion: Python
Lesson 1 of 2
  1. 1
    The best way to understand recursion is with lots of practice! At first, this method of solving a problem can seem unfamiliar but by the end of this lesson, we’ll have implemented a variety of algo…
  2. 2
    In the previous exercise, we used an iterative function to implement how a call stack accumulates execution contexts during recursive function calls. We’ll now address the conclusion of this funct…
  3. 3
    Now that we’ve built a mental model for how recursion is handled by Python, let’s implement the same function and make it truly recursive. To recap: We want a function that takes an integer as an …
  4. 4
    Excellent job writing your first recursive function. Our next task may seem familiar so there won’t be as much guidance. We’d like a function factorial that, given a positive integer as input, re…
  5. 5
    The previous exercise ended with a stack overflow, which is a reminder that recursion has costs that iteration doesn’t. We saw in the first exercise that **every recursive call spends time on th…
  6. 6
    Let’s use recursion to solve another problem involving lists: flatten(). We want to write a function that removes nested lists within a list but keeps the values contained. nested_planets = […
  7. 7
    So far our recursive functions have all included a single recursive call within the function definition. Let’s explore a problem which pushes us to use multiple recursive calls within the fun…
  8. 8
    Data structures can also be recursive. Trees are a recursive data structure because their definition is self-referential. A tree is a data structure which contains a piece of data **and reference…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo