Fibonacci Number

Difficulty: Easy

Problem

The Fibonacci numbers, commonly denoted F(n), form a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Given n, calculate F(n). Solve it using recursion.

Example

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3. The sequence is 0, 1, 1, 2, 3.

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: If someone magically gives you F(n-1) and F(n-2), then F(n) = F(n-1) + F(n-2). That's it — trust the recursion!

Use the Leap of Faith recipe to build the recursive solution: identify the smaller problem, trust the recursive call, combine results, and add the base case.

Steps

  1. Base case: if n <= 1, return n
  2. Leap of Faith: trust that fib(n-1) and fib(n-2) return correct values
  3. Combine: return fib(n-1) + fib(n-2)

Time complexity: O(2^n) · Space complexity: O(n)