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

1. Start the Spring Boot application.
2. 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.