Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Rust - Quick Recap

Recall & Review

beginner

What is recursion in simple terms?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

Why do we need recursion when we have loops?

Loops repeat actions but can't easily handle problems that break down into smaller similar problems, like tree traversals or factorial calculations. Recursion naturally fits these cases.

intermediate

Give an example of a problem that loops cannot express cleanly but recursion can.

Calculating factorial of a number or traversing a tree structure are easier with recursion because they involve repeating the same process on smaller parts.

beginner

What is a base case in recursion?

A base case is the simplest part of the problem that can be solved directly without further recursion. It stops the recursive calls.

intermediate

How does recursion help in expressing problems with nested or hierarchical data?

Recursion naturally follows the structure of nested or hierarchical data by calling itself on smaller parts, making the code simpler and clearer than loops.

What stops a recursive function from calling itself forever?

A A timer in the computer

B A loop inside the function

C A base case that ends recursion

D A variable that counts loops

A base case is a condition where the function stops calling itself, preventing infinite recursion.

Which problem is easier to solve with recursion than with loops?

A Summing numbers from 1 to 10

B Finding factorial of a number

C Printing numbers 1 to 10

D Adding two numbers

Factorial calculation naturally breaks down into smaller factorial problems, making recursion a clean solution.

Loops are best for problems that require:

A Breaking down problems into smaller similar parts

B Calling functions multiple times

C Handling nested data structures

D Repeating a fixed set of instructions

Loops repeat instructions a fixed number of times or until a condition is met, but don't handle nested structures well.

What is a key difference between recursion and loops?

A Recursion uses function calls; loops use repeated statements

B Loops can call themselves; recursion cannot

C Recursion is faster than loops always

D Loops need base cases; recursion does not

Recursion solves problems by calling the same function again, while loops repeat code blocks without function calls.

Which of these is a natural use case for recursion?

A Traversing a file system directory tree

B Iterating over a list of numbers

C Calculating the sum of two numbers

D Printing a message multiple times

Traversing hierarchical structures like directory trees fits recursion well because each folder can contain subfolders.

Explain why recursion is useful for problems that loops cannot express cleanly.

Think about how recursion handles smaller similar problems inside a big problem.

Describe the role of the base case in recursion and what happens if it is missing.

Base case is like the 'stop sign' for recursive calls.

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