Recursion vs Iteration When Each Wins in DSA Rust - Key Differences

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

When is iteration usually better than recursion?

Iteration is better when you want to save memory and avoid the overhead of many function calls, especially for simple loops or large data sets.

intermediate

Why can recursion be easier to understand for some problems?

Recursion matches how we naturally break down problems into smaller similar problems, making the code simpler and closer to the problem's definition.

beginner

What is a base case in recursion?

A base case is the simplest situation in recursion where the function stops calling itself and returns a result directly.

intermediate

Give an example when recursion wins over iteration.

Recursion wins when solving problems like tree traversals or divide-and-conquer algorithms where the problem naturally splits into smaller parts.

Which of these is a key advantage of iteration over recursion?

A Automatically handles base cases

B Uses less memory by avoiding function call overhead

C Always faster for all problems

D Easier to write for complex tree problems

Iteration uses loops and avoids the extra memory used by recursive function calls.

What must a recursive function always have to avoid infinite calls?

A A base case

B A loop

C An iterator

D A global variable

A base case stops the recursion by providing a direct answer.

Which problem is naturally suited for recursion?

A Finding max in an array

B Summing numbers in a list

C Calculating factorial

D Printing numbers from 1 to 10

Factorial calculation naturally breaks down into smaller factorials, perfect for recursion.

What is a downside of recursion compared to iteration?

A Cannot solve complex problems

B Does not use memory

C Always slower than iteration

D Can cause stack overflow if too deep

Deep recursion can use too much memory and crash the program.

When should you prefer iteration over recursion?

A When memory is limited and problem is simple looping

B When problem involves trees

C When problem is naturally divided into subproblems

D When you want simpler code

Iteration is better for simple loops and limited memory situations.

Explain in your own words when recursion is better than iteration and why.

Think about problems that naturally split into parts.

Describe the main risks or downsides of using recursion and how iteration can help.

Consider memory and program crashes.

Practice

1. Which situation is recursion generally better suited for compared to iteration?

easy

A. When the problem can be divided into similar smaller problems

B. When you need to process large data sets with minimal memory

C. When you want to avoid function call overhead

D. When the problem requires simple repeated loops

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem can be broken down into smaller similar problems, like tree traversals or factorial calculation.

2. Step 2: Compare with iteration use case

   Iteration is better for simple repeated loops or when memory overhead of function calls is a concern.

3. Final Answer:

   When the problem can be divided into similar smaller problems -> Option A

4. Quick Check:

   Recursion fits divide-and-conquer problems [OK]

Hint: Recursion fits divide-and-conquer problems best [OK]

Common Mistakes:

• Thinking recursion is always faster
• Confusing iteration with recursion use cases
• Ignoring function call overhead in recursion

2. Which of the following is the correct Rust syntax to write a recursive function that calculates factorial?

easy

A. fn factorial(n: u32) -> u32 { loop { return n * factorial(n - 1); } }

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

C. fn factorial(n: u32) -> u32 { while n > 0 { n *= n - 1; } n }

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

Solution

1. Step 1: Identify recursive function structure

   Recursive factorial calls itself with n-1 until base case n==0 returns 1.

2. Step 2: Check each option's correctness

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } correctly implements recursion with base case and recursive call. fn factorial(n: u32) -> u32 { let mut result = 1; for i in 1..=n { result *= i; } result } is iterative, C has incorrect loop logic, D causes infinite loop.

3. Final Answer:

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

4. Quick Check:

   Recursive factorial syntax [OK]

Hint: Look for base case and recursive call in function [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion for this question
• Incorrect loop or return statements

3. What is the output of this Rust code snippet?

fn sum_iter(n: u32) -> u32 {
    let mut total = 0;
    for i in 1..=n {
        total += i;
    }
    total
}

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

fn main() {
    println!("{}", sum_iter(3));
    println!("{}", sum_rec(3));
}

medium

A. 6
6

B. 3
3

C. 0
0

D. Error due to stack overflow

Solution

1. Step 1: Trace sum_iter(3)

   Loop adds 1 + 2 + 3 = 6.

2. Step 2: Trace sum_rec(3)

   Recursively adds 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 6 -> Option A

4. Quick Check:

   Both sum functions return 6 for input 3 [OK]

Hint: Sum 1 to n = n*(n+1)/2 = 6 for n=3 [OK]

Common Mistakes:

• Confusing output format with separate lines
• Assuming recursion causes error for small n
• Misreading loop range

4. Identify the bug in this recursive Rust function and choose the fix:

fn countdown(n: u32) {
    println!("{}", n);
    countdown(n - 1);
}

medium

A. Change println! to return n instead

B. Replace recursion with a for loop

C. Add a base case to stop recursion when n == 0

D. Use n + 1 instead of n - 1 in recursive call

Solution

1. Step 1: Analyze the recursive function

   Function calls itself with n-1 without stopping condition, causing infinite recursion.

2. Step 2: Determine fix to prevent infinite recursion

   Adding a base case like if n == 0 { return; } stops recursion safely.

3. Final Answer:

   Add a base case to stop recursion when n == 0 -> Option C

4. Quick Check:

   Base case prevents infinite recursion [OK]

Hint: Always add base case to recursive functions [OK]

Common Mistakes:

• Forgetting base case causes stack overflow
• Changing print statement instead of fixing recursion
• Using wrong recursive call direction

5. You want to process a large list of numbers to find the maximum value. Which approach is better in Rust and why? A recursive function that compares head and tail elements or an iterative loop?

hard

A. Recursive function, because Rust optimizes all recursion automatically

B. Iterative loop, because recursion may cause stack overflow on large lists

C. Recursive function, because it is always faster than iteration

D. Either approach is equally good for large lists

Solution

1. Step 1: Consider recursion limits in Rust

   Rust does not guarantee tail call optimization, so deep recursion risks stack overflow on large inputs.

2. Step 2: Compare iteration benefits

   Iteration uses constant stack space and is safer for large lists, avoiding overflow.

3. Final Answer:

   Iterative loop, because recursion may cause stack overflow on large lists -> Option B

4. Quick Check:

   Iteration safer for large data [OK]

Hint: Use iteration for large data to avoid stack overflow [OK]

Common Mistakes:

• Assuming recursion is always faster
• Ignoring stack overflow risk
• Believing Rust always optimizes recursion