Recursion Base Case and Recursive Case in DSA Rust - Time & Space Complexity

Time Complexity: Recursion Base Case and Recursive Case

O(n)

Understanding Time Complexity

When using recursion, it is important to understand how the function repeats itself and when it stops.

We want to know how the number of steps grows as the input gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code calculates the factorial of a number using recursion with a base case and a recursive case.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The function calls itself with a smaller number each time.
• How many times: It repeats until the number reaches zero, so n times.

How Execution Grows With Input

Each call waits for the next call with a smaller number until it reaches zero.

Input Size (n)	Approx. Operations
10	About 10 calls
100	About 100 calls
1000	About 1000 calls

Pattern observation: The number of steps grows directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line as the input number gets bigger.

Common Mistake

[X] Wrong: "Recursion always means exponential time because it repeats a lot."

[OK] Correct: Here, the recursion only happens once per call, so it grows linearly, not exponentially.

Interview Connect

Understanding how base and recursive cases affect time helps you explain your code clearly and shows you know how recursion works efficiently.

Self-Check

"What if the recursive case called the function twice instead of once? How would the time complexity change?"

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