The Two Faces of Recursion: Linear and Binary Approaches Explained
Master Recursion: One-Branch & Two-Branch Techniques
Hello guys, Preparing for coding interviews can feel overwhelming, especially when you realize how often recursion shows up in popular problems.
From binary trees to backtracking, recursion is one of those fundamental concepts that companies like Google, Meta, and Amazon love to test. If you don’t have a solid grip on it, even relatively simple problems can feel intimidating.
That’s why it’s important to not only understand the theory of recursion but also to practice it with real-world interview-style problems. Fortunately, there are some fantastic resources that make this much easier.
In the past we have talked about essential System design concepts and software architecture components like Rate Limiter, Database Scaling, API Gateway vs Load Balancer, Horizontal vs Vertical Scaling, Caching strategies.
And, in this article we will talk about the basics of recursion—dissecting its one-branch and two-branch variants to unveil how this elegant methodology can simplify coding endeavors.
For this article, I have teamed up with Hayk, a Senior Software Engineer, System Design and Coding interview expert, and creator of System Design for Beginners: Build Scalable Backend Systems Udemy course.
By the way, if you are preparing for coding interviews then using resources like AlgoMonster, ByteByteGo, or Exponent can help you a lot in cracking coding interviews.
For example, AlgoMonster takes a hands-on approach with categorized problems and patterns, helping you break down recursion step by step.
If you prefer visual learning, ByteByteGo is excellent for grasping complex coding concepts through diagrams and illustrations.
And if mock interviews are part of your prep strategy, Exponent gives you structured interview practice to build confidence.
With that, now I handover to Hayk Simonyan to take you through rest of articles.
Introduction to Recursion
In the realm of computer science, there exists a mesmerizing and somewhat mystical technique that often intrigues newcomers and experienced programmers alike: recursion.
At its core, recursion is a strategy where a function resolves a problem by calling itself, but with a reduced scope. This approach breaks down complex issues into more manageable sub-problems of an identical nature.
In this exploration, we delve into the nuances of recursion, dissecting its one-branch and two-branch variants to unveil how this elegant methodology can simplify coding endeavors.
The Singular Path of One-Branch Recursion:
Imagine standing in front of a mirror holding another mirror. You’d see an image within an image, receding into infinity. This is akin to one-branch recursion in action, where a function mirrors itself with a singular call.
A paradigmatic illustration is the calculation of a number’s factorial, defined as the product of all positive integers leading up to that number, n. How does recursion streamline this process?
n! = n⋅(n−1)⋅(n−2)⋅…⋅1n!=n⋅(n−1)⋅(n−2)⋅…⋅1
Consider the factorial of 4, represented mathematically as 4!. The recursive breakdown is:
Start with the number 4.
Multiply it by its predecessor, 3, yielding 12.
Continue with 2, arriving at 24.
Culminate by incorporating 1 to maintain the product, 24.
This sequence crystallizes as 4! = 4 × 3 × 2 × 1 = 24.
If we write this in code, we would have a recursive case, where our function makes a recursive call to itself with the argument n — 1 and multiplies n by the result of this recursive call.
But it should also have a base case to prevent it from running indefinitely. Here, if n is less than or equal to 1 the function just returns 1.
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
With a single recursive call, we break down the problem into smaller chunks until we hit the base case, where n is less than or equal to 1.
The Forked Paths of Two-Branch Recursion
Two-branch recursion unfolds like a tree with each call branching out twice.
It’s exemplified by generating the nth number in the Fibonacci sequence, a series where after the first two numbers, each subsequent number is the sum of the two before it.
F(0) = 0, F(1) = 1, F(n) = F(n — 1) + F(n — 2)
The recursion magic unfurls as follows for the 4th Fibonacci number:
Compute the 3rd and 2nd numbers, because the 4th is their sum.
For the 3rd, calculate the 2nd and 1st; again, the 3rd is their sum, with these two numbers being defined as 1, according to the base cases.
Captured in code, the two-branch recursion for Fibonacci numbers is:
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
This creates a computation tree, each branch resolving a piece of the Fibonacci puzzle.
The Call Stack: Recursion’s Backbone
Recursion relies on the call stack, a data structure that records where each function is up to. Each recursive invocation is stacked on top until a base case is hit. Then, the stack unwinds, resolving the problem step-by-step as it pops off the calls.
Recursion Vs Iteration:
It’s essential to note that any recursive solution can be rewritten iteratively, although the iterative version may require more code and may not be as intuitive.
While recursion provides a clean and simple way to solve problems, iterative solutions using loops can be more efficient in terms of memory usage.
Here’s how we could write an iterative solution to calculate the factorial of a number:
function factorialIterative(n) {
let result = 1;
for (let i = n; i > 0; i--) {
result *= i;
}
return result;
}Recognizing When to Recur
So, when does recursion rise to the occasion? Typically, it shines when a problem can be decomposed into smaller, analogous challenges.
It also excels in situations that exhibit self-similarity or a hierarchical structure, like traversing a family tree or navigating the nested folders of a filesystem.
Final Reflections
In conclusion, recursion is a powerful, loop-like construct for tackling problems by dividing them into tinier, similar sub-tasks. Whether it’s the straightforwardness of one-branch recursion or the complexity of two-branch recursion, this technique employs the stack to keep track of where each call is in the process.
A crucial point to note is that all types of recursions utilize the stack data structure to keep track of the function calls.
If you’re interested in diving deeper into the mechanics of the stack data structure and how it powers recursion, I recommend you check out this Deep Dive into Stacks + LeetCode Practice.
And, if you like this post then don’t forget to subscribe Hayk’s newsletter and if you want to support you can also join his System Design course on Udemy to Learn system design basics with APIs, databases, caching, proxies, load balancers, and real interview examples.
Other AI, System Design and Coding Interview Articles you may like
 | A guest post by
|
I enjoyed this. we can diversify this area. When I think recursion it's not limited to these scenario. I put entire apps and every function though this. It's like a double entry accounting system for whole system. There's no such thing as building something that goes nowhere. It's all recursive.