The Wizard's Code: Finding the Nth Fibonacci Number in Three Ways

In the ancient kingdom of Numaria, where magic and mathematics intertwined, a mysterious book appeared through a glowing portal. Sam, a young scholar with an insatiable curiosity, discovered this futuristic book and learned about a fascinating sequence—the Fibonacci sequence. But how could he find the nth Fibonacci number efficiently? He sought the wisdom of Eldrin, the legendary scholar wizard who knew the secrets of the past, present, and future.

The First Method: Recursion (A Bewitching but Costly Spell)

Eldrin waved his staff, and a magical projection appeared, showing the first method—recursion. "This method follows the natural definition of the Fibonacci sequence," he explained.

function fibonacciRecursive(n) {
    if (n <= 1) return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

console.log(fibonacciRecursive(6)); // Output: 8

Sam watched as numbers split and branched endlessly like an enchanted tree. "This spell is too chaotic! Each number calls upon two more, and the calculations grow exponentially!" he protested. Eldrin nodded. "Indeed, this method has O(2^n) time complexity, making it inefficient for large numbers. We need a better way."

The Second Method: Iterative Approach (The March of Soldiers)

Eldrin then conjured another method—iteration using loops. "Instead of invoking magic recursively, we march forward step by step," he said, drawing a straight path.

function fibonacciIterative(n) {
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

console.log(fibonacciIterative(6)); // Output: 8

Sam observed, "This is better, but as numbers grow, the march becomes longer and takes more time!" Eldrin sighed. "Yes, this runs in O(n) time complexity, which is an improvement, but not the ultimate solution."

The Third Method: The Secret Formula (The Wizard’s Final Revelation)

Eldrin flipped to a hidden page in the book, revealing an ancient formula—Binet’s Formula.

function fibonacciFormula(n) {
    const sqrt5 = Math.sqrt(5);
    const phi = (1 + sqrt5) / 2;
    return Math.round((Math.pow(phi, n) - Math.pow(-phi, -n)) / sqrt5);
}

console.log(fibonacciFormula(6)); // Output: 8

Sam gasped as glowing golden symbols formed in the air. "A single formula that instantly finds any Fibonacci number?" Eldrin smiled. "Yes, this has O(1) time complexity, making it the most efficient method. It’s the true power of mathematics in programming!"

Conclusion: The Magic of Optimization

Sam learned a great lesson that day—every problem has an optimized solution, and mathematics holds the key. "Never settle for brute force," Eldrin advised. "Recognize patterns, think mathematically, and seek the best approach."

With newfound wisdom, Sam set out to apply this principle to every challenge he faced. And so, the legend of the Fibonacci Wizard spread across Numaria, inspiring generations of scholars and programmers alike.

This story highlights the importance of mathematical thinking in programming. Optimization matters! Which method do you prefer when solving problems?