Why Recursion Base Case and Recursive Case in DSA Rust?

The Big Idea

What if you could solve huge problems by solving tiny pieces again and again until done?

The Scenario

Imagine trying to solve a big puzzle by yourself without breaking it into smaller parts. You keep trying to solve the whole puzzle at once, getting overwhelmed and stuck.

The Problem

Without a clear stopping point, you might keep repeating the same steps endlessly or get confused about when to stop. This makes solving the problem slow and error-prone.

The Solution

Recursion breaks a big problem into smaller, easier problems. The base case tells when to stop, and the recursive case breaks the problem down step-by-step, making the solution simple and clear.

Before vs After

✗ Before

fn factorial(n: u32) -> u32 {
    let mut result = 1;
    for i in 1..=n {
        result *= i;
    }
    result
}

✓ After

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

What It Enables

It enables solving complex problems by breaking them into simple, repeatable steps that naturally stop at the right moment.

Real Life Example

Think of folding a big map repeatedly until it becomes small enough to fit in your pocket. Each fold is like a recursive step, and when the map is small enough, you stop folding -- that's the base case.

Key Takeaways

Recursion splits problems into smaller parts.

The base case stops the recursion.

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