Recursion Base Case and Recursive Case in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in recursion?

The base case is the condition that stops the recursion. It prevents infinite calls by providing a simple answer without further recursion.

beginner

What is the recursive case in recursion?

The recursive case is the part where the function calls itself with a smaller or simpler input, moving towards the base case.

beginner

Why do we need both base case and recursive case in a recursive function?

The base case stops the recursion to avoid infinite loops, and the recursive case breaks the problem into smaller parts to solve it step by step.

intermediate

In Rust, how do you define a simple recursive function to calculate factorial?

Example in Rust: fn factorial(n: u32) -> u32 { if n == 0 { 1 // base case } else { n * factorial(n - 1) // recursive case } }

beginner

What happens if a recursive function has no base case?

Without a base case, the function calls itself forever, causing a stack overflow error and crashing the program.

What does the base case in recursion do?

A Creates a new variable

B Calls the function again

C Stops the recursion

D Prints the result

The base case stops the recursion by providing a simple answer without further calls.

In the factorial function, what is the base case?

A n == 1

B n < 0

C n > 0

D n == 0

The base case for factorial is when n == 0, returning 1.

What is the recursive case responsible for?

A Stopping recursion

B Calling the function with a smaller input

C Declaring variables

D Returning the final answer

The recursive case calls the function itself with a smaller or simpler input.

What error occurs if recursion has no base case?

A Stack overflow

B Syntax error

C Type error

D Runtime warning

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

Which Rust keyword is used to define a recursive function?

A fn

B loop

C let

D mut

The 'fn' keyword defines functions in Rust, including recursive ones.

Explain the roles of the base case and recursive case in a recursive function.

Think about how recursion starts and stops.

Write a simple Rust recursive function to calculate the factorial of a number and explain each part.

Use if-else to separate base and recursive cases.

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