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.