Why Dynamic Programming and When Recursion Alone Fails in DSA Rust - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA Rust

fn fib(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }
    fib(n [1] 1u32) + fib(n [1] 2u32)
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in the recursive calls.

Using multiplication or division which does not fit the Fibonacci definition.

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2). The code uses subtraction to get the previous two numbers.

2fill in blank

medium

Complete the code to add memoization to the Fibonacci function to avoid repeated calculations.

DSA Rust

use std::collections::HashMap;

fn fib_memo(n: u32, memo: &mut HashMap<u32, u32>) -> u32 {
    if n <= 1 {
        return n;
    }
    if memo.contains_key(&n) {
        return *memo.get(&n).unwrap();
    }
    let result = fib_memo(n [1] 1u32, memo) + fib_memo(n [1] 2u32, memo);
    memo.insert(n, result);
    result
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of subtraction in recursive calls.

Not checking or inserting into the memo HashMap.

Memoization stores results of fib(n-1) and fib(n-2) to avoid repeated work. The recursive calls reduce n by 1 and 2 using subtraction.

3fill in blank

hard

Fix the error in the recursive Fibonacci function that causes exponential time complexity.

DSA Rust

fn fib(n: u32) -> u32 {
    if n <= 1 {
        return n;
    }
    let a = fib(n [1] 1u32);
    let b = fib(n [1] 2u32);
    a + b
}

Drag options to blanks, or click blank then click option'

A+

B/

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction in recursive calls.

Not returning base cases correctly.

The recursive calls must subtract 1 and 2 from n to get previous Fibonacci numbers. Using addition causes infinite recursion and wrong results.

4fill in blank

hard

Fill both blanks to implement bottom-up dynamic programming for Fibonacci numbers.

DSA Rust

fn fib_dp(n: usize) -> u32 {
    let mut dp = vec![0u32; n + 1];
    dp[0] = 0u32;
    if n > 0 {
        dp[1] = 1u32;
    }
    for i in 2..=[1] {
        dp[i] = dp[i [2] 1usize] + dp[i - 2usize];
    }
    dp[n]
}

Drag options to blanks, or click blank then click option'

An

Bn - 1

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - in index calculations.

Looping up to n-1 instead of n.

The loop runs from 2 to n inclusive. The dp array uses subtraction to access previous Fibonacci values.

5fill in blank

hard

Fill all three blanks to create a memoized recursive function that returns the nth Fibonacci number.

DSA Rust

use std::collections::HashMap;

fn fib_memo(n: u32, memo: &mut HashMap<u32, u32>) -> u32 {
    if n <= 1 {
        return n;
    }
    if memo.contains_key(&n) {
        return *memo.get(&n).unwrap();
    }
    let result = fib_memo(n [1] 1u32, memo) [2] fib_memo(n [3] 2u32, memo);
    memo.insert(n, result);
    result
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or multiplication instead of subtraction in recursive calls.

Using multiplication or division instead of addition.

The recursive calls reduce n by 1 and 2 using subtraction. The results are added to get the Fibonacci number.

Practice

1. Why do we use dynamic programming instead of plain recursion for some problems?

easy

A. Because recursion alone can repeat the same calculations many times, making it slow.

B. Because recursion cannot solve problems with multiple steps.

C. Because dynamic programming uses loops instead of functions.

D. Because recursion always causes errors in programs.

Solution

1. Step 1: Understand recursion's limitation

   Recursion solves problems by calling itself but can repeat the same work many times.

2. Step 2: How dynamic programming helps

   Dynamic programming saves results of subproblems to avoid repeating calculations, making it faster.

3. Final Answer:

   Because recursion alone can repeat the same calculations many times, making it slow. -> Option A

4. Quick Check:

   Recursion repeats work, DP saves results [OK]

Hint: Recursion repeats work; DP remembers results to save time [OK]

Common Mistakes:

• Thinking recursion cannot solve multi-step problems
• Believing DP replaces recursion with loops only
• Assuming recursion always causes errors

2. Which of the following Rust function signatures correctly shows a recursive function for Fibonacci numbers?

easy

A. fn fib(n: u32) -> u32 { loop { n = n + 1; } }

B. fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } }

