Everything else is ready: study the parts, the key terms and the quiz below.
Recursion
Solve a problem by calling the same function on a smaller version of it.
In this lesson8 parts
- 01A folder inside a folder
- 02A function that calls itself
- 03Factorial
- 04The call stack
- 05A base case that is never reached
- 06Recursion on nested data
- 07Recursion against a loop
- 08Recap, your challenge, and next
Key terms
The words this lesson introduces, each in one line. The module’s glossary collects them all.
- base case
- The part of a recursive function that returns without calling the function again:
if n <= 1: return 1. - call stack
- The frames of every call that has started and not yet returned, the newest on top.
- recursion
- A function calling itself.
- RecursionError
- The error Python raises when the call stack goes past its limit,
sys.getrecursionlimit(), which is1000. - recursive case
- The part of a recursive function that calls the function on a smaller input:
return n * factorial(n - 1).
Quiz 5 questions
Your first pick on each question is the one that counts, and a right one earns a coin. Getting one wrong here is how the lesson sticks.
Practice
Problems to solve in your own notebook. Each states the problem, not the steps: working out the steps is the exercise. Level A applies the lesson, B combines it with earlier ones, C stretches it.
The self-checking notebook for this lesson is Notebook 2 · Recursion and Functions as Values.
Common mistakes
What you will see when it goes wrong, why it happens, and the fix.
Where it’s used
Where this lesson’s ideas turn up in real work.