Recursion Concept and Call Stack Visualization in DSA Rust

Mental Model

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

Analogy: Imagine a set of nested boxes where each box contains a smaller box inside it. You open each box until you find the smallest one, then close them back in reverse order.

main() -> func() -> func() -> func() -> base case
stack frames:
[func call 3]
[func call 2]
[func call 1]
[main]

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Show how recursive calls build up and then return results using the call stack

Step 1: Call factorial(3), which calls factorial(2)

Stack: [main] -> [factorial(3) ↑] -> [factorial(2)]
Waiting for factorial(2) result

Why: We break the problem into smaller part factorial(2)

Step 2: factorial(2) calls factorial(1)

Stack: [main] -> [factorial(3)] -> [factorial(2) ↑] -> [factorial(1)]
Waiting for factorial(1) result

Why: Keep breaking down until base case

Step 3: factorial(1) calls factorial(0), the base case

Stack: [main] -> [factorial(3)] -> [factorial(2)] -> [factorial(1) ↑] -> [factorial(0)]
Waiting for factorial(0) result

Why: Reach simplest problem with known answer

Step 4: factorial(0) returns 1 (base case)

Stack: [main] -> [factorial(3)] -> [factorial(2)] -> [factorial(1) ↑]
Return value 1

Why: Base case solved, start returning results

Step 5: factorial(1) returns 1 * factorial(0) = 1

Stack: [main] -> [factorial(3)] -> [factorial(2) ↑]
Return value 1

Why: Combine result with current step

Step 6: factorial(2) returns 2 * factorial(1) = 2

Stack: [main] -> [factorial(3) ↑]
Return value 2

Why: Combine result with current step

Step 7: factorial(3) returns 3 * factorial(2) = 6

Stack: [main]
Return value 6

Why: Final result computed

Result:

Stack empty, factorial(3) = 6

Annotated Code

DSA Rust

fn factorial(n: u32) -> u32 {
    if n == 0 {
        return 1; // base case: factorial(0) = 1
    }
    // recursive case: n * factorial(n-1)
    n * factorial(n - 1)
}

fn main() {
    let num = 3;
    let result = factorial(num);
    println!("Factorial of {} is {}", num, result);
}

if n == 0 { return 1; }

Check base case to stop recursion

n * factorial(n - 1)

Recursive call to solve smaller problem and multiply

Output

Factorial of 3 is 6

Complexity Analysis

Time: O(n) because the function calls itself n times until reaching the base case

Space: O(n) because each recursive call adds a new frame to the call stack

vs Alternative: Iterative approach uses O(1) space but recursion is easier to write and understand for problems like factorial

Edge Cases

Input 0 (base case)

Returns 1 immediately without further calls

DSA Rust

if n == 0 { return 1; }

Input 1

Calls factorial(0) once then returns 1

DSA Rust

n * factorial(n - 1)

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a simple stopping point, use recursion to solve it naturally.

Common Mistakes

Mistake: Forgetting the base case, causing infinite recursion
Fix: Always include a clear base case that stops recursion

Mistake: Calling the recursive function with the same argument, never reducing problem size
Fix: Make sure each recursive call works on a smaller or simpler input

Summary

Recursion solves problems by calling itself on smaller parts until reaching a simple base case.

Use recursion when a problem naturally breaks down into similar smaller problems.

The key is the base case that stops recursion and the call stack that holds intermediate results.

Practice

1. What happens when a recursive function calls itself without a base case?

easy

A. The function converts into a loop automatically.

B. The function returns immediately without doing anything.

C. The function runs only once and stops.

D. It causes infinite recursion leading to a stack overflow error.

Solution

1. Step 1: Understand recursion base case role

   The base case stops recursion by providing a condition to end calls.

2. Step 2: Analyze missing base case effect

   Without a base case, the function keeps calling itself endlessly, filling the call stack.

3. Final Answer:

   It causes infinite recursion leading to a stack overflow error. -> Option D

4. Quick Check:

   Missing base case = infinite recursion [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Thinking recursion stops automatically
• Assuming function returns without base case
• Confusing recursion with loops

2. Which of the following is the correct syntax to define a recursive function in Rust that calculates factorial of a number n?

easy

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

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

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

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

Solution

1. Step 1: Check function return type and base case

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } correctly returns u32 and has base case for n == 0 returning 1.

2. Step 2: Verify recursive call correctness

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } calls factorial(n - 1) correctly; others miss return type or have wrong logic.

3. Final Answer:

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

4. Quick Check:

   Correct syntax = fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } [OK]

Hint: Look for base case and correct return type in Rust function [OK]

Common Mistakes:

• Omitting return type in function signature
• Using while loop inside recursive function
• Calling factorial with n + 1 causing infinite recursion

3. What is the output of the following 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: Understand print order after recursion

   After reaching base case, prints happen in reverse call order: prints 1, then 2, then 3.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Recursion prints after calls = 1 2 3 [OK]

Hint: Print after recursive call prints in ascending order [OK]

Common Mistakes:

• Assuming prints happen before recursive call
• Confusing order of execution in recursion
• Ignoring base case effect

4. Identify the error in this Rust recursive function that calculates the sum of numbers from 1 to n:

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

medium

A. The base case condition should be n == 0, not n == 1.

B. The function lacks a return statement in the else block.

C. The recursive call uses n + 1 instead of n - 1, causing infinite recursion.

D. The function should use a loop instead of recursion.

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum(n + 1), which increases n, moving away from base case.

2. Step 2: Understand effect on recursion

   Since n grows, base case n == 1 is never reached, causing infinite recursion and stack overflow.

3. Final Answer:

   The recursive call uses n + 1 instead of n - 1, causing infinite recursion. -> Option C

4. Quick Check:

   Recursive call must reduce n to reach base case [OK]

Hint: Recursive calls should move toward base case by decreasing n [OK]

Common Mistakes:

• Using n + 1 instead of n - 1 in recursion
• Confusing base case condition
• Missing return keyword in else block

5. Given the following Rust recursive function that reverses a string slice, what will be the output of reverse("rust")?

fn reverse(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let (first, rest) = s.split_at(1);
        format!("{}{}", reverse(rest), first)
    }
}

fn main() {
    println!("{}", reverse("rust"));
}

hard

A. "tsur"

B. "rust"

C. "trus"

D. "rustt"

Solution

1. Step 1: Understand recursion and string splitting

   The function splits the string into first character and rest, then recursively reverses rest and appends first.

2. Step 2: Trace calls for "rust"

   reverse("rust") calls reverse("ust") + "r", reverse("ust") calls reverse("st") + "u", and so on, building reversed string "tsur".

3. Final Answer:

   "tsur" -> Option A

4. Quick Check:

   Recursive reverse builds string backwards = "tsur" [OK]

Hint: Recursive reverse appends first char after reversing rest [OK]

Common Mistakes:

• Confusing order of concatenation
• Not handling empty string base case
• Assuming original string is returned