FunctionsIntermediate⏱ 8 min38 / 63

Recursion

Learn how a function can call itself to solve problems elegantly, and discover the two essential rules that keep it from running forever.

Imagine you are looking for your keys. You check your coat pocket. Inside your coat pocket, you find another coat. So you check that pocket. Inside that pocket, you find yet another coat... and so on. That is recursion in a nutshell: a problem that contains a smaller version of itself.

In Python, recursion means writing a function that calls itself. It sounds strange at first, but it is a powerful way to solve problems that naturally repeat in smaller and smaller steps.

See it in action

Visual walkthrough1 / 6
1

A Function That Calls Itself

Recursion is when a function calls itself to solve a problem. Think of nesting dolls — each one contains a smaller version of the same thing, all the way down to the tiniest doll.

Recursion isn't magic — it's just a function calling itself with a simpler input each time.

#The Two Rules of Recursion

Every recursive function needs exactly two parts to work safely:

  • Base case — the stopping condition. When this is true, the function stops calling itself and returns a direct answer.
  • Recursive case — the function calls itself with a simpler or smaller input, moving toward the base case.

Without a base case, a recursive function will call itself forever — just like those coats-inside-coats with no end.

Think of it like

Russian Nesting Dolls

Think of recursion like Matryoshka dolls. Each doll contains a smaller doll inside. You keep opening them until you reach the tiniest doll — that is the base case. Then you are done.

#Your First Recursive Function: Countdown

Let's start with something simple. We want to count down from a number to zero, printing each number. We could do this with a loop, but let's do it recursively to see the pattern.

Each call to countdown() passes a smaller number until we hit zero.
def countdown(n):
    if n <= 0:          # base case: stop here
        print("Blast off!")
    else:               # recursive case: print and go smaller
        print(n)
        countdown(n - 1)

countdown(5)

Notice the pattern:

  • if n <= 0 is the base case — it stops the chain.
  • countdown(n - 1) is the recursive case — it calls itself with n one step smaller.

Each call is a little closer to the stopping point.

#Classic Example: Factorial

The factorial of a number is that number multiplied by every positive integer below it. For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

This is a perfect fit for recursion because 5! = 5 × 4!, and 4! = 4 × 3!, and so on — each step is a smaller version of the same problem.

factorial(5) breaks down into 5 * factorial(4), and so on, until it reaches 1.
def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    else:                  # recursive case
        return n * factorial(n - 1)

print(factorial(5))
print(factorial(1))
print(factorial(0))

#How the Call Stack Works

When Python runs a function, it keeps track of it on something called the call stack — imagine a stack of plates. Each function call adds a plate on top. When a function returns, its plate is removed.

With factorial(3), here is what happens step by step:

The calls build up (wind), then each returns its result back up the chain (unwind).
# Tracing factorial(3) mentally:
#
# factorial(3) --> 3 * factorial(2)
#                       factorial(2) --> 2 * factorial(1)
#                                             factorial(1) --> 1  (base case!)
#                                        returns 2 * 1 = 2
#                  returns 3 * 2 = 6

print(factorial(3))  # prints 6

First the calls build up (each one waits for the next). Then, once the base case is reached, the answers bubble back up through each waiting call. This build-and-unwind behavior is what makes recursion feel like magic.

#Infinite Recursion: The Danger Zone

Common mistake

Forgetting the Base Case = Infinite Loop

If your function never reaches a base case, it will keep calling itself forever — until Python gives up and raises a RecursionError. This is called infinite recursion.

``python # BROKEN: no base case! def oops(n): return n * oops(n - 1) # never stops ``

Always make sure your recursive case moves toward the base case.

#Python's Recursion Limit

Python sets a built-in safety limit: by default, functions can only call themselves about 1000 times before Python raises a RecursionError. This protects your computer's memory from runaway recursion.

You can check the limit with sys.getrecursionlimit(). You can raise it, but rarely need to.
import sys

print(sys.getrecursionlimit())
Tip

If you hit the limit, rethink your approach

Hitting Python's recursion limit usually means either your base case is wrong, or the problem is better solved with a loop. Most real-world Python code uses iteration (loops) for deep repetition, and recursion for elegant solutions on smaller inputs like trees and nested structures.

#Recursion vs. Iteration

Recursion and loops can often solve the same problem. Here is the same factorial in both styles:

Both give the same answer. The recursive version is often shorter and closer to the math definition.
# Iterative version (using a loop)
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive version
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

print(factorial_loop(5))      # 120
print(factorial_recursive(5)) # 120

When to use recursion: - The problem naturally breaks into smaller versions of itself (trees, nested folders, fractals). - The recursive solution is much cleaner and easier to read.

When to use a loop instead: - The recursion depth could be very large (thousands of steps). - Performance is critical — function calls have a small overhead.

Quick check

What happens if a recursive function has no base case?

Key takeaways

  • A recursive function calls itself to solve a smaller version of the same problem.
  • Every recursive function needs a **base case** (when to stop) and a **recursive case** (how to get smaller).
  • The call stack builds up as calls are made, then unwinds as each one returns its result.
  • Python enforces a recursion limit (~1000 calls) to prevent infinite recursion from crashing your program.
  • Use recursion when the problem is naturally self-similar; prefer loops when depth might be large.
Try it yourself · Call-stack stepper
Watch the calls stack up, then unwind as each one returns.
factorial()
step 1 / 9
factorial(4)

factorial(4) is called — it must wait for factorial(3)

Practice challenges
Test yourself · earn XP
0/4
Predict the output#1

What does this code print?

predict-output
def countdown(n):
    if n <= 0:
        print("Blast off!")
    else:
        print(n)
        countdown(n - 1)

countdown(3)
Fix the bug#2

This recursive factorial function has a bug. What is wrong?

fix-bug
def factorial(n):
    return n * factorial(n - 1)

print(factorial(4))
Fill in the blank#3

Complete the recursive function so that sum_down(3) returns 6 (3 + 2 + 1).

def sum_down(n):
    if n == :
        return 1
    return n + sum_down()

print(sum_down(3))  # 6
Reorder the lines#4

Put these lines in the right order to define and call a recursive function that prints numbers from 1 up to n.

1
    count_up(n, current + 1)
2
        return
3
count_up(3)
4
    if current > n:
5
def count_up(n, current=1):
6
    print(current)
Your turn
Practice exercise

Write a recursive function called sum_down(n) that takes a positive integer n and returns the sum of all integers from n down to 1. For example, sum_down(4) should return 10 (because 4 + 3 + 2 + 1 = 10). Do NOT use a loop — use recursion!

Try it live — edit the code and hit Run to execute real Python:

solution.py · editable