Many applications feature referral systems where users earn commissions by inviting others. Consider a scenario where User A invites User B, and User B, in turn, invites User C. In this chain, User A is the ultimate referrer for both User B and User C. User A, however, has no ultimate referrer. This referral hierarchy is typically stored in a database, with records typically containing an actor_id and a referrer_id. The challenge is to efficiently find the ultimate referrer for any given user ID.

This problem is a prime candidate for recursion, a powerful algorithmic technique and programming skill. Recursion is fundamental to many data structures and algorithms, including Depth-First Search (DFS) and various tree traversal methods. Mastering recursion is crucial for comprehending more complex topics later on.

A common analogy for recursion involves finding your row number in a dark movie theater. If you don't know your row, you ask the person in front of you. They, in turn, ask the person ahead of them, and so on, until the first row is reached. The person in the first row knows they are in row 1. This knowledge is passed back up the chain: the person in row 2 adds 1 to the information received from row 1, and this continues until you receive the answer. This process exemplifies recursion's divide-and-conquer approach, with the upward journey being the "decomposition" (递) and the downward journey being the "composition" (归).

Mathematically, this can be represented by a recurrence relation. For the movie theater example, if f(n) represents the row number, the relation is f(n) = f(n-1) + 1, with the base case f(1) = 1. This translates directly into code:

int findRow(int n) {
    if (n == 1) {
        return 1;
    }
    return findRow(n - 1) + 1;
}

Conditions for Recursion

For a problem to be suitable for a recursive solution, it must satisfy three conditions:

1. Subproblem Decomposition: The problem can be broken down into smaller, similar subproblems. In the movie theater example, determining your row number depends on knowing the row number of the person in front of you.
2. Identical Solution Strategy: The approach to solving the subproblems is identical to the approach for the original problem, differing only in scale. Your method of finding your row is the same as the person in front of you asking the person ahead of them.
3. Base Case: A termination condition must exist to prevent infinite recursion. In the movie theater example, the person in the first row provides this base case (f(1) = 1).

Writing Recursive Code

The key to writing recursive code lies in formulating the recurrence relation and identifying the base case(s). Translating these into code is then straightforward.

Consider a problem: finding the number of distinct ways to climb n stairs, where you can take either 1 or 2 steps at a time. Let f(n) be the number of ways to climb n stairs.

If you take one step first, you have n-1 stairs remaining, contributing f(n-1) ways. If you take two steps first, you have n-2 stairs remaining, contributing f(n-2) ways. Thus, the recurrence relation is f(n) = f(n-1) + f(n-2).

Now, for the base cases:

• For n=1 stair, there's only one way (1 step): f(1) = 1.
• For n=2 stairs, there are two ways (1+1 or 2 steps): f(2) = 2.

Testing this with n=3: f(3) = f(2) + f(1) = 2 + 1 = 3. The ways are (1,1,1), (1,2), (2,1), which matches.

The recursive code becomes:

int countWaysToClimb(int n) {
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return countWaysToClimb(n - 1) + countWaysToClimb(n - 2);
}

When dealing with recursive problems, especially those that branch into multiple subproblems (like the stair-climbing example), it's easy to get lost in the detailed execution flow. Instead of trying to trace every step, adopt the strategy of assuming the subproblems are already solved. Focus only on the relationship between the current problem and its direct subproblems. This abstraction simplifies understanding.

Stack Overflow Risk

Recursion relies on the call stack. Each function call pushes a stack frame onto the stack. Deeply nested recursive calls can exhaust the available stack space, leading to a StackOverflowError.

A potential mitigation is to impose a maximum recursion depth. However, this is often impractical as the actual stack limit varies and hardcoding a limit might be too restrictive or too permissive.

// Pseudo-code illustrating depth limit
int maxDepth = 1000;
int currentDepth = 0;

int findRowLimited(int n) {
    if (currentDepth > maxDepth) {
        throw new StackOverflowError("Recursion depth exceeded");
    }
    currentDepth++;
    if (n == 1) {
        currentDepth--; // Decrement depth upon returning
        return 1;
    }
    int result = findRowLimited(n - 1) + 1;
    currentDepth--; // Decrement depth upon returning
    return result;
}

Redundant Computations

Recursive functions, especially those with overlapping subproblems like the stair-climbing example, can perform the same calculations multiple times. For instance, calculating f(5) involves recalculating f(3) multiple times.

This can be optimized using memoization. Store the results of already computed subproblems in a data structure (like a hash map) and return the stored result if available, avoiding recomputation.

import java.util.HashMap;
import java.util.Map;

Map<Integer, Integer> memo = new HashMap<>();

int countWaysToClimbMemoized(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    if (memo.containsKey(n)) {
        return memo.get(n);
    }
    
    int result = countWaysToClimbMemoized(n - 1) + countWaysToClimbMemoized(n - 2);
    memo.put(n, result);
    return result;
}

Beyond stack overflow and redundant computations, recursive calls introduce overhead from function call mechanics, impacting time efficiency. Spatially, the call stack consumes memory, increasing space complexity (e.g., O(n) for the movie theater example).

Converting Recursion to Iteration

Recursive solutions can often be refactored in to iterative ones, which can mitigate stack overflow issues and sometimes improve performance.

For the movie theater example (f(n) = f(n-1) + 1):

int findRowIterative(int n) {
    int row = 1;
    for (int i = 2; i <= n; ++i) {
        row = row + 1;
    }
    return row;
}

For the stair-climbing example (f(n) = f(n-1) + f(n-2)):

int countWaysToClimbIterative(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    int prevPrev = 1; // f(1)
    int prev = 2;     // f(2)
    int current = 0;
    
    for (int i = 3; i <= n; ++i) {
        current = prev + prevPrev;
        prevPrev = prev;
        prev = current;
    }
    return current;
}

Essentially, any recursive algorithm can be converted to an iterative one by explicitly managing a stack data structure to simulate the call stack. However, this manual simulation often increases complexity without fundamentaly changing the nature of the algorithm or resolving all its inherent drawbacks.

Finding the Ultimate Referrer

Returning to the initial problem of finding the ultimate referrer for a given actorId, a concise recursive solution can be implemented:

// Assuming a method to fetch referrer from database
// public Long selectReferrer(long actorId);

long findRootReferrerId(long actorId) {
    Long referrerId = selectReferrer(actorId);
    if (referrerId == null) {
        return actorId; // Base case: no referrer found
    }
    // Recursive step: find root referrer of the current referrer
    return findRootReferrerId(referrerId);
}

This solution is elegant but has practical considerations:

1. Stack Overflow: Deep referral chains can lead to excessive recursion depth.
2. Infinite Recursion: Malicious or corrupt data can create cycles (e.g., A refers to B, B refers to C, C refers to A), causing infinite recursion. This can be mitigated by limiting recursion depth or by implementing cycle detection algorithms.

Conclusion

Recursion offers an expressive and often elegant way to solve problems that can be broken down into smaller, self-similar subproblems. Key to effective recursion is identifying the problem's recurrence relation and its base case. While powerful, recursive solutions must be carefully implemented to manage potential issues like stack overflow, redundant computations, and performance overhead. Converting recursive logic to iterative forms can often address these concerns, though it may require more verbose code. Debugging deeply recursive code can be challenging, often requiring different strategies than step-by-step tracing, such as logging or analyzing execution traces.