Introduction
As you know, I love blog-driven development.
I got a little bit confused about recursion when building a Linked List (data structure).
I ended up writing this piece for myself.
Enjoy the read.
What's recursion?
Let's use the Inception analogy! Remember that movie scene where they dream within a dream and then... within another dream?
That's somewhat like recursion. In programming, it means a function that says, "I'm going to solve a part of this problem and let another 'mini-me' function handle the rest!" So, it calls itself until the problem is completely solved.
History of recursion
Back in the day, nature was showing off recursion with stuff like snowflakes and branching trees.
Fast forward, Fibonacci used recursion in a number sequence.
Fast forward even more, coders love recursion because it's like a magic trick for tough problems.
In short, recursion's been everywhere, from nature's patterns to today's code!
Why does it exist?
Problem Splitting: Sometimes, staring at a big problem is hard. But if you can make it into a "mini-version" of itself, then the problem becomes easier.
Elegance: For certain problems, recursion offers an elegant solution.
Data Structures: Structures like trees and graphs have a recursive nature. Imagine going through a family tree: "Who's the parent of the parent of the parent...?"
Basics
Base Case: This is your escape hatch. Without it, you're stuck in the recursive dream forever (or at least until the system crashes). It defines when to stop.
Recursive Case: The function is called here, but with a smaller or simpler piece of the problem.
Pros
Clean Code: For some problems, recursion provides a neat solution without many lines of code.
Tree & Graph Structures: Walking through trees (like the Document Object Model in web dev) is often naturally recursive.
Divide & Conquer: Helps to break down complex problems into smaller, more manageable ones.
Cons
Efficiency: Each function call consumes memory. A loop might handle the same task more efficiently.
Stack Overflow: Too much recursion can crash your program because it uses up all the space reserved for function calls.
Complexity: For newcomers, recursion can sometimes be a bit harder to wrap the head around compared to loops.
When to consider?
Imagine you're building software and face problems like navigating a deeply nested menu, searching through hierarchical data, or implementing certain algorithms.
If you notice that the task at hand can be broken down into simpler, repetitive steps, then consider recursion.
Inner workings
Every recursive call gets added to the Stack. The pattern it follows is "last in, first out". So the last function call will be the one first completing.
The key takeaway here is that every recursive call remains "paused" until all of the deeper recursive calls complete.
Each function call gets its own space in memory (often visualized as a stack frame). These stack frames hold function parameters, local variables, and the return address.
Let's say we have a countDown function where the base gets hit when the number becomes zero.
This is roughly how it would look like running till it hits the base case:
Stack:
countDown(3) --> still running (paused)
countDown(2) --> still running (paused)
countDown(1) --> still running (paused)
countDown(0) --> completed
Once the last function has been popped off the stack (the one that hit the base case), the next one runs. It recursively moves up and completes each function.
Realistic Examples
Directory traversal
Let's say you're working on a file management system, something like Dropbox or Google Drive. Users can have folders, and within those folders, they can have more folders and files.
function countFiles(directory) {
let count = directory.files.length;
for (let subdirectory of directory.subdirectories) {
count += countFiles(subdirectory);
}
return count;
}
Imagine you're developing a discussion platform similar to Reddit.
Users can leave comments, and other users can reply to those comments. This can go several layers deep (a comment on a comment on a comment, and so on). Now, you need a function that can print all comments and their replies in a structured way.
function printComment(comment, indent = '') {
console.log(indent + comment.text);
for (let reply of comment.replies) {
printComment(reply, indent + '---');
}
}
Common Mistakes
Forgetting the base case
The base case is essential in recursion. Without it, your recursive function will run indefinitely, leading to a stack overflow. It's the condition under which the function stops calling itself.
function countDown(number) {
console.log(number);
countDown(number - 1);
}
function countDown(number) {
if (number <= 0) {
console.log("Done!");
return;
}
console.log(number);
countDown(number - 1);
}
Each recursive call should bring you one step closer to the base case. If you don't modify the inputs in a way that moves you towards the base case, you'll end up with infinite recursion.
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n);
}
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
Misunderstanding the Recursive Stack
It's important to remember that each recursive call gets its own execution context. Local variables aren't shared between calls.
function sumToN(n) {
let sum = 0;
if (n <= 1) return n;
sum += n + sumToN(n - 1);
return sum;
}
function sumToN(n) {
if (n <= 1) return n;
return n + sumToN(n - 1);
}
Ignoring the Return Value
Recursive functions often rely on return values of their recursive calls.
Ignoring or forgetting to use these can lead to incorrect results.
function reverseString(str) {
if (str === "") return "";
const lastChar = str[str.length - 1];
reverseString(str.substring(0, str.length - 1));
return lastChar;
}
function reverseString(str) {
if (str === "") return "";
const lastChar = str[str.length - 1];
return lastChar + reverseString(str.substring(0, str.length - 1));
}
This however is necessary if you want something returned from the function.
Conclusion
Recursion is beautiful when used right.
The tricky part lies in understanding how the inner workings work.
I hope you enjoyed this.
