Recursion

Introduction

Recursion had always been a challenging way of thinking for me. Even something as basic as Fibonacci Series making me overthink its solution. Coming from a solid grounding in iterative thinking, the shift to recursive problem-solving was like learning to write with my left hand after years of being right-handed. The struggle wasn't just about learning the syntax but adopting an entirely new mindset. As it was my weak point, I decided to solely focus on it until there was no confusion surrounding it.

The Leap of Faith

I've found ChatGPT great for learning in general. Naturally, I just used it and got started with a prompt "How do I master recursion in a week?" The answer led me down a path of resources, including an enlightening YouTube (opens in a new tab) video that reshaped my understanding about recursion. The key was the "leap of faith" — trust the function to do its job without obsessing over the inner workings. Once I understood that, things started to click. That was the main trap I was falling into. Making the switch from thinking iteratively, in which you would usually track what each variable was doing.

Simplifying the Complex

At its heart, recursion is about trust and a solid base case. It's the art of breaking down a problem into smaller versions of itself until the solution becomes apparent. A popular analogy is a matryoshka doll — opening one to find another, smaller, similar one inside, until you reach the tiny doll that holds the final answer.

Lets take an example. Say we want to build a program that calculates factorial of a number. Our first step is finding the pattern. In this case we can see that to calculate 5!, we just need to multiply 5 x 4!. 4! in turn is just 4 x 3! and it continues on till we reach 1. 1 will be our base case, its the point where our program needs to end. Without the base case, our program will be stuck in an infinite loop. The next thing we need to do is trusting the function that it will calculate the pattern that we want it to calculate.

int factorial(int number){
    if(number == 1) return 1; //base case
    return number * factorial(number - 1);
}

Practical Application: DFS and Beyond

Recursion truly shined for me when I tackled Depth-First Search (DFS) in tree data structures. Using recursion to delve deeper into a tree felt natural and intuitive. Most DFS problems follow a similar structure, only requiring minor tweaks to a standard formula. For instance, in finding the maximum depth of a tree, a simple recursive function can elegantly traverse through the tree's branches.The elegance of a recursive function calling itself to traverse deeper into a tree felt natural. DFS problems also are similar to each other in the sense there are usually just a few things that you need to change onto a blueprint giving result to something completely different.

int recurse(TreeNode *root){
    if(root == nullptr){     // usually the base case would be something similar
        return 0;
    }
    // computation here
    return max(recurse(root->left), recurse(root->right)) + 1; // example giving max depth of a tree
}

Advanced Challenges: Backtracking

While I haven't delved into tail recursion or memoization just yet, backtracking problems like generating subsets have been a playground for applying advanced recursion. Each recursive call branches out into possibilities, and backtracks when a path is fully explored. Here's a snippet to illustrate:

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.pop_back();
    }
}

Conclusion: A Newfound Confidence

Conquering recursion has not just enhanced my coding skills, it has bolstered my overall confidence. What once seemed like a daunting challenge is now a clear and approachable concept. My advice to fellow learners is to lean into your weaknesses; it's a powerful way to grow and improve. Thanks for joining me on this journey of discovery!