Recursion Base Case and Recursive Case in DSA Typescript - Deep Dive

Overview - Recursion Base Case and Recursive Case

What is it?

Recursion is a way a function calls itself to solve smaller parts of a problem. It has two main parts: the base case, which stops the recursion, and the recursive case, which breaks the problem into smaller pieces. Without these parts, the function would never stop or solve the problem. This concept helps solve problems that repeat in smaller steps, like counting down or searching through nested data.

Why it matters

Without recursion's base and recursive cases, programs could get stuck forever or crash. These parts let us write simple, clear solutions for complex problems that repeat in smaller forms. Recursion is used in many areas like sorting, searching, and working with trees or graphs. Understanding these parts helps you write safe and efficient code that solves problems step-by-step.

Where it fits

Before learning recursion base and recursive cases, you should understand functions and how they work. After this, you can learn about advanced recursion techniques like tail recursion, and then explore recursive data structures like trees and graphs.

Mental Model

Core Idea

Recursion solves a problem by stopping at a simple case and breaking the rest into smaller, similar problems.

Think of it like...

Imagine you have a stack of boxes to open. The base case is when you find the last box with a prize inside, so you stop opening more boxes. The recursive case is opening one box and then opening the smaller stack inside it, repeating until you reach the last box.

Recursion Function
┌─────────────────────────────┐
│ Call function with problem P │
└──────────────┬──────────────┘
               │
       ┌───────▼────────┐
       │ Is P simple?    │
       │ (Base Case)     │
       └───────┬────────┘
           Yes │ No
               │
       ┌───────▼────────┐
       │ Return answer   │
       └────────────────┘
               │
       ┌───────▼────────┐
       │ Break P into    │
       │ smaller problem │
       │ Call function   │
       └────────────────┘

Build-Up - 6 Steps

1

Foundation

Understanding What Recursion Is

Concept: Recursion means a function calls itself to solve smaller parts of a problem.

Think of recursion as a function that repeats itself with smaller inputs. For example, to count down from a number, the function calls itself with one less number until it reaches zero.

Result

You see how a function can repeat itself with smaller inputs to reach a simple answer.

Understanding that a function can call itself is the first step to grasping how recursion breaks problems down.

2

Foundation

Identifying the Base Case

Concept: The base case stops the recursion by giving a simple answer without calling itself again.

In recursion, the base case is like a stopping point. For example, when counting down, the base case is when the number reaches zero, and the function stops calling itself.

Result

The function stops repeating and returns a result when the base case is reached.

Knowing the base case prevents infinite loops and ensures the recursion ends safely.

3

Intermediate

Exploring the Recursive Case

🤔Before reading on: do you think the recursive case always reduces the problem size or can it sometimes increase it? Commit to your answer.

Concept: The recursive case breaks the problem into a smaller part and calls the function again with this smaller problem.

The recursive case is where the function calls itself with a smaller or simpler input. For example, to sum numbers from n down to 1, the function adds n to the sum of numbers from n-1 down to 1.

Result

The problem gets smaller with each call until it reaches the base case.

Understanding that the recursive case must reduce the problem size is key to making recursion work correctly.

4

Intermediate

Writing a Simple Recursive Function

🤔Before reading on: do you think a recursive function without a base case will work correctly or cause problems? Commit to your answer.

Concept: A recursive function must have both base and recursive cases to work properly.

