Recursion Concept and Call Stack Visualization in DSA Rust - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Call function with input n

↓

Check if n is base case?

↓

Return base

↓

Wait for result

↓

Calculate result

↓

Return result

Shows how a recursive function calls itself until it reaches a base case, then returns results back up the call stack.

Execution Sample

DSA Rust

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

println!("{}", factorial(3));

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

Execution Table

Step	Operation	Current n	Call Stack	Return Value	Visual Call Stack
1	Call factorial(3)	3	[factorial(3)]		factorial(3)
2	Call factorial(2)	2	[factorial(3), factorial(2)]		factorial(3) -> factorial(2)
3	Call factorial(1)	1	[factorial(3), factorial(2), factorial(1)]		factorial(3) -> factorial(2) -> factorial(1)
4	Call factorial(0)	0	[factorial(3), factorial(2), factorial(1), factorial(0)]		factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)
5	Base case reached, return 1	0	[factorial(3), factorial(2), factorial(1), factorial(0)]	1	factorial(3) -> factorial(2) -> factorial(1) -> (return 1)
6	Return factorial(1) = 1 * 1	1	[factorial(3), factorial(2), factorial(1)]	1	factorial(3) -> factorial(2) -> (return 1)
7	Return factorial(2) = 2 * 1	2	[factorial(3), factorial(2)]	2	factorial(3) -> (return 2)
8	Return factorial(3) = 3 * 2	3	[factorial(3)]	6	(return 6)
9	Final return, call stack empty		[]	6

💡 Recursion ends when base case n=0 is reached and all calls return their results back up.

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	Final
n		3	2	1	0	0	1	2	3
Call Stack	empty	[factorial(3)]	[factorial(3), factorial(2)]	[factorial(3), factorial(2), factorial(1)]	[factorial(3), factorial(2), factorial(1), factorial(0)]	[factorial(3), factorial(2), factorial(1), factorial(0)]	[factorial(3), factorial(2), factorial(1)]	[factorial(3), factorial(2)]	[factorial(3)]	empty
Return Value	none	none	none	none	1	1	1	2	6	6

Key Moments - 3 Insights

Why does the function keep calling itself instead of returning immediately?

Because the base case is not reached yet (see steps 1-4 in execution_table), the function must call itself with smaller n until n=0.

How does the function remember where to return after each recursive call?

Each call is added to the call stack (shown in Call Stack column), so after reaching base case, returns happen in reverse order (steps 5-8).

Why does the return value appear only after the base case is reached?

Because the function waits for the recursive call to finish before calculating and returning its own result (see Return Value column starting step 5).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the current call stack?

A [factorial(3), factorial(2), factorial(1)]

B [factorial(3), factorial(2), factorial(1), factorial(0)]

C [factorial(3), factorial(2)]

D [factorial(3)]

💡 Hint

Check the Call Stack column at step 4 in execution_table.

At which step does the function start returning values back up the call stack?

A Step 5

B Step 7

C Step 3

D Step 9

💡 Hint

Look for the first step where Return Value is not empty in execution_table.

If the input n was 4 instead of 3, how many calls would be on the call stack at the deepest point?

A 4

B 3

C 5

D 6

💡 Hint

The call stack depth equals n+1 because it includes the base case call with n=0.

Concept Snapshot

Recursion calls the same function with smaller input until base case.
Each call waits for the next to finish (call stack grows).
Base case returns a value, then calls return in reverse order.
Call stack tracks active calls and their inputs.
Useful for problems that break down into smaller similar problems.

Full Transcript

This visualization shows how recursion works by calling the same function repeatedly with smaller inputs until a base case is reached. The call stack grows as each call waits for the next. Once the base case returns a value, each call returns its result back up the stack. The example uses factorial(3), showing calls with n=3,2,1,0, then returns 1, then 1*1=1, then 2*1=2, then 3*2=6. The call stack and return values are tracked step-by-step to help understand recursion flow.

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