Memoization to Optimize Recursion in DSA C - Build from Scratch

Memoization to Optimize Recursion

📖 Scenario: You are working on a program that calculates Fibonacci numbers. The Fibonacci sequence is a series where each number is the sum of the two before it, starting with 0 and 1.Calculating Fibonacci numbers using simple recursion can be very slow because it repeats the same calculations many times. To make it faster, you will use memoization, which means saving results of calculations so you don't repeat them.

🎯 Goal: Build a C program that uses memoization to optimize the recursive calculation of Fibonacci numbers. You will create a function that remembers past results to avoid repeated work.

📋 What You'll Learn

Create an integer array called memo to store results of Fibonacci calculations.

Create a recursive function called fib that takes an integer n and returns the nth Fibonacci number.

Use memoization inside the fib function to save and reuse results.

Print the Fibonacci number for n = 10.

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world applications like caching web pages, optimizing game AI, and speeding up complex calculations.

💼 Career

Understanding memoization helps in writing efficient code, a key skill for software developers, especially in roles involving algorithms and performance optimization.

1

Create the memo array

Create an integer array called memo of size 11 and initialize all elements to -1.

DSA C

#include 

// Create an integer array called memo of size 11 and initialize all elements to -1
// Your code here

Hint

Use int memo[11] = { -1, -1, ..., -1 }; to create and initialize the array.

2

Create the fib function header

Create a recursive function called fib that takes an integer parameter n and returns an integer.

DSA C

#include 

int memo[11] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

// Create the fib function header
int fib(int n) {
    // Your code here
}

Hint

Write int fib(int n) to start the function.

3

Implement memoization in fib function

Inside the fib function, add these steps:
1. If n is 0, return 0.
2. If n is 1, return 1.
3. If memo[n] is not -1, return memo[n].
4. Otherwise, calculate fib(n-1) + fib(n-2), store it in memo[n], and return memo[n].

DSA C

#include 

int memo[11] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

int fib(int n) {
    // Add base cases and memoization logic here
    // Your code here
}

Hint

Use if statements for base cases and check memo[n] before recursive calls.

4

Print the Fibonacci number for n = 10

In the main function, call fib(10) and print the result using printf.

DSA C

#include 

int memo[11] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

int fib(int n) {
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (memo[n] != -1) {
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    // Call fib(10) and print the result
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", fib(10)); or store in a variable first.