Recursion Basics

Recursion: lesson 1 of 5

A function that solves a smaller copy of itself.

Lesson 1 of 5 · 5 min

Step 1 of 9

depth0base casen == 0

frames alive

printed

A recursive function needs two parts: a base case that answers directly, and a step that makes the problem smaller.

The Idea

A recursive function solves a problem by calling itself on a smaller version of the same problem. Two parts are non-negotiable: a base case that answers directly, and a recursive case that shrinks the input toward it. Miss either one and the calls never stop.

Real-World Example

A support desk escalation. The agent who cannot answer forwards your ticket one level up, and so does the next person, until somebody finally knows. That answer then travels back down the same chain to you.

The Code

def countdown(n):
    if n == 0:              # base case: answer directly
        print("liftoff")
        return
    print(n)
    countdown(n - 1)        # recursive case: smaller problem

countdown(3)
# 3
# 2
# 1
# liftoff

Your turn

What does this print?

def countdown(n):
  if n == 0:
      print("go")
      return
  print(n)
  countdown(n - 1)

countdown(2)

Mini quiz

1 / 3

Recursion Basics