Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Problem: Fibonacci Number

Explore how to implement the Fibonacci number sequence using recursion combined with memoization to avoid redundant calculations. Understand the transformation of exponential to linear time complexity and the use of a memo dictionary to cache results. This lesson helps you grasp recursion optimization techniques and analyze time and space complexity in Python solutions.

We'll cover the following...

Statement

The Fibonacci numbers, commonly denoted F(n), form a sequence known as the Fibonacci sequence. Each number in the sequence is the sum of the two preceding ones, starting from 00 and 11. The sequence is defined as follows:

Examples

canvasAnimation-image
1 / 3

Try it yourself!

Implement your solution in the following coding playground.

Python
usercode > Solution.py
def fib(n):
    # Replace this placeholder return statement with your code
    return -1
Fibonacci Number

Solution

The core idea behind this solution is to use recursion with memoization to compute the Fibonacci number F(n). The Fibonacci sequence is naturally defined by a recurrence relation, making recursion an intuitive approach. However, naive recursion leads to redundant computations because the same subproblems are solved multiple times. To eliminate this inefficiency, we use a memo dictionary to cache previously computed results. Before making any recursive call, we first check if the result for a given n already exists in memo. If it does, we return the cached value immediately, avoiding repeated work. This transforms the exponential time complexity of naive recursion into a linear one, since each Fibonacci number from 00 ...