Recursion Base Case and Recursive Case in DSA Typescript

Mental Model

Recursion solves a problem by breaking it into smaller parts until it reaches a simple case it knows how to solve directly.

Analogy: Imagine opening a set of nested Russian dolls: you keep opening smaller dolls until you find the smallest one that cannot be opened further, then you start putting them back together.

Problem -> Smaller Problem -> Smaller Problem -> Base Case (solved directly)
          ↑               ↑               ↑
       Recursive Case  Recursive Case  Base Case

Dry Run Walkthrough

Input: Calculate factorial of 3 (3!) using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down recursively

Step 1: Call factorial(3), not base case, so call factorial(2)

factorial(3) -> factorial(2) -> ?

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

Step 2: Call factorial(2), not base case, so call factorial(1)

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

Why: Keep breaking down until we reach the simplest case

Step 3: Call factorial(1), base case reached, return 1

factorial(1) = 1

Why: Base case stops recursion and provides a direct answer

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

factorial(2) = 2

Why: Combine smaller solved parts to build the answer

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

factorial(3) = 6

Why: Final answer is built by combining all parts

Result:

factorial(3) = 6

Annotated Code

DSA Typescript

class Recursion {
  static factorial(n: number): number {
    if (n === 0 || n === 1) {
      return 1; // base case: stop recursion
    }
    return n * Recursion.factorial(n - 1); // recursive case: reduce problem
  }
}

// Driver code
const input = 3;
const result = Recursion.factorial(input);
console.log(`factorial(${input}) = ${result}`);

if (n === 0 || n === 1) { return 1; }

Check for base case to stop recursion and return direct answer

return n * Recursion.factorial(n - 1);

Recursive case: call factorial with smaller input to build solution

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) due to the call stack growing with each recursive call

vs Alternative: Iterative approach uses O(1) space but recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

Input is 1 (smallest factorial)

Returns 1 immediately as base case

DSA Typescript

if (n === 0 || n === 1) { return 1; }

Input is 0 (factorial of zero)

Returns 1 immediately as base case

DSA Typescript

if (n === 0 || n === 1) { return 1; }

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 stack overflow.
Fix: Always include a base case that stops recursion.

Mistake: Using incorrect base case value (e.g., n === 0 without handling) leads to errors.
Fix: Define base case carefully to cover smallest input correctly.

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 the function returns without calling itself again.

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:

• Thinking base case calls recursion again
• Confusing base case with recursive case
• Ignoring base case leads to infinite recursion

2. Which of the following is the correct syntax for a recursive function in TypeScript that calculates factorial?

easy

A. function factorial(n: number): number { if (n === 0) return 1; else return n * factorial(n - 1); }

B. function factorial(n: number): number { while (n > 0) return n * factorial(n - 1); }

C. function factorial(n: number): number { if (n === 1) return 0; else return n + factorial(n - 1); }

D. function factorial(n: number): number { return n * factorial(n + 1); }

Solution

1. Step 1: Check base case correctness

   function factorial(n: number): number { if (n === 0) return 1; else return n * factorial(n - 1); } uses if (n === 0) return 1; which is correct for factorial base case.

2. Step 2: Check recursive call correctness

   function factorial(n: number): number { if (n === 0) return 1; else return n * factorial(n - 1); } calls factorial(n - 1) and multiplies by n, which matches factorial definition.

3. Final Answer:

   function factorial(n: number): number { if (n === 0) return 1; else return n * factorial(n - 1); } -> Option A

4. Quick Check:

   Correct base and recursive case syntax = function factorial(n: number): number { if (n === 0) return 1; else return n * factorial(n - 1); } [OK]

Hint: Base case returns 1 for factorial, recursive calls with n-1 [OK]

Common Mistakes:

• Using while loop instead of recursion
• Wrong base case value
• Recursive call increasing n causing infinite recursion

3. What will be the output of this TypeScript code?

function sumTo(n: number): number {
  if (n === 0) return 0;
  return n + sumTo(n - 1);
}
console.log(sumTo(3));

medium

A. 6

B. 3

C. 0

D. Error

Solution

1. Step 1: Trace recursive calls

   sumTo(3) calls 3 + sumTo(2), sumTo(2) calls 2 + sumTo(1), sumTo(1) calls 1 + sumTo(0), sumTo(0) returns 0.

2. Step 2: Calculate return values

   sumTo(1) = 1 + 0 = 1, sumTo(2) = 2 + 1 = 3, sumTo(3) = 3 + 3 = 6.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Sum 1+2+3 = 6 [OK]

Hint: Add n plus sumTo(n-1) until base case 0 [OK]

Common Mistakes:

• Confusing base case return value
• Adding instead of multiplying
• Missing base case causing infinite recursion

4. Identify the error in this recursive function and select the fix.

function countdown(n: number): void {
  if (n === 0) return;
  console.log(n);
  countdown(n + 1);
}
countdown(3);

medium

A. Change console.log(n) to console.log(n - 1)

B. Add a base case for n === 1

C. Remove the base case to allow infinite recursion

D. Change countdown(n + 1) to countdown(n - 1)

Solution

1. Step 1: Analyze recursive call direction

   The function calls countdown(n + 1), which increases n, causing infinite recursion.

2. Step 2: Fix recursive call to decrease n

   Changing to countdown(n - 1) moves towards base case n === 0, stopping recursion.

3. Final Answer:

   Change countdown(n + 1) to countdown(n - 1) -> Option D

4. Quick Check:

   Recursive call must approach base case [OK]

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

Common Mistakes:

• Increasing input causing infinite recursion
• Missing or wrong base case
• Changing print statement instead of recursion

5. You want to write a recursive function flatten that takes a nested array of numbers (e.g., [1, [2, [3]], 4]) and returns a flat array [1, 2, 3, 4]. Which approach correctly uses base and recursive cases?

hard

A. Base case: always return input; Recursive case: never call flatten recursively

B. Base case: if input is number, return number; Recursive case: call flatten on input

C. Base case: if input is empty array, return empty array; Recursive case: for each element, if array, call flatten, else add element

D. Base case: if input is array, return input; Recursive case: if input is number, call flatten

Solution

1. Step 1: Define base case for empty array

   If the input array is empty, return an empty array to stop recursion.

2. Step 2: Define recursive case for nested arrays

   For each element, if it is an array, recursively call flatten; if not, add element to result.

3. Final Answer:

   Base case: if input is empty array, return empty array; Recursive case: for each element, if array, call flatten, else add element -> Option C

4. Quick Check:

   Empty array stops recursion, nested arrays flatten recursively [OK]

Hint: Empty array stops recursion; recurse on nested arrays [OK]

Common Mistakes:

• Wrong base case returning number instead of array
• Not checking element type before recursion
• Infinite recursion by missing base case