Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Rust - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define a recursive function that counts down from n to 1.

DSA Rust

fn countdown(n: i32) {
    if n == 0 {
        return;
    }
    println!("{}", n);
    countdown([1]);
}

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

An + 1

Bn - 1

Cn * 2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using 0 always stops immediately without counting down.

The function calls itself with n - 1 to count down until it reaches zero.

2fill in blank

medium

Complete the code to calculate factorial of n recursively.

DSA Rust

fn factorial(n: u32) -> u32 {
    if n == 0 {
        1
    } else {
        n * factorial([1])
    }
}

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

A0

Bn + 1

Cn - 1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using 0 or 1 directly in recursive call breaks logic.

Factorial multiplies n by factorial of n - 1 until it reaches 0.

3fill in blank

hard

Fix the error in the recursive Fibonacci function to correctly compute fib(n).

DSA Rust

fn fib(n: u32) -> u32 {
    if n == 0 || n == 1 {
        n
    } else {
        fib([1]) + fib(n - 2)
    }
}

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

An - 1

Bn + 1

Cn - 3

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 causes infinite recursion.

Using n - 3 skips needed Fibonacci terms.

Fibonacci is sum of fib(n-1) and fib(n-2).

4fill in blank

hard

Fill both blanks to create a recursive function that sums numbers from 1 to n.

DSA Rust

fn sum_to_n(n: u32) -> u32 {
    if n == 0 {
        [1]
    } else {
        n + sum_to_n([2])
    }
}

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

A0

Bn - 1

C1

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 1 in base case causes off-by-one error.

Using n + 1 in recursive call causes infinite recursion.

Base case returns 0; recursive call sums n with sum_to_n(n - 1).

5fill in blank

hard

Fill all three blanks to create a recursive function that reverses a string slice.

DSA Rust

fn reverse(s: &str) -> String {
    if s.is_empty() {
        [1]
    } else {
        let (first, rest) = s.split_at(1);
        reverse([2]) + first
    }
}

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

AString::new()

B&s[1..]

C&rest

Ds

Attempts:

3 left

💡 Hint

Common Mistakes

Returning s in base case causes infinite recursion.

Using &s[1..] instead of &rest is correct but less clear here.

Base case returns empty string; recursive call reverses rest and adds first char.

Practice

1. Why do we use recursion instead of loops in some problems?
fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } }

easy

A. Recursion uses less memory than loops.

B. Loops are always slower than recursion.

C. Recursion can express problems with self-similar structure more naturally.

D. Loops cannot perform repeated actions.

Solution

1. Step 1: Understand recursion's purpose

   Recursion is useful when a problem can be broken down into smaller similar problems, like factorial.

2. Step 2: Compare recursion and loops

   Loops repeat actions but do not naturally express self-similar or nested problems as clearly as recursion.

3. Final Answer:

   Recursion can express problems with self-similar structure more naturally. -> Option C

4. Quick Check:

   Recursion = natural for self-similar problems [OK]

Hint: Recursion fits problems breaking into smaller similar parts [OK]

Common Mistakes:

• Thinking loops are always slower
• Believing recursion uses less memory
• Assuming loops cannot repeat actions

2. Which of the following is the correct Rust syntax for a recursive function that sums numbers from 1 to n?

easy

A. fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } }

B. fn sum(n: u32) -> u32 { loop { n + sum(n - 1) } }

C. fn sum(n: u32) -> u32 { while n > 0 { n + sum(n - 1) } }

D. fn sum(n: u32) -> u32 { if n == 0 { 1 } else { n * sum(n - 1) } }

Solution

1. Step 1: Identify correct base case and recursion

   fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } correctly returns 0 when n is 0 and sums recursively.

2. Step 2: Check syntax and logic

   Options B and C misuse loops inside recursion, causing infinite loops or errors. fn sum(n: u32) -> u32 { if n == 0 { 1 } else { n * sum(n - 1) } } multiplies instead of sums.

3. Final Answer:

   fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } -> Option A

4. Quick Check:

   Correct recursion syntax = fn sum(n: u32) -> u32 { if n == 0 { 0 } else { n + sum(n - 1) } } [OK]

Hint: Look for correct base case and recursive call pattern [OK]

Common Mistakes:

• Using loops inside recursive function incorrectly
• Wrong base case value
• Mixing sum and product operations

3. What is the output of this Rust code?

fn print_numbers(n: u32) {
    if n == 0 {
        return;
    }
    print_numbers(n - 1);
    println!("{}", n);
}

fn main() {
    print_numbers(3);
}

medium

A. 1 2 3

B. 3 2 1

C. 3 3 3

D. 1 1 1

Solution

1. Step 1: Trace recursive calls

   print_numbers(3) calls print_numbers(2), then print_numbers(1), then print_numbers(0) which returns immediately.

2. Step 2: Print after recursion unwinds

   After reaching 0, the calls print 1, then 2, then 3 in order.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Recursion prints ascending after calls [OK]

Hint: Look where print happens: before or after recursive call [OK]

Common Mistakes:

• Assuming print happens before recursion
• Confusing order of prints
• Ignoring base case return

4. Identify the error in this recursive Rust function that calculates Fibonacci numbers:

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

medium

A. Base cases are incorrect for Fibonacci sequence.

B. Function uses loops instead of recursion.

C. Function causes infinite recursion for n=0.

D. Missing return statement in the else branch causes no value returned.

Solution

1. Step 1: Check function branches for return values

   The else branch ends with an expression but lacks a return or semicolon, causing no value returned.

2. Step 2: Understand Rust expression rules

   In Rust, the last expression without semicolon is returned. Here, semicolon after fib(n - 1) + fib(n - 2) prevents return.

3. Final Answer:

   Missing return statement in the else branch causes no value returned. -> Option D

4. Quick Check:

   Semicolon stops return in else branch [OK]

Hint: Check for semicolons ending return expressions [OK]

Common Mistakes:

• Ignoring semicolon effect on return
• Thinking base cases are wrong
• Confusing recursion with loops

5. You want to flatten a nested list of integers using recursion in Rust. Which approach best expresses this problem that loops cannot cleanly solve?

fn flatten(list: &[Nested]) -> Vec<i32> {
    // Nested is enum: Int(i32) or List(Vec<Nested>)
    // Fill this function
}

hard

A. Use a loop that only handles flat lists, ignoring nested ones.

B. Use recursion to check each element: if Int, add to result; if List, recursively flatten and extend result.

C. Use a loop with a stack to simulate recursion manually.

D. Use a single loop to iterate and flatten all nested lists without recursion.

Solution

1. Step 1: Understand nested list structure

   Nested lists can contain integers or other lists, requiring a method to explore all levels.

2. Step 2: Apply recursion to handle arbitrary depth

   Recursion naturally handles nested structures by calling itself on sublists, collecting all integers.

3. Final Answer:

   Use recursion to check each element: if Int, add to result; if List, recursively flatten and extend result. -> Option B

4. Quick Check:

   Recursion handles nested depth cleanly [OK]

Hint: Recursion fits nested structures better than flat loops [OK]

Common Mistakes:

• Trying to flatten nested lists with simple loops
• Ignoring nested depth in loops
• Using loops that skip nested elements