Fibonacci Number

Easy· recursion· memoization

Problem

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1, and every later term is the sum of the two before it. Given n, return F(n). It is the classic first exercise in thinking recursively.

Examples

Input: n = 4

Output: 3

The sequence runs 0, 1, 1, 2, 3.

Input: n = 6

Output: 8

Constraints

• 0 <= n <= 30

Hints & approach

Hint 1

Write the definition directly as a function that calls itself, with two base cases.

Hint 2

Draw the call tree for n = 5. Which calls repeat?

Hint 3

Cache results, or just carry the last two values forward in a loop.

Approachtry the hints first

The recursive definition fib(n) = fib(n - 1) + fib(n - 2) with base cases 0 and 1 is correct but recomputes the same subproblems exponentially many times. Memoising each result brings it down to O(n). Since each term only depends on the previous two, you can go further and iterate with two variables, rolling them forward n times. This problem is the bridge from plain recursion to thinking about overlapping subproblems.

Time O(n) · Space O(1) iterative

Next →Subsets