Skip to content
BENIBIX Learn

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

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.

python
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!
Each call handles one number. It hands a smaller job to the next call, until the base case stops it.
The left side is recursion: each call is smaller, and the base case is where the chain stops.

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.