This article was originally published by the author on Medium and is republished here for wider accessibility.

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 Ruby 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: number is an integer where number ≥ 0

The Fibonacci sequence looks like this:

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

---

The Recursive Ruby Implementation

Below is a simple recursive method written in Ruby to calculate the nth Fibonacci number, where number is a non-negative integer (number ≥ 0).

# fibonacci.rb
def fibonacci(number)
if number < 2
number
else
fibonacci(number - 1) + fibonacci(number - 2)
end
end

The part that often feels mind-twisting for beginners is that the method calls itself twice:

fibonacci(number - 1) + fibonacci(number - 2)

This is exactly what recursion is: a function that keeps calling itself until a base case is reached.

---

The Base Case (Stopping Condition)

The base case in this method is:

if number < 2
number
end

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 a Tree Structure

To better understand how recursion works, it helps to visualise the method calls as a tree.

Diagram: Recursive call tree for fibonacci(n)

Each branch represents a recursive method call. The leaves of the tree are the base cases fibonacci(0) and fibonacci(1).

Example for fibonacci(2):

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

Step-by-Step: Evaluating fibonacci(2)

We start by calling:

fibonacci(2)

Since 2 is not less than 2, we enter the else branch:

fibonacci(1) + fibonacci(0)

The program now needs to evaluate both terms.

Evaluating fibonacci(1):

• number < 2 → return 1

Evaluating fibonacci(0):

• number < 2 → return 0

Now both terms have real values:

fibonacci(2) = 1 + 0 = 1

---

What’s Happening Behind the Scenes?

Each time the method calls itself:

• The current state of the method is stored in memory (the call stack)
• A new instance of the method runs with a smaller value
• Eventually, the base case (0 or 1) is reached
• The stack then unwinds, resolving each previous call

---

Example: Evaluating fibonacci(3)

From the definition of the sequence:

fibonacci(3) = fibonacci(2) + fibonacci(1)

Which becomes:

(fibonacci(1) + fibonacci(0)) + fibonacci(1) = 1 + 0 + 1 = 2

---

Key Learning Takeaway

Recursion works by breaking a problem down into smaller versions of the same problem until a simple, solvable case is reached.

---

Final Note on Performance

This recursive implementation of the Fibonacci sequence is not efficient for large values. More efficient approaches include iteration, memoisation, or dynamic programming.

However, this example is intentionally simple and is widely used in programming education because it clearly demonstrates how recursion works.

If this explanation helped you better understand recursion, then it has served its purpose.

---

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