Why Recursion Exists and What Loops Cannot Express Cleanly in DSA Rust - Why It Works

Concept Flow - Why Recursion Exists and What Loops Cannot Express Cleanly

Start Recursive Function

↓

Check Base Case?

Yes→Return Base Result

No↓

Call Function Itself with Smaller Input

↓

Combine Result with Current Step

↓

Return Combined Result

↓

End

Recursion breaks a problem into smaller parts, solves each part by calling itself, and combines results. Loops can't easily express problems needing nested or hierarchical steps.

Execution Sample

DSA Rust

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

let result = factorial(3);

Calculates factorial of 3 using recursion by multiplying n with factorial of n-1 until base case 0.

Execution Table

Step	Call	Argument n	Base Case?	Return Value	Stack Depth
1	factorial	3	No	3 * factorial(2)	1
2	factorial	2	No	2 * factorial(1)	2
3	factorial	1	No	1 * factorial(0)	3
4	factorial	0	Yes	1	4
5	Return from factorial(0)	-	-	1	3
6	Return from factorial(1)	-	-	1 * 1 = 1	2
7	Return from factorial(2)	-	-	2 * 1 = 2	1
8	Return from factorial(3)	-	-	3 * 2 = 6	0

💡 Recursion stops when base case n == 0 is reached, then returns unwind multiplying results.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 8
n	3	3	2	1	0	-
Return Value	-	-	-	-	1	6
Stack Depth	0	1	2	3	4	0

Key Moments - 3 Insights

Why does recursion need a base case?

Without a base case (see Step 4 in execution_table), recursion would call itself forever, causing a crash. The base case stops recursion and starts returning results.

Why can't loops express this factorial calculation cleanly?

Loops handle repeated steps but can't naturally express nested calls where each step depends on the result of a smaller problem, as recursion does (see stack depth changes in variable_tracker).

What does stack depth mean in recursion?

Stack depth shows how many recursive calls are waiting to return. Each call pauses until the next smaller call finishes (see Stack Depth column in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when n is 1 (Step 6)?

A 0

B 1

C 2

D 3

💡 Hint

Check the Return Value column at Step 6 in execution_table.

At which step does the recursion reach its base case?

A Step 2

B Step 6

C Step 4

D Step 8

💡 Hint

Look for Base Case? column marked Yes in execution_table.

If we remove the base case, what happens to the stack depth?

A It grows indefinitely

B It decreases over time

C It stays at 0

D It jumps to final value immediately

💡 Hint

Refer to Stack Depth column and key_moments about base case necessity.

Concept Snapshot

Recursion calls a function inside itself with smaller input.
It needs a base case to stop.
Each call waits for the next to finish (stack).
Loops repeat steps but can't handle nested dependencies easily.
Use recursion for problems like factorial, tree traversal.

Full Transcript

Recursion is a way to solve problems by breaking them into smaller versions of the same problem. Each recursive call waits for the next smaller call to finish, creating a stack of calls. The base case stops recursion to avoid infinite calls. Loops repeat actions but can't express nested or hierarchical problems cleanly. For example, factorial uses recursion by multiplying n with factorial of n-1 until n is zero. The stack depth shows how many calls are waiting. Without a base case, recursion would never stop and crash. This visual trace shows each call, argument, return value, and stack depth step-by-step.

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