Unit 3: Recursion and Advanced Techniques - Subjective Questions

Recursion is a programming technique in which a function solves a problem by calling itself on a smaller instance of the same problem.

A recursive solution has two essential components:

• Base condition: Stops further recursive calls and returns a directly known result.
• Recursive case: Reduces the original problem and invokes the function on a smaller input.

For example, factorial is defined as:

A recursive implementation is:

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

For factorial(4), the calls continue with 4, 3, 2, 1, and 0. After reaching the base condition, the calls return in reverse order to produce .

A base condition is the condition under which a recursive function returns without making another recursive call. It identifies the smallest problem instance whose answer is already known.

A correct base condition must be:

• Reachable: Every valid sequence of recursive calls should eventually reach it.
• Correct: It must return the proper result for the smallest input.
• Complete: It should cover all necessary terminal cases.

If the base condition is missing or unreachable, recursion continues until the call stack is exhausted, causing a stack overflow. If it returns an incorrect value, that error propagates through all pending calls. A poorly chosen base condition may also fail for boundary inputs such as zero, empty arrays, or negative values.

For factorial, n == 0 is a valid base condition because , and repeatedly reducing a positive by one eventually reaches zero.

A systematic recursive approach consists of the following steps:

• Define what the recursive function represents.
• Identify the smallest input and its direct answer.
• Reduce the current problem to one or more smaller instances.
• Assume the recursive calls correctly solve those smaller instances.
• Combine their results to obtain the current answer.
• Verify that every call moves toward a base condition.

Let represent the sum of array elements from index to the end:

Pseudocode:

arraySum(A, i):
    if i == length(A):
        return 0
    return A[i] + arraySum(A, i + 1)

The base case handles an empty suffix. Each call advances the index, so termination is guaranteed. The time complexity is and the recursion stack requires auxiliary space.

A classic recursive approach directly expresses a problem through smaller instances of itself. Examples include factorial, tree traversal, divide-and-conquer algorithms, and naive Fibonacci computation. Such solutions are often concise and closely match mathematical definitions.

Modern techniques improve performance or reliability in several ways:

• Memoization: Stores results of repeated subproblems, converting naive Fibonacci from time to time.
• Dynamic programming: Evaluates states iteratively, often avoiding call-stack overhead.
• Explicit stacks: Simulate recursive execution when recursion depth may be large.
• Tail-call optimization: Reuses a stack frame for eligible tail calls when supported by the language.
• Trampolining: Represents each recursive step as a deferred computation executed by a loop.
• Hybrid algorithms: Use recursion for large partitions and iteration for small partitions.

Classic recursion prioritizes clarity and structural correspondence. Modern approaches preserve that structure while controlling repeated work, stack usage, and practical runtime limits.

Direct recursion occurs when a function calls itself directly:

countdown(n):
    if n == 0:
        return
    countdown(n - 1)

Indirect recursion occurs when functions call one another cyclically. For example, isEven calls isOdd, which calls isEven:

isEven(n):
    if n == 0: return true
    return isOdd(n - 1)

isOdd(n):
    if n == 0: return false
    return isEven(n - 1)

Key differences are:

• Direct recursion has a self-call visible in the same function.
• Indirect recursion involves a call cycle containing two or more functions.
• Indirect recursion can be harder to trace and debug because termination depends on the complete cycle.

Termination is verified using a decreasing measure, such as . In direct recursion, every self-call must reduce that measure. In indirect recursion, every traversal of the function cycle must collectively move the measure toward a reachable base condition.

A function is tail-recursive when its recursive call is the final operation performed by that function. No computation remains after the recursive call returns. In non-tail recursion, the caller must perform additional work after receiving the recursive result.

Non-tail-recursive factorial:

factorial(n):
    if n == 0: return 1
    return n * factorial(n - 1)

The multiplication is pending after the recursive call, so each frame must be retained.

Tail-recursive factorial uses an accumulator:

factorialTail(n, accumulator):
    if n == 0: return accumulator
    return factorialTail(n - 1, n * accumulator)

The initial call is factorialTail(n, 1). Its invariant is that accumulator contains the product accumulated so far.

A compiler or runtime supporting tail-call optimization may execute the tail-recursive form in stack space. Without that optimization, both versions still use stack space, although their evaluation order differs.

Recursive calls are normally managed using the call stack. Every active call receives a stack frame containing information such as:

• Function parameters and local variables
• The return address
• Saved execution state
• Intermediate values needed after the recursive call

For factorial(4), frames are pushed for factorial(4), factorial(3), factorial(2), factorial(1), and factorial(0). The deepest call reaches the base condition and returns . Frames are then popped in last-in, first-out order while pending multiplications are completed.

