Recursion, Searching and Basic Problem Solving

Introduction

Many software tasks become manageable when a programmer identifies a repeated subproblem or exploits structure in the input. Recursion expresses a problem in terms of smaller instances of itself. Searching algorithms locate information efficiently. Problem-solving patterns such as divide-and-conquer, two pointers, sliding windows and prefix sums transform apparently different tasks into recognizable computational forms.

These techniques are especially relevant to full stack development. They support hierarchical user interfaces, file and category trees, database-like lookup, event-stream analysis, validation, routing and API performance. Their correct use nevertheless requires careful attention to call-stack limits, sortedness assumptions, index boundaries and numeric behavior.

Learning Objectives

After completing this chapter, students should be able to:

• explain stack frames and the execution of recursive calls;
• formulate recursive algorithms with valid base cases and progress conditions;
• compare ordinary recursion, tail recursion and iteration;
• prevent uncontrolled recursion and stack overflow;
• implement and analyze linear and binary search;
• maintain loop invariants and avoid boundary errors;
• apply divide-and-conquer, two-pointer, sliding-window and prefix-sum techniques;
• select techniques according to input structure and operational requirements.

1. Recursion and the Call Stack

1.1 Recursive formulation

A recursive function solves a problem by invoking itself on a smaller or simpler instance. A correct recursive formulation requires:

1. Base case: an input for which the answer is returned directly.
2. Recursive case: a reduction to one or more smaller instances.
3. Progress: every recursive path must eventually reach a base case.
4. Combination rule: partial answers must be combined correctly.

For a non-negative integer n, factorial is defined by:

Here, n is a dimensionless non-negative integer. The recurrence is not defined by this formula for negative integers. For example:

A JavaScript implementation using BigInt is:

function requireNonNegativeInteger(n) {
  if (!Number.isSafeInteger(n) || n < 0) {
    throw new RangeError("n must be a non-negative safe integer");
  }
}

function factorial(n) {
  requireNonNegativeInteger(n);

  function compute(k) {
    if (k === 0) return 1n;
    return BigInt(k) * compute(k - 1);
  }

  return compute(n);
}

console.log(factorial(4)); // 24n

Validation occurs before recursion begins. BigInt avoids the ordinary Number type’s loss of integer precision for sufficiently large factorials, although it does not prevent call-stack exhaustion.

1.2 Stack frames

Each function call creates an activation record, commonly called a stack frame. A frame normally records parameters, local variables, the return address and temporary evaluation state. Frames are placed on the call stack in last-in, first-out order.

For factorial(4), calls descend through factorial(0). The base case returns 1n to factorial(1), not directly to factorial(2). The remaining calls then unwind in reverse order.

Figure: The complete call sequence includes factorial(0), whose result returns first to factorial(1).

If each call performs constant work apart from its recursive call, execution time satisfies:

Here, T(n) is execution cost for input n, while c and d are constants under a unit-cost model. Expanding the recurrence gives T(n) = d + nc, hence time complexity is Θ(n). Because n + 1 calls coexist at the deepest point, auxiliary stack space is also Θ(n).

1.3 Recursion on structural data

Recursion is particularly natural when data is recursively defined. A file system contains files and directories, while each directory can contain further directories. Similar structures occur in document object models, category trees and abstract syntax trees.

function countNodes(node) {
  if (!node || !Array.isArray(node.children)) return 1;

  let total = 1;
  for (const child of node.children) {
    total += countNodes(child);
  }
  return total;
}

For malformed cyclic data, this function would not terminate. Production code traversing graph-like objects should maintain a visited set. Tree recursion is safe only when the structure is genuinely acyclic and its depth is acceptable.

2. Tail Recursion, Iteration and Stack Safety

2.1 Tail recursion

A call is in tail position when its result is returned directly, with no pending operation. Factorial can use an accumulator:

function factorialTail(n) {
  requireNonNegativeInteger(n);

  function compute(k, accumulator) {
    if (k === 0) return accumulator;
    return compute(k - 1, BigInt(k) * accumulator);
  }

  return compute(n, 1n);
}

This implementation validates negative, fractional and unsafe numeric inputs before recursion. Consequently, invalid input cannot cause indefinite descent through successively smaller negative or fractional values.

Although tail recursion can theoretically be executed in constant stack space through tail-call optimization, developers must not assume that every JavaScript runtime performs this optimization. A tail-recursive function can therefore still overflow the call stack.

2.2 Iterative conversion

The corresponding iterative algorithm is usually safer in JavaScript:

