🎓 A1Learner
🔍

Python Recursion

Recursion is a function calling itself. Each call works on a smaller piece of the job.

A function that calls itself

sum_to(4) adds 4 plus sum_to(3). The calls keep shrinking the number.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)


print(sum_to(4))

The base case stops it

When n reaches 0, the function returns 1 at once. It makes no new call there.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)


print(factorial(4))

A countdown that calls itself

Each call prints one number. Then it calls itself with a smaller number.

def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)


countdown(3)

Example

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)


def countdown(n):
    if n == 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)


print(factorial(5))
countdown(3)

Key points

  • Recursion: a function calling itself
  • Base case: the simple case that stops the calls
  • Each call gets its own copy of the variables
  • Call stack: the pile of calls that are still waiting to finish
  • Too many calls raise RecursionError.
  • Python sets a limit on how deep the calls may go.

In this example, factorial(5) calls itself with smaller numbers each time. The base case returns 1 when n reaches 0. The waiting calls then multiply 5 by 4 by 3 by 2 by 1, which gives 120. Next, countdown(3) prints 3 and calls itself with 2. The calls print 2 and 1 in the same way. At 0, the base case prints Go! and the calls stop.

Note

A loop solves many of these jobs with less risk.

Use recursion when the job clearly splits into smaller copies of itself.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Why does every recursive function need a base case?