A Guide to Fibonacci Series and Recursion in Go Language

The Fibonacci sequence is one of the most common problems you'll solve throughout your software career. Its implementation can be as simple or complex as you want.

One of the most frequently used solutions is recursion—a core concept in computer science. Whether you're learning computer science, preparing for your next interview, or simply reinforcing old concepts, join me in writing a Fibonacci sequence using recursion with Go.

What is recursion?

Recursion means breaking a problem into smaller subproblems. Sometimes you'll add or remove something f(n), or you'll need to adjust the solution f(n - 1). In some cases, you might solve the problem for half of the dataset.

In the Fibonacci sequence, the function calls itself with smaller inputs. Each recursive call works toward the base case.

Problem Statement

Given n calculate the nth Fibonacci number.

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting with 0 and 1. The sequence begins as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Breaking it down:

• Input: an integer where the series will stop.

• Output: the sequence from 0 to n.

Now that we've identified the input, output, and approach, it's time to implement it.

Algorithm

First, since the function calls itself, I need to prevent infinite loops. To do this, I define a base case—a condition that tells the function when to stop.

if n <= 1 {
    return n
}

Every recursive function consists of two parts: the base case (when to stop) and the recursive case (when to call itself). I've already defined the base case. Now it's time to declare the recursive case. For Fibonacci, I need to call the function twice with smaller inputs—specifically n - 1 and n - 2.

return fibonacci(n-1) + fibonacci(n-2)

You might be asking: "Why does it call itself twice?" Good question. Each number is the sum of the two preceding ones.

The Fibonacci function is mathematically defined as: F(n) = F(n-1) + F(n-2) for n > 1. 1

So to compute F(4), you need:

• F(3) (which needs F(2) and F(1))

• F(2) (which needs F(1) and F(0))

Easy, right? And there you have it—you've solved the Fibonacci sequence using recursion. But I'm afraid to say it's the worst solution.

Visual example

Why learn something that's a bad solution? Well, because it's the core concept for complex solutions like dynamic programming or memoization. If you're a React programmer, you've used memoization plenty of times with the useMemo or useCallback hooks. So that's why you need to learn recursion first.

An example will make this clearer. Let's find the Fibonacci sequence for the number 4.

Let's trace through the recursion step by step:

1. F(4) calls F(3) and F(2)

2. F(3) calls F(2) and F(1)

* `F(2)` calls `F(1)` and `F(0)`

* `F(1)` returns 1 (base case)

* `F(0)` returns 0 (base case)

* So `F(2) = 1 + 0 = 1`

* `F(1)` returns 1 (base case)

* So `F(3) = 1 + 1 = 2`

1. F(2) calls F(1) and F(0)

* `F(1)` returns 1 (base case)

* `F(0)` returns 0 (base case)

* So `F(2) = 1 + 0 = 1`

1. Final result: F(4) = 2 + 1 = 3

Notice how F(2) is calculated twice and F(1) is calculated three times. This redundancy is why the naive recursive solution is inefficient—it has exponential time complexity of O(2ⁿ). For larger values of n, the same calculations are repeated thousands or even millions of times.

This is exactly why we need optimization techniques like memoization or dynamic programming, which store previously calculated values to avoid redundant work.

Final Thougths

Recursion is best used when it makes the solution clearer. When you call a function from another function, the calling function pauses in a partially completed state. Imagine what this does to memory.

Despite its drawbacks, recursion powers many important algorithms, so it's worth understanding how it works.

If you want to dive deeper or practice, try other exercises like factorial or the Tower of Hanoi. Happy coding, and I'll see you in the next one!

Comments

[Fred Brooker]

The Fibonacci sequence is one of the most common problems you'll solve throughout your software career.

😂

no 😏 I'm a programmer for 40 years and never had a use case to solve Fibonacci - if we talk about recursion, there's plenty of useful cases - count files, count directories, convert all the files into mp3, fix diacritics in filenames etc... 🙄

[Dan Jones]

Fibonacci is one of those things that's useful for teaching how recursion works, but actually a terrible use case for recursion.

A loop makes it O(n), instead of O(n^2)