function factorialIterative(n) {
  requireNonNegativeInteger(n);

  let result = 1n;
  for (let k = 2; k <= n; k++) {
    result *= BigInt(k);
  }
  return result;
}

All three implementations take Θ(n) multiplication steps. Ordinary and unoptimized tail recursion use Θ(n) stack space, whereas iteration uses Θ(1) auxiliary control space. The growing BigInt result itself still consumes memory, so constant auxiliary control space does not mean constant total storage for arbitrarily large outputs.

2.3 Preventing stack overflow

A stack overflow occurs when nested calls exceed the runtime’s stack capacity. The exact limit is environment-dependent and should not be hard-coded as a universal value.

Recommended controls include:

• validate inputs before recursion;
• prove that each call progresses toward a base case;
• use iteration for potentially deep linear recursion;
• use an explicit stack for deep tree or graph traversal;
• track visited nodes when cycles are possible;
• impose depth or resource limits on untrusted data;
• test degenerate inputs, such as a tree shaped like a linked list.

An explicit stack moves traversal state to heap-managed storage:

function countNodesIterative(root) {
  if (!root) return 0;

  let count = 0;
  const stack = [root];

  while (stack.length > 0) {
    const node = stack.pop();
    count++;
    if (Array.isArray(node.children)) {
      for (const child of node.children) stack.push(child);
    }
  }
  return count;
}

3. Searching

3.1 Linear search

Linear search examines elements sequentially until it finds a match or reaches the end.

function linearSearch(values, target) {
  for (let i = 0; i < values.length; i++) {
    if (values[i] === target) return i;
  }
  return -1;
}

For an array of length n, the best case takes one comparison. The worst case takes n comparisons, giving Θ(n) time and Θ(1) auxiliary space. It works on unsorted data and is often appropriate for small collections or one-off searches.

Linear search is also suitable for objects when equality is defined by a key rather than object identity:

function findUserById(users, id) {
  for (let i = 0; i < users.length; i++) {
    if (users[i].id === id) return i;
  }
  return -1;
}

3.2 Binary search

Binary search requires data sorted according to the same ordering used by the search. It repeatedly eliminates approximately half of the remaining interval.

