Recursion vs Iteration When Each Wins in DSA Rust - Visual Comparison

Concept Flow - Recursion vs Iteration When Each Wins

Start

↓

Choose Problem Type

↓

Problem fits recursive pattern?

↓

Use Recursion

↓

Stack grows

↓

Base case reached

↓

Unwind stack

↓

Result

+--> No↓

Use Iteration

↓

Loop runs

↓

Update variables

↓

Result

This flow shows how to decide between recursion and iteration based on problem type and resource use.

Execution Sample

DSA Rust

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

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

Calculates factorial of n using recursion and iteration.

Execution Table

Step	Operation	Call Stack Depth	Current n	Action	Result / Partial Result
1	Call factorial_recursive(3)	1	3	Check n==0? No, recurse with n=2	Pending
2	Call factorial_recursive(2)	2	2	Check n==0? No, recurse with n=1	Pending
3	Call factorial_recursive(1)	3	1	Check n==0? No, recurse with n=0	Pending
4	Call factorial_recursive(0)	4	0	Base case reached, return 1	1
5	Return from factorial_recursive(1)	3	1	Calculate 1 * 1	1
6	Return from factorial_recursive(2)	2	2	Calculate 2 * 1	2
7	Return from factorial_recursive(3)	1	3	Calculate 3 * 2	6
8	Call factorial_iterative(3)	0	-	Initialize result=1	1
9	Loop i=1	0	-	result = 1 * 1	1
10	Loop i=2	0	-	result = 1 * 2	2
11	Loop i=3	0	-	result = 2 * 3	6
12	End loop	0	-	Return result	6

💡 Recursion ends when base case n==0 is reached; iteration ends after loop completes.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	Final
n (recursive)	3	3	2	1	0	1	2	3	-	-	-	-	-
Call Stack Depth	0	1	2	3	4	3	2	1	0	0	0	0	0
result (iterative)	1	1	1	1	1	1	1	1	1	1	2	6	6

Key Moments - 3 Insights

Why does recursion use a call stack and iteration does not?

Recursion calls itself repeatedly, each call waiting for the next to finish, so the call stack grows (see steps 1-4 in execution_table). Iteration uses loops and updates variables in place without extra calls (see steps 8-12).

When does recursion stop calling itself?

Recursion stops when it reaches the base case (n == 0), returning a value without further calls (step 4 in execution_table). This prevents infinite recursion.

Why might iteration be better for large inputs?

Iteration uses constant memory and avoids growing the call stack, so it handles large inputs without risk of stack overflow (see call stack depth stays 0 in steps 8-12).

Visual Quiz - 3 Questions

Look at the execution_table, what is the call stack depth when factorial_recursive(1) is called?

A 1

B 3

C 4

D 2

💡 Hint

Check Step 3 in execution_table under 'Call Stack Depth'

At which step does the recursion reach its base case and return a value?

A Step 4

B Step 7

C Step 2

D Step 5

💡 Hint

Look for 'Base case reached' in execution_table

If we increase n to 5, how would the call stack depth change during recursion?

A It would stay the same

B It would decrease

C It would increase to 5 at the deepest call

D It would be zero

💡 Hint

Call stack depth equals current recursion depth, see pattern in execution_table steps 1-4

Concept Snapshot

Recursion calls a function within itself until a base case stops it.
Iteration uses loops to repeat actions until a condition fails.
Recursion uses more memory (call stack), iteration uses less.
Use recursion for problems naturally recursive (trees, divide and conquer).
Use iteration for large inputs or simple repeated tasks.
Base case in recursion prevents infinite calls.

Full Transcript

This lesson compares recursion and iteration by tracing factorial calculation both ways. Recursion calls itself with decreasing n until base case n=0 returns 1, then unwinds multiplying results. Iteration uses a loop multiplying from 1 to n. Recursion uses a call stack growing with each call, iteration uses constant memory. Recursion is elegant for problems with natural recursive structure but risks stack overflow on large inputs. Iteration is efficient for large inputs and simple repetition. Key points include understanding call stack depth, base case stopping recursion, and when to choose each method.

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