---
title: Recursion in Python
source: https://app.sythra.ai/learn/python/recursion-in-python
topic: Python
updated: 2026-08-12
publisher: Sythra (https://app.sythra.ai)
---

# Recursion in Python

Recursion in Python is a function calling itself to solve smaller versions of the same problem, always stopping at a base case. Classic examples are factorial (n! = n × (n-1)!) and Fibonacci (fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)).

_Source: [https://app.sythra.ai/learn/python/recursion-in-python](https://app.sythra.ai/learn/python/recursion-in-python) — free to read on Sythra._

## Key points

- Every recursive function needs a base case that stops the calls
- Each recursive call gets its own independent stack frame with its own local variables
- The leap of faith: trust that a recursive call on a smaller input returns the correct answer
- Forgetting the base case causes a RecursionError after Python's default 1000-call limit
- Guard recursive functions against invalid input with isinstance() before recursing

Here is an idea that sounds strange at first: a function is allowed to call _itself_. This is called **recursion in Python**, and it is one of the most elegant ideas in all of programming — used for anything that naturally breaks into smaller versions of itself, like tree structures and mathematical sequences.

## What you will learn

- How a function calling itself actually works, step by step
- The **base case** — what stops recursion from running forever
- How to trace the classic `factorial()` and `fibonacci()` examples
- The **leap of faith** — the right way to think about recursive calls
- Guarding a recursive function against bad input
- What happens when you forget the base case: `RecursionError`

## A first example: counting down

```python
def countdown(n):
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n - 1)
```

Call it with `countdown(3)` and here is what happens, step by step:

- `countdown(3)` — is 3 ≤ 0? No. Prints `3`, then calls `countdown(2)`.
- `countdown(2)` — is 2 ≤ 0? No. Prints `2`, then calls `countdown(1)`.
- `countdown(1)` — is 1 ≤ 0? No. Prints `1`, then calls `countdown(0)`.
- `countdown(0)` — is 0 ≤ 0? Yes! Prints `'Blastoff!'` and stops.

```python
# Output:
3
2
1
Blastoff!
```

Each call to `countdown` creates a smaller version of the same problem. The function keeps going until it reaches the stopping condition — called the **base case**. The base case is what prevents the function from calling itself forever.

> **When to reach for recursion:** 

## Stack diagrams for recursive functions

Each time a function is called, Python creates a **frame** — a little box holding that function's local variables. Recursion creates a more dramatic version of this: every time a function calls _itself_, Python creates a brand new frame on the stack, completely separate from the others.

For `countdown(3)`, the stack looks like this at its deepest point, just before `countdown(0)` prints "Blastoff!":

```text
__main__
countdown   n = 3
countdown   n = 2
countdown   n = 1
countdown   n = 0   <- base case
```

Each frame is completely independent — the `n` inside `countdown(3)` has no connection to the `n` inside `countdown(2)`; they are separate boxes, just with the same label inside them. When the base case runs and returns, the frames start collapsing from the bottom upward: `countdown(0)` finishes and disappears, `countdown(1)` picks up where it left off, then `countdown(2)`, then `countdown(3)`, until control returns to `__main__`. This collapsing is why recursive functions actually _finish_.

## The factorial function: recursion that returns a value

Factorial has a mathematical definition that refers to itself: `0! = 1`, and `n! = n × (n-1)!`. So `3! = 3 × 2! = 3 × 2 × 1! = 3 × 2 × 1 × 0! = 3 × 2 × 1 × 1 = 6`. This maps almost directly into Python:

```python
def factorial(n):
    if n == 0:
        return 1
    else:
        recurse = factorial(n - 1)
        result = n * recurse
        return result
```

Trace through `factorial(3)`: it needs `factorial(2)`, which needs `factorial(1)`, which needs `factorial(0)`, which returns `1` (the base case). Then the results flow back up: `1 × 1 = 1`, then `2 × 1 = 2`, then `3 × 2 = 6`.

## The leap of faith: trusting your own functions

Tracing through recursive calls in your head gets overwhelming fast. There is a better way to think about it — the **leap of faith**.

When you call `math.sqrt()`, you do not dig into its source code to verify it works — you just trust it. Apply the same thinking to your own functions. When you write `factorial(n)` and it calls `factorial(n-1)`, do not follow the chain — just ask: _if I assume `factorial(n-1)` gives the correct answer, can I compute `factorial(n)` from it?_ If yes — multiply by `n` — then your logic is correct. Trust the function to handle the rest. This is not laziness; it is the right mental model for recursive code. Trying to trace every call is what makes your head explode.

## Fibonacci: recursion with two calls

The Fibonacci sequence is defined as `fibonacci(0) = 0`, `fibonacci(1) = 1`, and `fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)`:

```python
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
```

This function makes _two_ recursive calls, so the call tree branches instead of forming a straight chain. Trying to trace it manually for even moderate values of `n` is impractical — the leap of faith is especially important here: assume both recursive calls return correct results, and the logic becomes obvious: add them together.

## Guarding against bad input

What happens if you call `factorial(1.5)`?

```python
factorial(1.5)   # RecursionError: maximum recursion depth exceeded
```

The base case checks for `n == 0`, but `1.5` never hits zero — it goes `0.5`, `-0.5`, `-1.5`... forever. The fix is to guard against bad input at the start of the function using `isinstance()`:

```python
def factorial(n):
    if not isinstance(n, int):
        print('Factorial is only defined for integers.')
        return None
    elif n < 0:
        print('Factorial is not defined for negative integers.')
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial(n - 1)
```

```python
factorial('fred')   # Factorial is only defined for integers.
factorial(-2)        # Factorial is not defined for negative integers.
factorial(5)         # 120
```

The first two conditions are called **guardians** — they intercept invalid inputs before the real logic runs. Guardians are a clean pattern for making functions robust without complicating the core logic.

## Infinite recursion: what happens when you forget the base case

If a recursive function never reaches its base case, it calls itself forever — or rather, it _tries_ to. Python has a built-in safety limit of 1000 recursive calls; after that, it stops the program and throws an error:

```python
def recurse():
    recurse()    # no base case — will call itself forever
```

```python
# RecursionError: maximum recursion depth exceeded
```

The error message Python gives you has a traceback hundreds of lines long, all showing the same function calling itself over and over. If you ever see this, the fix is always the same: find your base case, make sure it is there, and make sure every recursive call is actually _moving toward it_.

> **Two questions to ask every recursive function:** 

## Common mistakes

- Forgetting the base case entirely, causing a `RecursionError`
- Writing a base case that the recursive calls never actually reach (like checking for exactly 0 when the input can be a float)
- Trying to trace every single call in your head instead of trusting the leap of faith
- Using recursion for simple repetition where a `for` loop would be clearer
- Forgetting to guard against invalid input types before recursing

> **Practice with Sythra:**  [Practice with AI tutor](https://app.sythra.ai/pricing)

## FAQ

### What is recursion in Python?

Recursion is when a function calls itself to solve a smaller version of the same problem, continuing until it reaches a base case that stops the chain of calls.

### What is a base case in recursion?

A base case is the condition that stops a recursive function from calling itself further, such as n == 0 in a factorial function. Without one, the function recurses forever until Python raises a RecursionError.

### What is the leap of faith in recursion?

The leap of faith means trusting that a recursive call correctly solves a smaller version of the problem, without mentally tracing every single call. You only need to verify that your function is correct assuming the recursive call already works.

### Why does factorial(1.5) cause a RecursionError?

The base case checks for n == 0, but repeatedly subtracting 1 from 1.5 never lands exactly on 0 — it goes 0.5, -0.5, -1.5, forever — so the base case is never reached and Python eventually raises RecursionError.

### Should I use recursion or a loop in Python?

For simple repetition, a for or while loop is usually clearer and faster. Recursion shines for problems that naturally break into smaller versions of themselves, like tree traversal or mathematical sequences defined recursively.

## Related

- [Conditionals in Python (if, elif, else)](https://app.sythra.ai/learn/python/conditionals-in-python) — The if/else logic every base case depends on.
- [Fruitful Functions in Python](https://app.sythra.ai/learn/python/fruitful-functions-python) — Return values — what recursive calls actually hand back.
- [Functions in Python in Depth](https://app.sythra.ai/learn/python/python-functions-in-depth) — Default arguments, *args, **kwargs, lambdas, and scope.
- [Python course hub](https://app.sythra.ai/learn/python) — All free Python explainers and the path into Agentic practice.
- [The while Loop in Python](https://app.sythra.ai/learn/python/while-loop-python) — Condition-based repetition, break, and infinite loop traps.

---

Written by Sythra — Learn machine learning by building. Practice this topic with Sythra's AI tutor: https://app.sythra.ai/pricing