function binarySearch(sortedValues, target) {
  let low = 0;
  let high = sortedValues.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (sortedValues[mid] === target) return mid;
    if (sortedValues[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

The midpoint expression avoids the overflow risk associated with adding two very large integer indices in fixed-width languages. JavaScript arrays have other practical size limits, but the form remains portable best practice.

The loop maintains this invariant:

If the target exists in the array, then it lies within the inclusive interval from low to high.

When sortedValues[mid] < target, all indices at or below mid can be discarded, so low becomes mid + 1. Using low = mid would sometimes fail to shrink the interval.

For n ≥ 1, after k halvings the candidate count is at most approximately n/2^k. The process finishes when this count falls below one, so k grows logarithmically with n. The maximum number of loop iterations is:

Thus binary search takes O(log₂ n) time and the iterative implementation uses Θ(1) auxiliary space.

3.3 Boundary variants

Many real tasks require the first or last occurrence rather than any occurrence. The following lower-bound algorithm returns the first index whose value is greater than or equal to the target. If no such element exists, it returns sortedValues.length.

function lowerBound(sortedValues, target) {
  let low = 0;
  let high = sortedValues.length; // half-open interval [low, high)

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (sortedValues[mid] < target) low = mid + 1;
    else high = mid;
  }

  return low;
}

The half-open interval [low, high) simplifies insertion-point logic. For [2, 4, 4, 7], lowerBound(array, 4) returns 1, while lowerBound(array, 5) returns 3.

Sorting solely to perform one search may cost more than linear search. For repeated queries, however, sorting once or maintaining an index may be worthwhile.

4. Reusable Problem-Solving Techniques

4.1 Divide-and-conquer

Divide-and-conquer algorithms follow three stages:

1. divide a problem into smaller subproblems;
2. solve the subproblems, often recursively;
3. combine their results.

Binary search uses this principle but follows only one subproblem. Merge sort solves both halves and combines them by merging. Its standard recurrence is:

This expression assumes n is a power of two for convenient analysis, the two subproblems have equal size, and merging costs cn for constant c. There are log₂ n levels, each performing Θ(n) aggregate merge work, so total time is Θ(n log n). Non-power-of-two sizes use floor and ceiling partitions but retain the same asymptotic bound.

Divide-and-conquer is effective when subproblems are substantially smaller and combination is efficient. It may be unsuitable when recursion overhead dominates tiny inputs or when overlapping subproblems cause repeated work; dynamic programming may then be preferable.

4.2 Two pointers

The two-pointer technique maintains two indices whose movements eliminate impossible candidates. Consider determining whether a sorted numeric array contains two values with a given sum.

function hasPairWithSum(sortedValues, target) {
  let left = 0;
  let right = sortedValues.length - 1;

  while (left < right) {
    const sum = sortedValues[left] + sortedValues[right];
    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }

  return false;
}

For [1, 3, 4, 6, 8, 10] and target 14, the algorithm progresses from 1 + 10 = 11 to 3 + 10 = 13, and then to 4 + 10 = 14. It succeeds in three iterations.

Correctness depends on sorted order. If the sum is too small, moving the right pointer left cannot increase it, while moving the left pointer right can. Each pointer moves at most n − 1 positions, so time is Θ(n) and auxiliary space is Θ(1).

Other uses include removing duplicates from sorted arrays, merging sequences and partitioning data. The pointer movement rule must always be justified by an invariant rather than guessed.

4.3 Sliding windows

A sliding window tracks a contiguous range and reuses information when the range moves. For a fixed window of width k, the maximum sum can be found without recomputing every sum.

function maxFixedWindowSum(values, k) {
  if (!Number.isInteger(k) || k <= 0 || k > values.length) {
    throw new RangeError("k must be between 1 and values.length");
  }

  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += values[i];

  let best = windowSum;
  for (let right = k; right < values.length; right++) {
    windowSum += values[right] - values[right - k];
    best = Math.max(best, windowSum);
  }
  return best;
}

For [2, 1, 5, 1, 3, 2] and k = 3, the window sums are 8, 7, 9 and 6; the maximum is 9 from [5, 1, 3].

A variable-size window can solve problems such as finding the longest contiguous segment whose sum does not exceed a threshold. The common shrink-when-too-large method requires non-negative elements. With negative values, removing an element does not necessarily reduce the sum, so the monotonic reasoning fails.

When each element enters and leaves a valid window at most once, total time is Θ(n), not Θ(n²), even though one loop may be nested inside another.

4.4 Prefix sums

Prefix sums precompute cumulative totals so that range-sum queries can be answered in constant time. For an array a of length n, define a prefix array P of length n + 1 by:

For inclusive indices 0 ≤ l ≤ r < n, the range sum is:

The subtraction works because both prefixes contain all elements before l, which cancel.

function buildPrefixSums(values) {
  const prefix = new Array(values.length + 1).fill(0);
  for (let i = 0; i < values.length; i++) {
    prefix[i + 1] = prefix[i] + values[i];
  }
  return prefix;
}

function rangeSum(prefix, left, right) {
  if (!Number.isInteger(left) || !Number.isInteger(right) ||
      left < 0 || right < left || right + 1 >= prefix.length) {
    throw new RangeError("invalid inclusive range");
  }
  return prefix[right + 1] - prefix[left];
}

For a = [3, -1, 4, 2], the prefix array is [0, 3, 2, 6, 8]. Therefore, the sum from index 1 through 3 is P[4] − P[1] = 8 − 3 = 5, matching −1 + 4 + 2 = 5.

Building the prefix array takes Θ(n) time and space; each subsequent range query takes Θ(1). Prefix sums support negative values, unlike some variable-window methods. They are most suitable when the underlying array is static or rarely updated. Frequent updates may justify a Fenwick tree or segment tree.

5. Selecting an Appropriate Technique

Technique selection must include preprocessing costs. Binary search is fast only after sorting or indexing. Prefix sums accelerate queries but require extra memory and rebuilding after changes. A hash table may offer expected constant-time equality lookup but does not replace binary search for ordering questions such as lower bounds.

6. Applied Case: API Request Monitoring

Background

The following is an illustrative case. A full stack team operates an online learning platform. Each service instance emits request records containing a timestamp and response duration. Within each daily file, records are sorted by timestamp.

Problem

Operations staff need to:

1. locate the first request at or after a given timestamp;
2. compute request-duration totals for many intervals;
3. detect the busiest fixed five-minute interval;
4. avoid failures when importing deeply nested metadata supplied by clients.

Analysis

A linear scan would answer each timestamp query in Θ(n) time. Because records are sorted, lower-bound binary search can locate the first qualifying record in Θ(log n).

If each query asks for the total duration between record indices, a prefix sum of durations supports each total in Θ(1) after Θ(n) preprocessing. If timestamps are irregular, binary search first converts time boundaries into index boundaries.

For fixed-duration time windows, two timestamp pointers can maintain a half-open interval. As the right boundary advances, records older than five minutes are removed from the left. This is a time-based sliding window rather than a fixed-number-of-records window.

Client metadata may be thousands of levels deep or cyclic. Recursive traversal is therefore replaced with an explicit stack and a WeakSet or Set of visited objects. A maximum-node policy limits resource consumption.

Approach

The processing pipeline is:

1. validate that timestamps are ordered and durations are finite, non-negative numbers;
2. build a duration prefix array;
3. use lowerBound to find interval boundaries;
4. calculate totals by subtracting prefix values;
5. use a sliding window for peak five-minute traffic;
6. traverse metadata iteratively with cycle detection and resource limits.

Suppose durations in milliseconds are [120, 80, 200, 100, 150]. The prefix array is [0, 120, 200, 400, 500, 650]. The total for records at indices 1 through 3 is:

The units remain milliseconds because prefix construction and subtraction use values with the same unit.

Outcome

Repeated interval queries become independent of interval length. Timestamp lookup becomes logarithmic, while the sliding-window scan remains linear in the number of records. Explicit traversal prevents call-stack dependence and gives the service control over maximum work.

Learning Points

• Combining techniques is often more effective than seeking one universal algorithm.
• Input guarantees, particularly sortedness, must be verified or established.
• Half-open intervals reduce ambiguity when translating timestamps to indices.
• Resource controls are part of algorithm design for public-facing services.
• Units and numeric limits matter in operational analytics; very large totals may require BigInt or a database numeric type.

7. Common Errors, Governance and Contemporary Practice

Boundary and correctness errors

Frequent defects include:

• omitting or misdefining a recursive base case;
• failing to reduce the recursive input;
• applying binary search to unsorted data;
• mixing inclusive and exclusive boundaries;
• using left <= right when a two-pointer task requires distinct elements and therefore left < right;
• reading beyond an array’s valid indices;
• using a variable sliding window where negative values invalidate monotonic movement;
• computing prefix[right] - prefix[left] for an inclusive query instead of prefix[right + 1] - prefix[left].

Assertions, property-based tests and boundary-focused unit tests are valuable. Test empty arrays, one-element arrays, duplicate values, absent targets, first and last positions, invalid ranges and maximum expected depth.

Security and governance

Algorithms process data; they do not establish authorization. A fast lookup must still enforce access-control and tenant-isolation rules. Public APIs should limit input sizes and recursive nesting to resist denial-of-service attacks. Logs used for algorithm evaluation may contain personal information and should follow retention, minimization and access policies.

Data-dependent execution can also reveal information through timing in security-sensitive code. Standard linear or binary search should not be assumed constant-time. Authentication and cryptographic comparisons should use vetted platform facilities rather than improvised search logic.

Technology and AI-assisted development

Modern profilers can reveal excessive recursion, allocation and comparison costs. Static analyzers can detect unreachable base cases or suspicious index expressions. AI coding tools can suggest algorithms, but generated implementations must be checked against preconditions and tested at boundaries. In particular, a plausible binary search can still contain a one-character update error that prevents termination.

Contemporary production systems frequently use library search, database indexes, distributed query engines and streaming frameworks. Understanding the underlying algorithms remains essential because developers must interpret complexity, choose indexes, diagnose latency and recognize when an abstraction’s assumptions are violated.

Chapter Summary

Recursion represents a problem through smaller instances and is executed through stack frames. Correct recursion requires a reachable base case, progress and a valid combination rule. Tail recursion does not guarantee constant stack use in JavaScript, so iteration or an explicit stack is preferable when depth may be large. Input validation is essential, including for accumulator-based recursive functions.

Linear search works on unsorted data in linear time. Binary search achieves logarithmic time on correctly sorted random-access data by preserving and shrinking a candidate interval. Lower-bound variants illustrate how half-open intervals support reliable boundary processing.

Divide-and-conquer decomposes problems, two pointers exploit monotonic movement, sliding windows reuse work across contiguous ranges, and prefix sums answer static range queries through cumulative preprocessing. Each technique depends on explicit assumptions. Professional implementation combines complexity analysis with validation, boundary testing, numeric awareness, security controls and resource governance.

Key Terms

Activation record: Runtime information stored for one function invocation.

Base case: A recursive condition that returns without making another recursive call.

Binary search: A search that repeatedly halves a sorted candidate interval.

Call stack: The last-in, first-out structure that manages active function calls.

Divide-and-conquer: A method that divides a problem, solves subproblems and combines results.

Half-open interval: A range that includes its lower boundary but excludes its upper boundary.

Invariant: A property that remains true throughout an algorithm’s execution.

Linear search: Sequential examination of elements until a target is found or input ends.

Lower bound: The first position containing a value greater than or equal to a target.

Prefix sum: A cumulative total used to answer range-sum queries efficiently.

Progress condition: The requirement that recursive calls move toward a base case.

Recurrence relation: An equation expressing cost or value in terms of smaller inputs.

Recursion: Solving a problem through calls on smaller instances of the same problem.

Sliding window: A maintained contiguous range whose state is updated incrementally.

Stack overflow: Failure caused by exceeding available call-stack capacity.

Tail call: A function call whose result is immediately returned without pending work.

Tail-call optimization: Reuse of a stack frame for an eligible tail call.

Two-pointer technique: Coordinated movement of two indices to eliminate candidates efficiently.

Review Questions

Short Answer Questions

1. What four properties are required for a correct recursive formulation?
2. Why can tail-recursive JavaScript code still cause stack overflow?
3. State the sortedness requirement for binary search.
4. What does lowerBound return when every array element is smaller than the target?
5. Why is an extra zero stored at the beginning of a prefix-sum array?

Long Answer Questions

1. Explain the complete call and return sequence for factorial(4), including the role of factorial(0).
2. Compare ordinary recursion, tail recursion and iteration in terms of readability, execution and stack-space requirements.
3. Derive the logarithmic time complexity of binary search and explain its loop invariant.
4. Compare two pointers, sliding windows and prefix sums, emphasizing assumptions and suitable problem types.
5. Discuss how validation, resource limits and boundary testing improve the reliability and security of public-facing algorithms.

Analytical / Application Questions

1. Design an algorithm that returns the first and last positions of a target in a sorted array containing duplicates. Analyze its complexity and identify boundary cases.
2. A server stores one million hourly measurements and receives frequent static range-sum queries. Compare direct summation, prefix sums and a tree-based structure if updates are later introduced.
3. Given a deeply nested JSON-like structure that may contain cycles, design a safe iterative traversal. Specify its data structures, termination controls and complexity.

Multiple Choice Questions with Answers

Question 1

In the recursive evaluation of factorial(4) with base case factorial(0) = 1, which function receives the base-case result first?

A. factorial(4)

B. factorial(3)

C. factorial(2)

D. factorial(1)

Correct Answer: D. factorial(1)

Question 2

Why does factorialTail validate that its input is a non-negative integer before recursion?

A. To ensure the recursive argument progresses toward the base case

B. To make every multiplication constant-time

C. To guarantee JavaScript performs tail-call optimization

D. To convert the result automatically to Number

Correct Answer: A. To ensure the recursive argument progresses toward the base case

Question 3

What is the worst-case time complexity of linear search over an array of length n?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n log n)

Correct Answer: C. Θ(n)

Question 4

Which condition is essential for the numeric binary-search implementation in the chapter?

A. The array must contain no duplicate values

B. The array must be sorted using the same ordering as the search

C. The target must occur exactly once

D. The array length must be a power of two

Correct Answer: B. The array must be sorted using the same ordering as the search

Question 5

For the sorted array [2, 4, 4, 7], what does lowerBound(array, 5) return?

A. 1

B. 2

C. 3

D. 4

Correct Answer: C. 3

Question 6

For [1, 3, 4, 6, 8, 10], which pair is found by the two-pointer algorithm when the target sum is 14?

A. 1 and 10

B. 3 and 10

C. 4 and 10

D. 6 and 10

Correct Answer: C. 4 and 10

Question 7

For [2, 1, 5, 1, 3, 2], what is the maximum sum of any contiguous window of width 3?

A. 7

B. 8

C. 9

D. 10

Correct Answer: C. 9

Question 8

Given prefix sums [0, 3, 2, 6, 8], what is the inclusive sum from original-array index 1 through 3?

A. 2

B. 5

C. 6

D. 8

Correct Answer: B. 5

Question 9

Why can the usual shrink-when-too-large sliding-window method fail when values may be negative?

A. Removing the left value does not necessarily decrease the sum

B. Negative values cannot be represented in arrays

C. The window must always have a fixed width

D. Prefix sums cannot contain negative totals

Correct Answer: A. Removing the left value does not necessarily decrease the sum

Question 10

Which approach is generally safest for traversing an extremely deep tree in JavaScript when recursion depth is unbounded?

A. Recursive traversal without validation

B. Tail recursion with assumed optimization

C. Binary search over the child nodes

D. Iterative traversal using an explicit stack

Correct Answer: D. Iterative traversal using an explicit stack