Recursion Base Case and Recursive Case in DSA C

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine stacking boxes inside bigger boxes until you find the smallest box that you can open easily without opening any more boxes.

Function call stack:
main -> func(3) -> func(2) -> func(1) -> base case reached
Each arrow means a new call waiting for the smaller call to finish.

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find factorial(3) by breaking it down into smaller factorial calls until base case

Step 1: Call factorial(3), which calls factorial(2)

factorial(3) -> factorial(2) ↑ waiting

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

Step 2: Call factorial(2), which calls factorial(1)

factorial(3) -> factorial(2) -> factorial(1) ↑ waiting

Why: Keep breaking down until we reach the simplest case

Step 3: Call factorial(1), which hits base case and returns 1

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

Why: Base case stops recursion and starts returning answers

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

factorial(3) -> factorial(2) = 2

Why: Combine smaller answer to get bigger answer

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

factorial(3) = 6

Why: Final answer is built by combining all smaller answers

Result:

factorial(3) = 6

Annotated Code

DSA C

#include <stdio.h>

// Recursive function to calculate factorial
int factorial(int n) {
    if (n == 1) {
        return 1; // base case: factorial of 1 is 1
    }
    return n * factorial(n - 1); // recursive case: n * factorial of smaller number
}

int main() {
    int num = 3;
    int result = factorial(num);
    printf("factorial(%d) = %d\n", num, result);
    return 0;
}

if (n == 1) {

check for base case to stop recursion

return 1; // base case

return simple answer directly

return n * factorial(n - 1);

recursive call with smaller input to build answer

Output

factorial(3) = 6

Complexity Analysis

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

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

vs Alternative: Iterative approach uses a loop and constant space, but recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

Input is 1 (smallest valid input)

Function immediately returns 1 without further calls

DSA C

if (n == 1) {

Input is 0 or negative (not handled in this code)

Function will recurse infinitely or produce incorrect result

DSA C

No guard for n <= 0 in this code

When to Use This Pattern

When a problem can be broken into smaller versions of itself and has a simple stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and program crash
Fix: Always include a base case that stops recursion

Mistake: Base case returns wrong value, leading to incorrect final answer
Fix: Ensure base case returns the correct simple answer

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. What is the purpose of the base case in a recursive function?

easy

A. To call the function again with a smaller input

B. To stop the recursion and prevent infinite calls

C. To increase the input size for the next call

D. To print the result of the recursion

Solution

1. Step 1: Understand what recursion does

   Recursion calls the same function repeatedly with smaller inputs.

2. Step 2: Identify the role of the base case

   The base case stops the recursion by providing a condition where no further calls happen.

3. Final Answer:

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

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 calls function again
• Ignoring the need for a stopping condition

2. Which of the following is the correct syntax for a base case in a recursive function in C?

easy

A. if (n == 0) return 1;

B. while (n > 0) callFunction(n-1);

C. for (int i=0; i

D. return callFunction(n+1);

Solution

1. Step 1: Identify base case syntax

   The base case uses an if condition to check when to stop recursion.

2. Step 2: Check each option

   if (n == 0) return 1; uses if (n == 0) return 1; which correctly stops recursion. Others use loops or increase n, which are incorrect.

3. Final Answer:

   if (n == 0) return 1; -> Option A

4. Quick Check:

   Base case uses if condition [OK]

Hint: Base case uses if condition to stop recursion [OK]

Common Mistakes:

• Using loops instead of base case
• Increasing input instead of decreasing
• Missing return statement in base case

3. What is the output of the following C code?

int factorial(int n) {
  if (n == 0) return 1;
  else return n * factorial(n - 1);
}

int main() {
  printf("%d", factorial(3));
  return 0;
}

medium

A. 6

B. 9

C. 3

D. 0

Solution

1. Step 1: Trace factorial(3) calls

   factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0).

2. Step 2: Calculate return values

   factorial(0) = 1; factorial(1) = 1*1=1; factorial(2) = 2*1=2; factorial(3) = 3*2=6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   3! = 6 [OK]

Hint: Factorial n! = n*(n-1)! with base case 0! = 1 [OK]

Common Mistakes:

• Not returning 1 for factorial(0)
• Multiplying incorrectly
• Confusing output with input

4. Identify the error in this recursive function that calculates the sum of numbers from 1 to n:

int sum(int n) {
  if (n == 1) return 1;
  else return n + sum(n);
}

medium

A. Base case condition is incorrect

B. Missing return statement

C. Function should not be recursive

D. Recursive call does not reduce input

Solution

1. Step 1: Check base case

   Base case is if (n == 1) return 1; which is correct.

2. Step 2: Analyze recursive call

   Recursive call is sum(n) which does not reduce n, causing infinite recursion.

3. Final Answer:

   Recursive call does not reduce input -> Option D

4. Quick Check:

   Recursive input must decrease [OK]

Hint: Recursive calls must reduce input to reach base case [OK]

Common Mistakes:

• Calling sum(n) instead of sum(n-1)
• Wrong base case value
• Forgetting to return recursive call

5. You want to write a recursive function to reverse a string in C. Which of the following correctly shows the base case and recursive case?

hard

A. Base case: always call reverse with length-1; Recursive case: print string

B. Base case: if string length > 1, call reverse again; Recursive case: return string as is

C. Base case: if string is empty or length 1, return string; Recursive case: return last char + reverse(rest of string)

D. Base case: if string is empty, print string; Recursive case: add first char to end

Solution

1. Step 1: Understand base case for string reversal

   Base case stops recursion when string is empty or length 1, returning string as is.

2. Step 2: Understand recursive case

   Recursive case returns last character plus reversed substring excluding last character.

3. Final Answer:

   Base case: if string is empty or length 1, return string; Recursive case: return last char + reverse(rest of string) -> Option C

4. Quick Check:

   Base case stops; recursive case reduces string [OK]

Hint: Base case returns small string; recursive case reduces string size [OK]

Common Mistakes:

• Wrong base case condition
• Recursive case not reducing string length
• Confusing base and recursive cases