Fibonacci Sequence

Problem Statement

Generate the nth number in the Fibonacci sequence, where each number is the sum of the two preceding ones, starting with 0 and 1 (i.e., 0, 1, 1, 2, 3, 5, 8, ...). This easy-level problem is a recursion classic, defined as F(n) = F(n-1) + F(n-2), with base cases F(0) = 0 and F(1) = 1. It’s a beautiful way to see recursion in action, though it can get slow for large n—perfect for learning optimization later!

Example

Input: n = 0

Output: 0 (first number in sequence)

Input: n = 4

Output: 3 (sequence: 0, 1, 1, 2, 3)

Input: n = 6

Output: 8 (sequence: 0, 1, 1, 2, 3, 5, 8)

Code

public class Solution {
    public int fibonacci(int n) {
        if (n < 0) return -1; // Invalid input
        if (n == 0) return 0; // Base case 1
        if (n == 1) return 1; // Base case 2
        return fibonacci(n - 1) + fibonacci(n - 2); // Recursive step
    }
}
            

def fibonacci(n):
    if n < 0:
        return -1  # Invalid input
    if n == 0:
        return 0   # Base case 1
    if n == 1:
        return 1   # Base case 2
    return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive step

# Example usage
print(fibonacci(0))  # 0
print(fibonacci(4))  # 3
print(fibonacci(6))  # 8
            

function fibonacci(n) {
    if (n < 0) return -1; // Invalid input
    if (n === 0) return 0; // Base case 1
    if (n === 1) return 1; // Base case 2
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursive step
}

// Example usage
console.log(fibonacci(0)); // 0
console.log(fibonacci(4)); // 3
console.log(fibonacci(6)); // 8
            

Explanation

• Base Cases: F(0) = 0 and F(1) = 1 define the sequence’s start.
• Recursive Case: F(n) = F(n-1) + F(n-2), summing the previous two numbers.
• Flow Example (n=4): fibonacci(4) → fibonacci(3) + fibonacci(2) → [fibonacci(2) + fibonacci(1)] + [fibonacci(1) + fibonacci(0)] → [1 + 1] + [1 + 0] → 2 + 1 → 3.
• Tree Growth: Each call branches into two more, forming a binary tree of calls.
• Caution: This naive recursion repeats calculations (e.g., fibonacci(2) is computed multiple times), making it inefficient for large n.

Note