Why Dynamic Programming and When Recursion Alone Fails in DSA C - Quick Recap

Recall & Review

beginner

What is the main problem with using plain recursion for some problems?

Plain recursion often recalculates the same subproblems multiple times, leading to a lot of repeated work and slow performance.

beginner

What does Dynamic Programming (DP) do differently compared to plain recursion?

DP saves the results of subproblems so they can be reused later, avoiding repeated calculations and making the solution faster.

intermediate

Why is overlapping subproblems important for using Dynamic Programming?

Overlapping subproblems mean the same smaller problems appear many times. DP works well here by storing answers to these problems once and reusing them.

beginner

What is 'memoization' in the context of Dynamic Programming?

Memoization is a technique where we store the results of recursive calls in a table (like an array) so we don't compute them again.

beginner

Give an example of a problem where recursion alone is inefficient but Dynamic Programming helps.

Calculating Fibonacci numbers using plain recursion is slow because it repeats work. Using DP with memoization or tabulation makes it fast.

Why does plain recursion often lead to slow solutions?

A It recalculates the same subproblems multiple times

B It uses too much memory

C It never reaches the base case

D It only works for small inputs

Plain recursion repeats calculations for the same subproblems, causing slow performance.

What is the main benefit of Dynamic Programming?

A It always uses less memory

B It uses more recursion

C It ignores base cases

D It stores results of subproblems to avoid repeated work

DP saves subproblem results to reuse them, speeding up the solution.

Which condition makes a problem suitable for Dynamic Programming?

A No base case

B No recursion needed

C Overlapping subproblems and optimal substructure

D Only one subproblem

DP works well when subproblems overlap and the problem has optimal substructure.

What is memoization?

A Ignoring repeated calculations

B Storing results of recursive calls to reuse later

C Calling functions repeatedly

D Using loops instead of recursion

Memoization saves results of recursive calls to avoid recalculating them.

Which problem is a classic example where DP improves over recursion?

A Fibonacci number calculation

B Sorting an array

C Finding maximum in an array

D Printing numbers from 1 to n

Fibonacci calculation with recursion repeats work; DP speeds it up by storing results.

Explain why recursion alone can be inefficient and how Dynamic Programming solves this problem.

Think about how many times the same small problem is solved in recursion.

Describe the role of memoization in Dynamic Programming and how it differs from plain recursion.

Focus on storing and reusing answers.