Recursion in Python
Level 4 · Functions
What recursion is: a function that calls itself on a smaller job. Why it needs a base case to stop, and the limit of 1,000 calls.
Course contentsLesson 14 of 18
Level 1 · What a program is
Level 2 · Values and variables
Level 3 · Decisions and loops
Level 4 · Functions
Level 5 · Errors and debugging
Level 6 · Good code habits
After this lesson you can
- Explain how a function can call itself
- Write a base case that stops recursion
- Say when a loop is the better choice
12 mincovers 2 glossary entries
Worth reading first: Scope and Passing Arguments
How a function can call itself, and why it stops
Recursion is when a function calls itself to solve a smaller copy of the same job. To count down from 3, a function prints 3, then calls itself to count down from 2. That call prints 2 and calls itself for 1. Python allows about 1,000 calls deep by default before it stops the program.
Every function like this needs a base case: the point where it stops calling itself. For the countdown, it is n == 0, where it just returns. Without one, the function calls itself again and again. Then Python hits the limit and stops the program with an error.
Each call gets its own local names. When countdown(3) calls countdown(2), the first call pauses and waits, with its own n still set to 3. Python keeps a pile of these paused calls. As each one returns, the one below it picks up where it left off.
A classic example is the factorial of a number: 4 factorial is 4 × 3 × 2 × 1, which is 24. The recursive rule is n times the factorial of n - 1, with a base case of 1. The code reads almost exactly like the maths, which is the charm of it.
Recursion shines on things that hold smaller copies of themselves. A folder holds files and more folders. Each of those holds files and more folders. A function that lists a folder can call itself on each folder inside, however deep they go.
For a plain count or a walk down a list, a loop is simpler and faster. Every call costs a little memory while it waits, and a loop does not. In Python, reach for recursion when the data is nested, and for a loop when it is flat.
The common mistake is a base case that is never reached, such as stopping at n == 0 when n goes down by 2 from 5. It jumps from 1 to -1 and keeps going. Make sure each call moves closer to the base case.
def countdown(n):
if n == 0: # base case: stop here
print("Go!")
return
print(n)
countdown(n - 1) # a smaller copy of the same job
countdown(3)
# 3
# 2
# 1
# Go!Worked example
Emma counts the files in a folder
Emma's photo folder holds 3 folders, and those hold more folders, 4 levels deep. A loop cannot know how deep to go.
She writes a function that counts the files in a folder and calls itself on each folder inside. The base case is a folder with no folders in it. It finds 1,236 photos.
The words for this lesson2
Check yourself
What happens to a recursive function with no base case?
Finished this lesson?
Marking it complete also marks its 2 glossary entries learned, which updates your roadmap and your saved page. 0 are already marked.