Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Rust - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive vs Loop Factorial

What is the output of this Rust code that calculates factorial using recursion and a loop?

DSA Rust

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

fn factorial_loop(n: u32) -> u32 {
    let mut result = 1;
    for i in 1..=n {
        result *= i;
    }
    result
}

fn main() {
    let rec = factorial_recursive(5);
    let looped = factorial_loop(5);
    println!("Recursive: {} Loop: {}", rec, looped);
}

A Recursive: 24 Loop: 120

B Recursive: 120 Loop: 120

C Recursive: 120 Loop: 24

D Recursive: 0 Loop: 0

💡 Hint

Both methods calculate factorial of 5, which is 120.

Both recursive and loop methods correctly compute 5! = 120.

🧠 Conceptual

intermediate

Why Recursion Can Express Problems Loops Cannot Easily

Which of these problem types is best expressed using recursion rather than loops?

A Repeating a task 10 times

B Summing numbers from 1 to 100

C Traversing a tree structure

D Calculating the average of a list

💡 Hint

Think about problems with nested or branching structures.

Tree traversal naturally fits recursion because each node can have multiple child nodes, which loops cannot easily handle without extra data structures.

🔧 Debug

advanced

Identify the Error in Recursive Fibonacci

What error will this Rust code produce when calculating fibonacci(5)?

DSA Rust

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

fn main() {
    println!("{}", fibonacci(5));
}

A Stack overflow error due to infinite recursion

B Compilation error due to missing return statements

C Prints 5 correctly

D Prints 8 correctly

💡 Hint

Trace fibonacci(5) calls carefully.

The code correctly computes fibonacci(5) = 8 by summing fibonacci(4) and fibonacci(3).

❓ Predict Output

advanced

Output of Recursive Directory Size Calculation

Given this simplified Rust code to calculate total size of files in nested directories recursively, what is the output?

DSA Rust

struct File {
    size: u32,
}

struct Directory {
    files: Vec<File>,
    subdirs: Vec<Directory>,
}

impl Directory {
    fn total_size(&self) -> u32 {
        let files_size: u32 = self.files.iter().map(|f| f.size).sum();
        let subdirs_size: u32 = self.subdirs.iter().map(|d| d.total_size()).sum();
        files_size + subdirs_size
    }
}

fn main() {
    let dir = Directory {
        files: vec![File { size: 10 }, File { size: 20 }],
        subdirs: vec![
            Directory {
                files: vec![File { size: 5 }],
                subdirs: vec![],
            },
            Directory {
                files: vec![],
                subdirs: vec![
                    Directory {
                        files: vec![File { size: 15 }],
                        subdirs: vec![],
                    }
                ],
            },
        ],
    };
    println!("Total size: {}", dir.total_size());
}

A Total size: 50

B Total size: 30

C Total size: 35

D Total size: 40

💡 Hint

Add sizes of all files including nested directories.

Sum of files: 10 + 20 + 5 + 15 = 50.

🧠 Conceptual

expert

Why Recursion is Essential for Some Algorithms

Which statement best explains why recursion is essential for some algorithms and cannot be replaced by simple loops without extra data structures?

A Recursion naturally handles problems with self-similar subproblems and implicit stacks, which loops cannot express without explicit stacks or queues.

B Loops are always slower than recursion and thus recursion is preferred for performance.

C Loops cannot perform repeated tasks, only recursion can.

D Recursion uses less memory than loops in all cases.

💡 Hint

Think about how recursion manages function calls and problem breakdown.

Recursion uses the call stack to manage self-similar subproblems naturally, while loops require explicit data structures to mimic this behavior.

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