Recursion vs Iteration When Each Wins in DSA Rust - Trade-offs & Analysis

Mental Model

Recursion solves problems by breaking them into smaller copies of themselves, while iteration solves problems by repeating steps in a loop. Each has strengths depending on the problem's nature.

Analogy: Recursion is like a set of nested Russian dolls, where each doll contains a smaller one inside, and iteration is like walking around a circular track repeatedly until you finish your laps.

Recursion:
main() -> func() -> func() -> func() -> base case
Iteration:
start -> loop -> loop -> loop -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration compute factorial and when each is better

Step 1: Recursion calls factorial(4), which calls factorial(3)

factorial(4) -> factorial(3) -> ... -> base case factorial(0)

Why: Recursion breaks problem into smaller subproblems until base case

Step 2: Recursion reaches base case factorial(0) = 1 and returns up the call stack

factorial(0) = 1 -> factorial(1) = 1 x 1 -> factorial(2) = 2 x 1 -> factorial(3) = 3 x 2 -> factorial(4) = 4 x 6

Why: Base case stops recursion and results combine on return

Step 3: Iteration initializes result=1 and multiplies by 1, 2, 3, 4 in loop

result=1 -> result=1x1=1 -> result=1x2=2 -> result=2x3=6 -> result=6x4=24

Why: Iteration repeats multiplication step by step until done

Result:

Final factorial = 24 for both recursion and iteration

Annotated Code

DSA Rust

fn factorial_recursive(n: u32) -> u32 {
    if n == 0 {
        return 1; // base case stops recursion
    }
    n * factorial_recursive(n - 1) // recursive call with smaller n
}

fn factorial_iterative(n: u32) -> u32 {
    let mut result = 1;
    for i in 1..=n {
        result *= i; // multiply result by current i
    }
    result
}

fn main() {
    let n = 4;
    let rec = factorial_recursive(n);
    let iter = factorial_iterative(n);
    println!("Recursive factorial({}) = {}", n, rec);
    println!("Iterative factorial({}) = {}", n, iter);
}

if n == 0 { return 1; }

stop recursion at base case to avoid infinite calls

n * factorial_recursive(n - 1)

recursive call reduces problem size by 1

for i in 1..=n { result *= i; }

loop multiplies result by each number from 1 to n

Output

Recursive factorial(4) = 24

Iterative factorial(4) = 24

Complexity Analysis

Time: O(n) because both recursion and iteration multiply n numbers once

Space: Recursion uses O(n) stack space due to call stack; iteration uses O(1) constant space

vs Alternative: Iteration is more space efficient; recursion is simpler to write for problems naturally defined by self-calls

Edge Cases

n = 0 (base case)

Recursion returns 1 immediately; iteration loop does not run and returns 1

DSA Rust

if n == 0 { return 1; }

n = 1 (smallest positive)

Recursion calls factorial(1) then factorial(0); iteration multiplies once by 1

DSA Rust

for i in 1..=n { result *= i; }

When to Use This Pattern

When a problem naturally breaks into smaller subproblems or has a clear base case, recursion fits well; when you need efficient space and simple repetition, iteration is better.

Common Mistakes

Mistake: Forgetting the base case in recursion causing infinite calls
Fix: Always include a base case that stops recursion

Mistake: Using recursion for very large inputs causing stack overflow
Fix: Use iteration or tail recursion optimization if available

Summary

Recursion solves problems by calling itself with smaller inputs; iteration solves by repeating steps in a loop.

Use recursion when the problem naturally fits a divide-and-conquer or self-similar pattern; use iteration when you want efficient space and simple repetition.

The key insight is recursion uses the call stack to remember work, while iteration uses loops to repeat work without extra stack.

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