Recursion Base Case and Recursive Case in DSA Rust - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start Recursive Function Call

↓

Check Base Case Condition

↓

Return Base Case Value

↓

Make Recursive Call with Smaller Input

↓

Combine Recursive Result with Current Step

↓

Return Combined Result

↓

End Recursive Call

The function checks if it reached the simplest case (base case). If yes, it returns a value. Otherwise, it calls itself with a smaller input and combines the result.

Execution Sample

DSA Rust

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

Calculates factorial of n using recursion with base case n==0 returning 1.

Execution Table

Step	Call Stack	Current n	Condition (n==0?)	Action	Return Value	Visual Call Stack
1	factorial(3)	3	No	Call factorial(2)		factorial(3)
2	factorial(3) -> factorial(2)	2	No	Call factorial(1)		factorial(3) └─ factorial(2)
3	factorial(3) -> factorial(2) -> factorial(1)	1	No	Call factorial(0)		factorial(3) └─ factorial(2) └─ factorial(1)
4	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	0	Yes	Return 1	1	factorial(3) └─ factorial(2) └─ factorial(1) └─ factorial(0)
5	factorial(3) -> factorial(2) -> factorial(1)	1	-	Calculate 1 * 1	1	factorial(3) └─ factorial(2) └─ factorial(1)
6	factorial(3) -> factorial(2)	2	-	Calculate 2 * 1	2	factorial(3) └─ factorial(2)
7	factorial(3)	3	-	Calculate 3 * 2	6	factorial(3)
8	-	-	-	Return final result 6	6	-

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

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	Final
n	3	3	2	1	0	1	2	3	3
Return Value					1	1	2	6	6
Call Stack Depth	1	1	2	3	4	3	2	1	0

Key Moments - 3 Insights

Why does the recursion stop at n == 0?

Because the base case condition n == 0 returns a value without further recursive calls, as shown in step 4 of the execution_table.

What happens after the base case returns a value?

The function returns to the previous call, combines the returned value with current n, and continues returning up the call stack, as seen from steps 5 to 8.

Why do we multiply n with factorial(n-1) in the recursive case?

Because factorial(n) = n * factorial(n-1), so each call waits for the smaller factorial to return before multiplying, shown in steps 5, 6, and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the return value when n is 0?

A 0

B n

C 1

D Undefined

💡 Hint

Check the 'Return Value' column at step 4 in execution_table.

At which step does the recursion start to return values back up the call stack?

A Step 5

B Step 3

C Step 4

D Step 8

💡 Hint

Look for the first step where 'Return Value' is filled and calculation happens after base case returns.

If the base case was changed to n == 1 instead of n == 0, how would the call stack depth at step 4 change?

A It would be deeper

B It would be shallower

C It would be the same

D Recursion would not stop

💡 Hint

Check variable_tracker 'Call Stack Depth' and think when base case triggers.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion by returning a value (e.g., n==0 returns 1)
- Recursive Case: calls itself with smaller input (e.g., n * factorial(n-1))
Each call waits for the smaller call to finish before returning.
Without base case, recursion never ends.
Visualize call stack growing and shrinking.

Full Transcript

Recursion works by calling the same function inside itself with smaller inputs until it reaches a base case. The base case stops further calls and returns a value. Then each previous call uses that returned value to compute its own result and returns it. For example, factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0). At factorial(0), the base case returns 1. Then factorial(1) returns 1*1=1, factorial(2) returns 2*1=2, and factorial(3) returns 3*2=6. The call stack grows with each call and shrinks as calls return. This process ensures recursion ends and produces the correct result.

Practice

1. In a recursive function, what is the purpose of the base case?

easy

A. To increase the input size for the next call

B. To call the function again with a smaller input

C. To print the result of the recursion

D. To stop the recursion and prevent infinite calls

Solution

1. Step 1: Understand the base case role

   The base case is the condition that stops the recursion from continuing indefinitely.