Example in TypeScript: function factorial(n: number): number { if (n === 0) { // base case return 1; } else { // recursive case return n * factorial(n - 1); } } Calling factorial(3) calculates 3 * 2 * 1.

Result

factorial(3) returns 6.

Seeing both cases in code helps understand how recursion solves problems step-by-step.

5

Advanced

Tracing Recursive Calls Step-by-Step

🤔Before reading on: do you think the function calls happen all at once or one after another? Commit to your answer.

Concept: Recursion works by stacking calls and resolving them from the base case back up.

When factorial(3) is called: - factorial(3) waits for factorial(2) - factorial(2) waits for factorial(1) - factorial(1) waits for factorial(0) - factorial(0) returns 1 (base case) Then each call returns: - factorial(1) returns 1 * 1 = 1 - factorial(2) returns 2 * 1 = 2 - factorial(3) returns 3 * 2 = 6

Result

The final result is 6 after all calls return.

Understanding the call stack and return order clarifies how recursion unfolds and resolves.

6

Expert

Recognizing Risks Without Proper Base Cases

🤔Before reading on: do you think missing a base case causes a crash or just wrong answers? Commit to your answer.

Concept: Without a base case, recursion never stops and causes errors like stack overflow.

Example of missing base case: function infiniteRecursion(n: number): number { return infiniteRecursion(n - 1); } Calling infiniteRecursion(5) causes the program to crash because it never stops calling itself.

Result

Program crashes with a stack overflow error.

Knowing the critical role of base cases prevents serious runtime errors in recursive functions.

Under the Hood

When a recursive function calls itself, the program saves the current state (like local variables and where to return) on a call stack. Each new call adds a layer to this stack. When the base case is reached, the function returns a value, and the program removes layers from the stack one by one, completing each waiting call.

Why designed this way?

Recursion was designed to simplify problems that repeat in smaller forms. Using a call stack allows the program to remember where it left off in each call. Alternatives like loops can do similar work but recursion matches the problem's natural structure better, especially for nested or branching data.

Call Stack Example for factorial(3):

┌───────────────┐
│ factorial(0)  │ <- base case returns 1
├───────────────┤
│ factorial(1)  │ waits for factorial(0)
├───────────────┤
│ factorial(2)  │ waits for factorial(1)
├───────────────┤
│ factorial(3)  │ waits for factorial(2)
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: do you think recursion always needs a base case to work? Commit to yes or no.

Common Belief: Some think recursion can work without a base case if the problem is small.

Reality: Every recursive function must have a base case to stop; otherwise, it causes infinite calls and crashes.

Why it matters: Missing base cases lead to program crashes and wasted resources, making recursion unsafe.

Quick: do you think the recursive case can increase the problem size? Commit to yes or no.

Common Belief: People sometimes believe the recursive case can make the problem bigger to solve it.

Reality: The recursive case must always reduce the problem size to guarantee the function reaches the base case.

Why it matters: Increasing problem size causes infinite recursion and stack overflow errors.

Quick: do you think recursion is always slower than loops? Commit to yes or no.

Common Belief: Many believe recursion is always less efficient than loops.

Reality: While recursion can be slower due to call overhead, some problems are naturally simpler and clearer with recursion, and some languages optimize tail recursion to match loop speed.

Why it matters: Misunderstanding this can lead to avoiding recursion even when it makes code clearer and easier to maintain.

Expert Zone

1

Tail recursion optimization can convert some recursive calls into loops internally, saving memory and preventing stack overflow.

2

Mutual recursion happens when two or more functions call each other recursively, which requires careful base cases to avoid infinite loops.

3

Recursion depth limits vary by language and environment, so deep recursion can cause crashes unless optimized or rewritten iteratively.

When NOT to use

Avoid recursion when the problem size is very large and the language does not optimize tail calls, as this can cause stack overflow. Instead, use iterative loops or explicit stacks to manage state.

Production Patterns

Recursion is widely used in parsing expressions, traversing trees and graphs, implementing divide-and-conquer algorithms like quicksort and mergesort, and solving dynamic programming problems with memoization.

Connections

Call Stack

Recursion relies on the call stack to keep track of function calls and returns.

Understanding the call stack helps explain why recursion uses memory and how base cases stop the stack from growing infinitely.

Divide and Conquer Algorithms

Recursion naturally implements divide and conquer by breaking problems into smaller parts.

Knowing recursion clarifies how algorithms like mergesort split and merge data efficiently.

Mathematical Induction

Recursion mirrors mathematical induction by proving a base case and assuming smaller cases to solve bigger ones.

Seeing recursion as induction helps understand why base and recursive cases are essential for correctness.

Common Pitfalls

#1 Forgetting the base case causes infinite recursion.

Wrong approach:

function countdown(n: number): void {
console.log(n);
countdown(n - 1); // no base case
}

Correct approach:

function countdown(n: number): void {
if (n <= 0) return; // base case
console.log(n);
countdown(n - 1);
}

Root cause:

Not including a stopping condition means the function never knows when to stop calling itself.

#2 Recursive case does not reduce problem size, causing infinite calls.

Wrong approach:

function sum(n: number): number {
if (n === 0) return 0;
return n + sum(n + 1); // problem size increases
}

Correct approach:

function sum(n: number): number {
if (n === 0) return 0;
return n + sum(n - 1); // problem size decreases
}

Root cause:

Calling with larger inputs instead of smaller ones prevents reaching the base case.

#3 Assuming recursion is always the best solution.

Wrong approach:

Using recursion for very large inputs without optimization:
function fibonacci(n: number): number {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

Correct approach:

Use iteration or memoization to optimize:
function fibonacci(n: number): number {
const memo = [0, 1];
for (let i = 2; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
}

Root cause:

Not considering performance and stack limits leads to inefficient or crashing code.

Key Takeaways

Recursion solves problems by calling itself with smaller inputs until reaching a simple base case that stops the calls.

The base case is essential to prevent infinite recursion and program crashes.

The recursive case must always reduce the problem size to guarantee the function eventually stops.

Understanding how the call stack manages recursive calls helps explain recursion's memory use and behavior.

Recursion is powerful for problems with natural repetition but requires careful design to avoid pitfalls like infinite loops and inefficiency.

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