Recursion Base Case and Recursive Case in DSA Rust

Mental Model

Recursion solves a problem by breaking it into smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine folding a big paper until it becomes small enough to fit in your hand; the base case is when the paper is small enough to hold easily.

Problem -> Smaller Problem -> Even Smaller Problem -> Base Case (solved directly)
          ↑               ↑                  ↑
       recursive       recursive          stop here

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking down the problem recursively

Step 1: Call factorial(3), not base case, so call factorial(2)

factorial(3) -> factorial(2) -> ?

Why: We reduce the problem to a smaller one to solve it step by step

Step 2: Call factorial(2), not base case, so call factorial(1)

factorial(3) -> factorial(2) -> factorial(1) -> ?

Why: Keep breaking down until we reach the simplest problem

Step 3: Call factorial(1), base case reached, return 1

factorial(1) = 1

Why: Base case stops recursion and provides direct answer

Step 4: Return factorial(2) = 2 x factorial(1) = 2 x 1 = 2

factorial(2) = 2

Why: Combine smaller answers to build solution

Step 5: Return factorial(3) = 3 x factorial(2) = 3 x 2 = 6

factorial(3) = 6

Why: Final answer is built by combining all smaller results

Result:

factorial(3) = 6

Annotated Code

DSA Rust

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

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

if n == 0 || n == 1 {

check if we reached the simplest problem to stop recursion

return 1; // base case: stop recursion

return direct answer for base case

n * factorial(n - 1) // recursive case: reduce problem

call factorial on smaller input and combine result

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) due to the call stack holding n recursive calls

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

Edge Cases

Input n = 1 (smallest valid input)

Function immediately returns 1 without further recursion

DSA Rust

if n == 0 || n == 1 {

Input n = 0 (now handled in this code)

Function returns 1 immediately, correctly handling zero factorial

DSA Rust

if n == 0 || n == 1 {

When to Use This Pattern

When a problem can be solved by solving smaller versions of itself and combining results, look for recursion with a clear base case.

Common Mistakes

Mistake: Missing or incorrect base case causing infinite recursion
Fix: Always define a base case that stops recursion with a direct answer

Mistake: Not reducing the problem size in recursive call
Fix: Make sure each recursive call works on a smaller or simpler input

Summary

Recursion solves problems by calling itself with smaller inputs until a simple base case is reached.

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

The base case stops recursion, and the recursive case breaks the problem down step by step.

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