Understanding Recursion using the Fibonacci Sequence (Python Edition)

The Fibonacci sequence is often one of the first mathematical concepts used to help new programmers understand recursion — a technique where a function calls itself in order to solve a problem. While recursion can feel confusing at first, the Fibonacci sequence provides a clear and visual way to see how recursive calls work and how results are built up step by step.

In this article, I explain the Fibonacci sequence and walk through a simple recursive Python implementation, using both code and a tree-style explanation. The goal is not to write the most efficient solution, but to help new coders understand what recursion is, how it behaves, and how a program unwinds recursive calls to produce a final result.

---

The Fibonacci Sequence

In mathematics, the Fibonacci sequence is defined as a sequence of numbers where:

• The first two numbers are 0 and 1
• Each subsequent number is the sum of the previous two
• The sequence is defined only for non-negative integers

For all cases discussed in this article:
index is an integer where index ≥ 0

The Fibonacci sequence looks like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

---

Recursive Fibonacci Implementation (Python)

Below is a simple recursive function written in Python to calculate the Fibonacci value at a given index.

This version also counts how many times the function is called, making the cost of recursion visible.

def fibonacci(n):
    """
    Recursive Fibonacci function.
    Returns the Fibonacci value at index n.
    """
    global call_count
    call_count += 1

    if n < 2:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

The part that often feels mind‑bending for beginners is that the function's code shows that it calls itself twice when n == 2, and more times when n > 2.

This is exactly what recursion is: a function that keeps calling itself until a base case is reached. The base case is where the recursion finally stops. This is critical, otherwise the function will never stop calling itself.

---

The Base Case (Stopping Condition)

The base case in this function is:

if n < 2:
    return n

This handles the two simplest Fibonacci values:

• fibonacci(0) = 0
• fibonacci(1) = 1

Once either of these values is reached, recursion stops for that branch.

---

Visualising Recursion with Tree Structures

To better understand recursion, it helps to visualise each function call as a tree.

Each node represents a call to fibonacci(n), and each branch represents a recursive call.

The leaves of the tree are the base cases fibonacci(0) and fibonacci(1).

fibonacci(0) and fibonacci(1)

f(0) = 0   [Base Case]
f(1) = 1   [Base Case]

fibonacci(2)

f(2) = 1
├── f(1) = 1
└── f(0) = 0

fibonacci(3)

f(3) = 2
├── f(2)
│   ├── f(1) = 1
│   └── f(0) = 0
└── f(1) = 1

fibonacci(4)

f(4) = 3
├── f(3)
│   ├── f(2)
│   │   ├── f(1) = 1
│   │   └── f(0) = 0
│   └── f(1) = 1
└── f(2)
    ├── f(1) = 1
    └── f(0) = 0

fibonacci(5)

f(5) = 5
├── f(4)
│   ├── f(3)
│   │   ├── f(2)
│   │   │   ├── f(1) = 1
│   │   │   └── f(0) = 0
│   │   └── f(1) = 1
│   └── f(2)
│       ├── f(1) = 1
│       └── f(0) = 0
└── f(3)
    ├── f(2)
    │   ├── f(1) = 1
    │   └── f(0) = 0
    └── f(1) = 1

Why fibonacci(5) Already Feels Big

Even though fibonacci(5) produces a small result (5), the tree above already contains many repeated branches.

Notice how values like fibonacci(2) and fibonacci(3) appear multiple times in different parts of the tree.

Each of these repeated branches represents extra work done by the program. As the index increases, the number of repeated calculations grows extremely fast, which is why a recursive Fibonacci implementation becomes slow much sooner than most beginners expect.

---

Thinking in “Instances” and the Call Stack

Each time a recursive call is made, the current state (or instance) of the function is stored in memory on the call stack, and a new call is evaluated.

As base cases return 0 or 1, earlier paused calls become solvable. The program then unwinds back up the call stack, combining results until the original call returns its final value.

This behaviour corresponds directly to the tree diagrams shown above.

---

Full Interactive Command-Line Program

The following is a complete Python command-prompt application.

It repeatedly asks the user which Fibonacci index to calculate, displays the result, and shows how many recursive calls were required.

def fibonacci(n):
    """
    Recursive Fibonacci function.
    Returns the Fibonacci value at index n.
    """
    global call_count
    call_count += 1

    if n < 2:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)


def main():
    global call_count

    print("Recursive Fibonacci Calculator")
    print("------------------------------")
    print("• Index must be a non-negative integer (index ≥ 0)")
    print("• Enter 'e' to exit the program")
    print("• Warning: Recursive Fibonacci is slow for large values\n")

    while True:
        print("------------------------------------------------------------------------\n")
        user_input = input("Which Fibonacci index would you like to calculate? ")

        if user_input.lower() == 'e':
            print("------------------------------------------------------------------------\n")
            print("Exiting Fibonacci calculator. Goodbye!")
            break

        try:
            index = int(user_input)

            if index < 0:
                print("Error: Index must be 0 or greater.\n")
                continue

            if index > 30:
                print("Warning: This may take a long time using recursion.\n")

            call_count = 0
            result = fibonacci(index)

            print("\nResult")
            print("------")
            print(f"Fibonacci({index}) = {result}")
            print(f"Total calls made to the Fibonacci function: {call_count}\n")

        except ValueError:
            print("Error: Please enter a valid integer or 'e' to exit.\n")


if __name__ == "__main__":
    main()

---

Sample Command-Line Run

The output below shows how quickly the number of recursive calls grows, even for relatively small Fibonacci indexes:

Fibonacci(0)  -> 1 call
Fibonacci(1)  -> 1 call
Fibonacci(2)  -> 3 calls
Fibonacci(5)  -> 15 calls
Fibonacci(10) -> 177 calls
Fibonacci(20) -> 21891 calls
Fibonacci(30) -> 2692537 calls

This dramatic growth directly reflects the branching structure seen in the recursion trees above.

Written by Bennie van der Merwe — electronic and software engineer.