Creating a Fibonacci Service in Spring Boot

In this tutorial, we will build a simple Fibonacci service using Spring Boot. The service calculates Fibonacci numbers based on the index provided by the user. This example is intentionally designed using a recursive algorithm to demonstrate performance challenges and the need for optimization later (e.g., caching).

1. Understanding Fibonacci Sequence

The Fibonacci sequence is defined as:

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2) for n >= 2

Example sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

As the index increases (e.g., index 40+), the Fibonacci numbers grow quickly, and a naive recursive algorithm can become exponentially slow.

2. Project Structure

We will create the following structure under the Spring Boot project:

src/main/java/com/example/fib/
    ├── service/
    │     └── FibonacciService.java
    └── controller/
          └── FibonacciController.java

service: Contains the business logic for Fibonacci calculation.
controller: Exposes a REST API to retrieve Fibonacci numbers by index.

3. Creating the Fibonacci Service

Create a service class to calculate Fibonacci numbers:

package com.example.fib.service;

import org.springframework.stereotype.Service;

@Service
public class FibonacciService {

    // Public method to calculate Fibonacci number for a given index
    public long getFibonacci(int index) {
        return calculateFibonacci(index);
    }

    // Recursive method (intentionally inefficient for demonstration)
    private long calculateFibonacci(int index) {
        if (index < 2) {
            return index; // Base case: Fib(0) = 0, Fib(1) = 1
        }
        return calculateFibonacci(index - 1) + calculateFibonacci(index - 2);
    }
}

Notes:

The recursive algorithm has exponential time complexity (O(2^n)), making it slow for large indices.
This is intentional to simulate computationally heavy operations.

4. Creating the Fibonacci Controller

Create a REST controller to expose the Fibonacci service:

package com.example.fib.controller;

import com.example.fib.service.FibonacciService;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;

@RestController
@RequestMapping("/fib")
public class FibonacciController {

    @Autowired
    private FibonacciService fibonacciService;

    @GetMapping("/{index}")
    public long getFibonacci(@PathVariable int index) {
        return fibonacciService.getFibonacci(index);
    }
}

Endpoint: GET /fib/{index}
The controller takes an index as a path variable and returns the corresponding Fibonacci number.

5. Running the Application

Start the Spring Boot application.
Access the API using a browser or Postman:

http://localhost:8080/fib/5   -> 5
http://localhost:8080/fib/10  -> 55
http://localhost:8080/fib/30  -> 832040

Smaller indices return almost instantly.
Larger indices (e.g., 40+) may take several seconds due to the recursive computation.
Very large indices may never complete because of exponential complexity.

6. Observations

The naive recursive Fibonacci implementation is intentionally slow to simulate heavy computational load.
This setup demonstrates a real-world scenario where frequent requests for heavy computations can overwhelm the server.
To handle performance bottlenecks:
- Introduce caching (e.g., Redis, in-memory cache)
- Use dynamic programming or iterative approaches to reduce computation time

7. Next Steps

Optimize the Fibonacci calculation using memoization or iterative approach.
Integrate caching mechanisms (like Redis) to store previously calculated Fibonacci numbers and improve performance for repeated requests.
Extend the service to handle multiple concurrent requests efficiently.