Memoization to Optimize Recursion in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of recursion?

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does memoization improve the performance of recursive functions?

It saves the results of recursive calls in a cache (like an array or dictionary) so that each unique call is computed only once, reducing time complexity from exponential to linear in many cases.

intermediate

In C, what data structure is commonly used to implement memoization for recursion?

An array or a hash table (if keys are not simple integers) is commonly used to store computed results for memoization in C.

intermediate

What is the difference between memoization and dynamic programming?

Memoization is a top-down approach that caches results of recursive calls, while dynamic programming is often a bottom-up approach that builds solutions iteratively. Both avoid repeated work but differ in implementation style.

beginner

Why is memoization especially useful in problems like Fibonacci sequence calculation?

Because naive recursion recalculates the same Fibonacci numbers many times, memoization stores these results once computed, drastically reducing the number of calls and improving efficiency.

What does memoization store to optimize recursion?

A Previously computed results

B Input parameters only

C Function call stack

D Random values

Memoization stores previously computed results to avoid recalculating them.

Which data structure is commonly used for memoization in C when inputs are integers?

A Linked list

B Queue

C Stack

D Array

Arrays are commonly used to store memoized results indexed by integer inputs.

Memoization changes the time complexity of naive Fibonacci recursion from exponential to what?

A Quadratic

B Linear

C Logarithmic

D Constant

Memoization reduces Fibonacci recursion time complexity to linear by caching results.

Memoization is an example of which programming technique?

A Greedy algorithm

B Bottom-up dynamic programming

C Top-down dynamic programming

D Divide and conquer without caching

Memoization is a top-down approach that caches recursive calls.

What happens if memoization is not used in recursive functions with overlapping subproblems?

A The function recalculates the same results multiple times

B The function runs faster

C The function uses less memory

D The function never terminates

Without memoization, recursive functions with overlapping subproblems recompute results repeatedly.

Explain how memoization optimizes a recursive function using the Fibonacci sequence as an example.

Think about how many times the same Fibonacci number is calculated without memoization.

Describe the steps to implement memoization in a recursive C function.

Focus on how to avoid repeated work by checking and storing results.