Finding the Ultimate Referrer with Recursive Code: A Deep Dive
Written on
Chapter 1: Understanding Referral Commissions
Many applications feature referral commissions, where user A invites user B to sign up, and subsequently, user B invites user C. In this scenario, user A serves as the "ultimate referrer" for user C and also for user B, while user A does not have a referrer of their own.
To manage these referral relationships, we typically utilize a database containing two primary columns: actor_id for the user ID and referrer_id for the corresponding referrer ID.
With this context in mind, let's tackle the question: how can we identify the "ultimate referrer" for a given user ID? This leads us to today's focus: recursion.
Section 1.1: What Is Recursion?
From my experience with data structures and algorithms, I believe recursion and dynamic programming are the most challenging concepts to grasp. Recursion is a powerful programming technique widely used in various algorithm implementations, including Depth-First Search (DFS) and tree traversals (pre-order, in-order, and post-order). A solid understanding of recursion is essential for tackling more complex data structures and algorithms.
Despite its reputation, recursion is not an esoteric concept. We encounter recursive patterns in everyday life. For example, if you're at a dark movie theater and want to determine which row you're in, you might ask the person in front of you. They would then inquire of the person ahead of them, continuing this process until reaching the front row. Each person forwards the row number back, allowing you to deduce your own.
This scenario illustrates a classic recursion problem-solving pattern, where the act of asking is called "recursion," and the feedback loop is termed "unwinding." Essentially, all recursive problems can be expressed through a recurrence relation. In this case, we can represent it as follows:
f(n) = f(n - 1) + 1, where f(1) = 1
Here, f(n) denotes the row you wish to find, f(n-1) represents the row number directly in front of you, and f(1)=1 indicates that the front-row occupant knows they are in the first row. This relation can be translated into recursive code:
int f(int n) {
if (n == 1) return 1;
return f(n-1) + 1;
}
Section 1.2: Conditions for Recursion
What types of problems can recursion solve? I have identified three criteria that must be satisfied:
- The problem can be divided into smaller subproblems.
- In our movie theater example, "Which row am I in?" can be broken down into asking "Which row is the person in front of me in?"
- The problem and its subproblems follow the same approach, differing only in data size.
- The method used to resolve "Which row am I in?" is identical for the person ahead.
- There must be a base case that terminates the recursion.
- In our example, the individual in the first row does not need to ask anyone else; they inherently know they are in row one. This acts as the stopping condition, or base case.
Chapter 2: Implementing Recursive Code
Having established the groundwork, let's examine how to write recursive code. The critical steps involve formulating the recurrence relation and identifying the termination condition. Once these elements are clear, translating them into code is relatively straightforward.
To illustrate, consider a scenario where you need to climb n steps, taking either one or two steps at a time. The challenge is to find the number of distinct ways to reach the top. We can categorize climbing methods based on the first step taken: either one step or two steps. Thus, the total number of ways to ascend n steps can be expressed as:
f(n) = f(n-1) + f(n-2)
With the recurrence relation established, we now identify our termination conditions: when there is one step, f(1) = 1, and when there are two steps, f(2) = 2.
The combined recurrence relation and termination conditions become:
f(1) = 1;
f(2) = 2;
f(n) = f(n-1) + f(n-2);
The resulting recursive code looks like this:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}
In summary, the essence of writing recursive code lies in breaking down a complex problem into simpler components, establishing a recurrence formula, determining the termination conditions, and then coding the solution.
Section 2.1: Handling Stack Overflow in Recursive Code
When developing recursive code, one must be wary of issues like stack overflow. A stack overflow occurs when the call stack exceeds its limit, potentially crashing the system. This is particularly problematic with deep recursion.
For instance, in the movie theater example, if the stack size is limited, querying f(19999) may lead to a stack overflow error.
To mitigate this risk, we can restrict the maximum depth of recursion in our code. For example:
int depth = 0;
int f(int n) {
++depth;
if (depth > 1000) throw new Exception("Too deep!");
if (n == 1) return 1;
return f(n-1) + 1;
}
However, this approach has its limitations, as it relies on the remaining stack space, which is unpredictable.
Section 2.2: Reducing Redundant Calculations
Recursive methods can also lead to redundant calculations. For instance, in our Fibonacci example, f(3) is computed multiple times. To address this, we can store previously calculated results using a hash table to avoid unnecessary computations:
public int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (hasSolvedList.containsKey(n)) {
return hasSolvedList.get(n);}
int ret = f(n-1) + f(n-2);
hasSolvedList.put(n, ret);
return ret;
}
There are other challenges associated with recursive code, including time inefficiencies due to numerous function calls and high space complexity, as each call consumes stack space.
Chapter 3: Converting Recursive Code to Iterative Code
While recursion offers clarity and conciseness, it can also lead to significant drawbacks, such as stack overflow and redundant calculations. Therefore, the decision to use recursion should be based on the context.
Is it feasible to transform recursive code into iterative code? Yes, it is possible. For instance, we can rewrite our climbing example in an iterative manner:
int f(int n) {
int ret = 1;
for (int i = 2; i <= n; ++i) {
ret += 1;}
return ret;
}
Similarly, the Fibonacci sequence can be implemented without recursion:
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int ret = 0;
int pre = 2;
int prepre = 1;
for (int i = 3; i <= n; ++i) {
ret = pre + prepre;
prepre = pre;
pre = ret;
}
return ret;
}
While you can convert most recursive code into iterative loops, it often involves simulating the stack operations manually, which adds complexity.
Section 3.1: Finding the Ultimate Referrer
Now, returning to our initial inquiry about identifying the "ultimate referrer," the solution can be encapsulated in a few lines of code:
long findRootReferrerId(long actorId) {
Long referrerId = select referrer_id from [table] where actor_id = actorId;
if (referrerId == null) return actorId;
return findRootReferrerId(referrerId);
}
While this approach is succinct, it may face challenges in practical applications due to potential deep recursion and dirty data in the database.
To address the recursion depth issue, we can limit it as previously discussed. Additionally, we need to manage data integrity to prevent infinite loops in referral chains, which will be explored in future articles.
Conclusion
Recursion is a highly effective coding technique, capable of solving any problem that meets the established criteria. However, writing recursive code can be challenging. The key is to clearly define the recursive formula, establish the termination conditions, and translate this into code.
Despite its advantages, recursion also carries risks such as stack overflow, redundant calculations, and high resource consumption. Thus, careful management of these potential issues is vital when implementing recursive solutions.
Chapter 4: Additional Resources
Explore how to implement a Connect 4 AI using the minimax algorithm in this informative video.
Learn about SQL hierarchies using CONNECT BY and recursive WITH in this detailed tutorial.