The recursion depth is , so the auxiliary stack space is . Stack memory is automatically released when each call returns. However, very deep or non-terminating recursion can exceed the runtime's stack limit and cause a stack overflow. Heap memory is involved only when the function explicitly allocates dynamic objects or when a particular runtime stores continuations there.

Advantages of recursion:

• Produces concise solutions for self-similar problems.
• Naturally represents tree traversal, graph search, divide-and-conquer, and backtracking.
• Closely follows recursive mathematical definitions.
• Simplifies restoration of earlier state because each call has its own local variables.

Disadvantages of recursion:

• Uses stack space proportional to recursion depth unless optimized.
• Adds function-call overhead.
• Can cause stack overflow on large or adversarial inputs.
• May repeat subproblems and become exponentially slow without memoization.
• Can be harder to trace when there are many branches or indirect calls.
• Behavior may depend on language-specific recursion and tail-call limits.

Iteration is preferable when the recursion depth can be large, the state transition is simple, strict memory bounds are required, or the target language does not optimize recursive calls. Recursion remains preferable when it gives a substantially clearer representation and the depth is safely bounded.

Backtracking is a depth-first search technique that incrementally constructs candidate solutions and abandons a candidate as soon as it cannot lead to a valid complete solution.

Its standard pattern is:

• Choose: Add one available option to the current partial solution.
• Explore: Recursively investigate choices that extend this state.
• Unchoose: Undo the change so that another option can be tried.

General pseudocode:

search(state):
    if state is a complete solution:
        record state
        return
    for choice in available choices:
        if choice is valid:
            apply(choice)
            search(state)
            undo(choice)

Ordinary exhaustive enumeration generates every possible candidate and checks validity afterward. Backtracking performs pruning: it tests constraints on partial candidates and stops exploring invalid branches early. Its worst-case running time may still be exponential, but effective pruning can greatly reduce the practical search space.

Maintain a current permutation and a Boolean array indicating which elements have already been used.

generate(current, used):
    if length(current) == n:
        output current
        return

    for i from 0 to n - 1:
        if not used[i]:
            used[i] = true
            append A[i] to current
            generate(current, used)
            remove the last element
            used[i] = false

Correctness:

• At depth , current contains exactly distinct input elements.
• Every unused element is considered for position .
• Therefore, every ordering of the elements corresponds to one root-to-leaf path.
• The used array prevents an element from appearing twice in one permutation.
• Because the first differing choice creates a different path, no permutation is generated twice when the input elements are distinct.

There are output permutations, and copying each complete permutation costs . Hence the output-sensitive time complexity is . The recursion depth, current list, and used array require auxiliary space, excluding the output.

If duplicate values are treated as distinct solely by their positions, the ordinary permutation algorithm produces duplicate outputs. A standard solution is to sort the input and skip equivalent choices at the same decision level.

After sorting, apply this condition before choosing index :

if used[i]: continue
if i > 0 and A[i] == A[i - 1] and not used[i - 1]: continue

The second condition means that among equal unused values, only the first occurrence can start a branch at the current depth. The next equal occurrence may be used only after the previous one has already been selected in the current path.

For values with frequencies , the number of unique permutations is:

Sorting costs . Generation time is proportional to the number of unique outputs times , while auxiliary space remains excluding the output.

Let search(start, remaining) find nondecreasing combinations using candidate indices from start onward. Sorting the candidates enables pruning.

search(start, remaining):
    if remaining == 0:
        record current combination
        return

    for i from start to last index:
        if candidates[i] > remaining:
            break
        append candidates[i]
        search(i, remaining - candidates[i])
        remove the last value

Calling search(i, ...) permits reuse of the current candidate. Restricting later choices to index or greater prevents order-based duplicates such as [2, 3] and [3, 2].

The branch is successful when remaining == 0. Since all candidates are positive, a candidate larger than the remaining target cannot be part of a solution. After sorting, all subsequent candidates are also too large, so the loop can stop.

The worst-case running time is exponential because many combinations may be explored. Recursion depth is at most , where is the target and is the smallest positive candidate.

The N-Queens problem asks for placements of queens on an chessboard such that no two queens share a row, column, or diagonal.

Place exactly one queen in each row. For row , try every column that is not under attack, recurse to row , and remove the queen when returning.

Efficient safety checks use three sets or Boolean arrays:

• columns[c] identifies an occupied column.
• mainDiagonal[r - c] identifies a descending diagonal.
• antiDiagonal[r + c] identifies an ascending diagonal.

Queens at and share a diagonal precisely when or .

Each validity test and update then takes time. The algorithm records a solution after queens have been placed in all rows. Its worst-case time is commonly bounded by after column pruning, although diagonal pruning reduces the explored states considerably. The board path and attack structures use auxiliary space.