2. Step 2: Differentiate from recursive case

   The recursive case calls the function again with smaller input, but the base case stops recursion.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option D

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case stops recursion to avoid infinite loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case increases input size
• Assuming base case prints output

2. Which of the following is the correct syntax for a recursive function in Rust that calculates factorial?

easy

A. fn factorial(n: u32) -> u32 { loop { factorial(n - 1) } }

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

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

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

Solution

1. Step 1: Check base case and recursive call

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } correctly uses if n == 0 { 1 } as base case and recursive multiplication.

2. Step 2: Identify syntax errors in other options

   fn factorial(n: u32) -> u32 { while n > 0 { n * factorial(n - 1) } } uses while loop incorrectly, C loops infinitely, D uses addition instead of multiplication.

3. Final Answer:

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

4. Quick Check:

   Correct base case and recursive call = fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } [OK]

Hint: Look for base case with if and recursive call with smaller input [OK]

Common Mistakes:

• Using loops instead of recursion
• Missing base case
• Wrong operation in recursive call

3. What is the output of this Rust code?

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

fn main() {
    println!("{}", sum(3));
}

medium

A. 3

B. 6

C. 0

D. Stack overflow error

Solution

1. Step 1: Trace recursive calls for sum(3)

   sum(3) = 3 + sum(2), sum(2) = 2 + sum(1), sum(1) = 1 + sum(0), sum(0) = 0.

2. Step 2: Calculate total sum

   sum(3) = 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum 1 to 3 = 6 [OK]

Hint: Add numbers down to zero using recursion [OK]

Common Mistakes:

• Confusing base case value
• Forgetting to add current n
• Expecting runtime error

4. Identify the error in this recursive Rust function that calculates factorial:

fn factorial(n: u32) -> u32 {
    n * factorial(n - 1)
}

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

medium

A. Missing base case to stop recursion

B. Wrong return type for factorial

C. Incorrect function name

D. Using multiplication instead of addition

Solution

1. Step 1: Check for base case presence

   The function lacks a base case like if n == 0 { 1 } to stop recursion.

2. Step 2: Understand recursion consequences

   Without base case, recursion never stops, causing stack overflow error.

3. Final Answer:

   Missing base case to stop recursion -> Option A

4. Quick Check:

   Base case missing = Missing base case to stop recursion [OK]

Hint: Always include base case to stop recursion [OK]

Common Mistakes:

• Assuming recursion stops automatically
• Ignoring base case importance
• Confusing return types

5. You want to write a recursive function in Rust to find the nth Fibonacci number. Which of the following correctly shows the base case and recursive case?

hard

A. if n == 0 { 0 } else if n == 1 { 1 } else { fib(n - 1) + fib(n - 2) }

B. if n == 1 { 0 } else if n == 2 { 1 } else { fib(n - 1) * fib(n - 2) }

C. if n == 0 { 1 } else { fib(n - 1) + fib(n - 2) }

D. if n == 0 { 0 } else { fib(n - 1) - fib(n - 2) }

Solution

1. Step 1: Identify correct base cases for Fibonacci

   Fibonacci sequence starts with fib(0) = 0 and fib(1) = 1, so base cases must reflect that.

2. Step 2: Check recursive case correctness

   Recursive case sums previous two Fibonacci numbers: fib(n-1) + fib(n-2).

3. Final Answer:

   if n == 0 { 0 } else if n == 1 { 1 } else { fib(n - 1) + fib(n - 2) } -> Option A

4. Quick Check:

   Correct base and recursive case for Fibonacci = if n == 0 { 0 } else if n == 1 { 1 } else { fib(n - 1) + fib(n - 2) } [OK]

Hint: Fibonacci base cases: 0 and 1; recursive case sums previous two [OK]

Common Mistakes:

• Wrong base case values
• Using multiplication or subtraction instead of addition
• Missing one base case