C. fn fib(n: u32) -> u32 { return n * n; }

D. fn fib(n: u32) -> u32 { let mut sum = 0; for i in 0..n { sum += i; } sum }

Solution

1. Step 1: Identify recursive call pattern

   fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } calls fib(n-1) and fib(n-2) inside the function, which is classic recursion for Fibonacci.

2. Step 2: Check other options for recursion

   Options A, C, and D do not call fib recursively; they use loops or simple calculations.

3. Final Answer:

   fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } -> Option B

4. Quick Check:

   Recursive calls in function = fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } [OK]

Hint: Look for function calling itself inside its body [OK]

Common Mistakes:

• Choosing loop-based or arithmetic-only functions
• Missing the recursive calls in the function body
• Confusing loops with recursion

3. What is the output of this Rust code using recursion to calculate Fibonacci of 4?

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

fn main() {
    println!("{}", fib(4));
}

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + 1 = (1 + 0) + 1 = 2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The println! macro prints the result of fib(4), which is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Break fib(n) into fib(n-1)+fib(n-2) stepwise [OK]

Common Mistakes:

• Adding fib(3) and fib(2) incorrectly
• Confusing fib(4) with fib(5)
• Forgetting base cases fib(0)=0, fib(1)=1

4. This Rust recursive function to calculate Fibonacci is very slow for large inputs. What is the main problem?

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

medium

A. It does not have a base case to stop recursion.

B. It uses too much memory because it stores all results in a vector.

C. It uses a loop instead of recursion.

D. It repeats the same calculations many times without saving results.

Solution

1. Step 1: Analyze recursion behavior

   The function calls fib(n-1) and fib(n-2) repeatedly without saving results, causing repeated work.

2. Step 2: Identify why it is slow

   Repeated calculations cause exponential time complexity, making it slow for large n.

3. Final Answer:

   It repeats the same calculations many times without saving results. -> Option D

4. Quick Check:

   Repeated work slows recursion without memoization [OK]

Hint: Check if function saves sub-results to avoid repeats [OK]

Common Mistakes:

• Thinking it uses too much memory storing results
• Believing it uses loops instead of recursion
• Missing the base case presence

5. You want to optimize this recursive Fibonacci function using dynamic programming in Rust. Which approach correctly applies memoization?

fn fib(n: usize, memo: &mut Vec) -> usize {
    if n <= 1 {
        n
    } else {
        if let Some(value) = memo[n] {
            value
        } else {
            let result = fib(n-1, memo) + fib(n-2, memo);
            memo[n] = Some(result);
            result
        }
    }
}

fn main() {
    let n = 5;
    let mut memo = vec![None; n+1];
    println!("{}", fib(n, &mut memo));
}

hard

A. This code uses a vector to save results and avoids repeated calculations, applying memoization correctly.

B. This code uses a loop instead of recursion, so it is not memoization.

C. This code does not save any results, so it is plain recursion.

D. This code will cause a runtime error because memo is not mutable.

Solution

1. Step 1: Check memo vector usage

   The function uses a mutable vector memo to store results of fib(n) once calculated.

2. Step 2: Confirm memoization logic

   Before calculating fib(n), it checks if memo[n] has a value to reuse, avoiding repeated work.

3. Final Answer:

   This code uses a vector to save results and avoids repeated calculations, applying memoization correctly. -> Option A

4. Quick Check:

   Memo vector stores results to speed recursion [OK]

Hint: Memo vector with Option stores and reuses results [OK]

Common Mistakes:

• Confusing memoization with loops
• Forgetting to pass mutable reference to memo
• Assuming no results are saved