Represent a placement as an array in which index is the row and value is the selected column.

Starting in row , the algorithm tries columns from left to right. After every placement, it rejects columns already used and diagonals identified by or . When a row has no legal column, it removes the queen from the preceding row and tries that row's next option.

For example, starting with column eventually produces dead ends. Starting with column permits the sequence:

• Row : column
• Row : column
• Row : column
• Row : column

The two valid solutions are:

Every pair of entries has distinct columns. Their row-column differences and row-column sums are also distinct, so no queens share diagonals. The two results are mirror images and are the only solutions for .

A happy number is a positive integer that eventually becomes when repeatedly replaced by the sum of the squares of its decimal digits. If the sequence enters a cycle that excludes , the number is unhappy.

For a number , define:

where are the decimal digits of .

To test happiness, maintain a set of previously encountered values:

isHappy(x):
    seen = empty set
    while x != 1 and x not in seen:
        insert x into seen
        x = sumOfSquaredDigits(x)
    return x == 1

To find the next happy number, begin with candidate = n + 1 and increment it until isHappy(candidate) returns true.

Cycle detection guarantees that testing an unhappy number terminates. Floyd's slow-and-fast pointer method can replace the set to use auxiliary space. The outer search returns the first successful candidate, so it is necessarily the smallest happy number greater than .

Both approaches repeatedly apply the digit-square transformation and determine whether the sequence reaches or enters a cycle.

Hash-set approach:

• Store every visited value.
• Return true if the current value becomes .
• Return false if a value is encountered for the second time.
• It is straightforward to understand and can expose the actual cycle.
• It requires memory proportional to the number of distinct visited states.

Floyd's cycle detection:

• Maintain slow = F(slow) and fast = F(F(fast)).
• If fast reaches , the number is happy.
• If slow == fast before reaching , the sequence has entered a non-happy cycle.
• It requires auxiliary space.

Both methods take time proportional to the number of states visited before reaching or detecting a cycle. Floyd's method is more space-efficient, while a hash set is often easier to implement and debug.

A sum string is a digit string that can be split into at least three nonempty numeric substrings such that every substring after the first two represents the sum of the preceding two numbers.

For example, 122436 can be split as , and .

Algorithm:

• Try every possible nonempty first substring.
• Try every possible nonempty second substring following it.
• Reject a multi-digit number with a leading zero unless the specification explicitly permits it.
• Compute the decimal-string sum of the two selected values.
• Check whether this sum occurs immediately after the second value.
• If it matches, recursively continue with the second value and the sum.
• Accept when the recursive matching consumes the entire string.

Trying all first and second split positions covers every possible starting decomposition. Once those two numbers are fixed, every subsequent number is uniquely determined, so recursive matching is sufficient to prove or reject that decomposition.

A sum string may contain numeric parts longer than the largest value supported by built-in integer types. Converting such substrings to fixed-width integers can overflow, produce an error, or silently return an incorrect value. Decimal-string addition avoids this limitation.

To add strings a and b:

• Start at their rightmost digits.
• Add the current digits and a carry value.
• Append the digit total % 10 to a temporary result.
• Set carry = total / 10 using integer division.
• Continue until both strings and the carry are exhausted.
• Reverse the temporary result.

This process takes time and space. Leading-zero rules must be checked separately when choosing substrings. Using string addition makes the sum-string test correct for arbitrarily long inputs, subject only to available memory.

In the water overflow problem, glasses are arranged in rows. Each glass has capacity unit. Water is poured into the top glass, and any excess is divided equally between the two glasses immediately below it.

Let be the total water reaching the glass at row and column , using zero-based indexing. The top receives the poured amount :

For valid positions below the top:

A parent term is omitted when its coordinates are outside the pyramid. The actual amount retained by a glass is:

A naive recursive implementation recomputes the same parent states many times. Memoization reduces the work to states for all glasses through row , with storage. A row-by-row dynamic-programming simulation can achieve auxiliary space.

Create an array representing the water reaching each glass in the current row. Initialize the top value to the poured amount . For each glass with incoming amount water:

• Compute overflow = max(0, water - 1).
• The glass retains min(1, water).
• Add overflow / 2 to each of its two children in the next row.

Pseudocode:

current[0] = X
for row from 0 to targetRow - 1:
    next = array of zeros
    for col from 0 to row:
        overflow = max(0, current[col] - 1)
        next[col] += overflow / 2
        next[col + 1] += overflow / 2
    current = next

Overflow must be computed from the incoming amount before capping. If current[col] is first replaced by min(1, current[col]), information about all excess water is lost and no water can be propagated correctly.

Processing through row takes time and auxiliary space.