Recursion: Python
Recursion gives you a new perspective on problem-solving by defining a problem in terms of itself.
Start
Key Concepts
Review core concepts you need to learn to master this subject
Stack Overflow Error in Recursive Function
Fibonacci Sequence
Call Stack Construction in While Loop
Binary Search Tree
Recursion and Nested Lists
Fibonacci Recursion
Modeling Recursion as Call Stack
Recursion in Python
Stack Overflow Error in Recursive Function
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 errorA 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.
- 1The 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…
- 2In 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…
- 3Now 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 …
- 4Excellent 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…
- 5The 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…
- 6Let’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 = […
- 7So 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…
- 8Data 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
Recursion: Python
Start