Recursive Leap of Faith [Technique Tuesdays]

A lot of you struggle with Dynamic Programming and Backtracking. This will help you.

May 18, 2022

Cama-ihi my amazing reader,

That’s one of the common traditional Alaskan ways of saying hello (good to see you). As this newsletter and my articles have grown more, I have been able to interact with a lot more of you. This is more validation of the effectiveness of the approach I have been pushing.

This growth clearly shows that the approach I propose is clearly effective and much needed.

With this increased recognition has come more communication with people. And it seems like some of you are still struggling to code up recursion problems. So I have a very interesting trick for you. This technique can be applied to all recursion programming, and is always effective (at least for coming up with brute force solutions). This my amazing friends is called the recursive leap of faith.

Make sure you guys also read up on all the other recursion posts. Will leave you bulletproof. Recursion Theory is overlooked by so many people.

I know it sounds like I’m promising a lot. But trust me, it is worth it. Let’s get into it.

For the best results, become a premium subscription. Imagine yourself safe from all the terrible advice out there, cruising your way to your dream job and crushing your career. A subscription will get you there.

The Highlights

This post will cover the following ideas-

What is the recursive leap of faith?- Simply put, we assume that our recursive call will work exactly as it’s supposed to.
How this works- If you read through the recursive theory I have covered, you will know that recursive problems can be solved by splitting the problem into base cases and the recursive steps. Leap of faith covers the latter.
Getting good at this technique- Practice. Shocking I know.

Sound like something you’d be interested in? Let’s get groovy.

The Technique

The technique is deceptively simple. Simply put, as with all recursion, we work out the base cases. Once we have created them, we take the recursive cases, and then call our recursive function with updated parameters. So far, so obvious. Where’s the magic that I promised?

The leap of faith method is the assumption that the method/function we're in the middle of writing already works. So if we are creating a recursive call on a graph, we will assume that the function already works for the subgraph.

Some of you are probably feeling a little confused, so let’s go through a few examples.

Depth of Tree Recursion

Let’s start small. This is the classic recursive problem.

def depthT(node, depth){
 
if node is null: #base case
  return depth

 else:
   return max(depthT(node.left, depth+1), depthT(node.right, depth+1))
}

Notice how we implicitly assume that the depthT function will work for all the sub-trees?

You’re probably not convinced because this is a simple example. Let’s kick things up a notch.

Word Search

Last week, we covered the Word Search problem. This is a darling of many technical interviews. Let’s look at the baseline solution through the lens of our wonder technique. In a nutshell, we want to find out if a word exists in our grid, assuming we can only take characters from cells adjacent to each other. And we can’t repeat the contents from the same cell more than once per word.

Make sure you don’t miss any of the solutions.

Our dfs solution has a few base cases. They are when we go out of bounds, have already visited a cell on the board, or know that our current cell doesn’t match the character at our required index.

            if r<0 or r>=len(board) or c<0 or c>=len(board[0]):
                return False
            if board[r][c]!=word[idx] or (r,c) in visited:
                return False

Next up, we know that if our index is the same as the length of our desired string, and we haven’t hit the conditions already mentioned, we have found our match.

if idx == len(word)-1:
                return True

These are the edge cases we go through. If the input has gone through these edge cases, and not triggered them, we know that it is the following mold

So far we haven’t gone out of bounds or repeated the cell in this combination.
The string we have created so far is a strict substring of the target one.

Now is when we can take the leap of faith. See if you can spot it-

for dr,dc in neighbors:
                nr,nc = r+dr, c+dc
                if dfs( idx+1, nr, nc):
                    return True

Simply put, we are assuming that dfs traversal will work for the rest of the graph and the remaining substring.

FYI the final solution I shared for this problem is much faster than average. Use it to get exceptional results.

I could go on and on but I don’t want to make this email too long. Fortunately, we have covered a lot of problems using recursion. Go through them, and look at how they all implicitly use the leap of faith. If you’re still not convinced, go through any recursive solution online and you will see the recursive leap of faith is present.

Why this works

Now that you know that it works, let’s take a second to discuss why this is such a powerful technique. Simply put, the recursive leap of faith is based on the inductive property of recursive solutions. What do these fancy words mean?

Y’all are too kind. Send me an email with how much you love me to boost my ego. All compliments are appreciated <3

Notice how in the leap of faith we assume that our function will work for our subproblem. When our recursive problem is called on the subproblem we have two options-

We hit one of the base cases. Assuming they are constructed well, our program terminates with the appropriate results.
We hit a recursive case, and our assumption again kicks in. This time on the sub-subproblem. This process will work till we hit a base case.

If you have been a good boy/girl/non-binary/whatever and read into the recommended posts, you know that this is similar to the logic of why Mathematical Induction works. Hence the inductive property of recursive solutions.

Notice how all these are based on recursive problem-solving.

On a practical note, this technique will severely reduce your overthinking. Half the struggle with Recursion people have is that they are unable to gain clarity while working through problems. Implementing the leap of faith will allow you to work through problems quicker by giving you a clear direction.

Getting Good with this technique

So how can you get good with this amazing technique? Time for the boring part of the newsletter- PRACTICE. To get the most out of the problems you go through, use this format here.

Remember, coding interviews are a skill. Solving Leetcode Style problems is a skill. You have to put in the work to gain mastery over these skills. You don’t have to do the 500+ problems that every Leetcode guru online pushes, but you do need a few to develop baseline comfort.

The good thing is that this technique requires very little additional effort. As you go through the recursion problems online, just take some time to explicitly break it down into base cases and leap of faiths. Originally, this will feel slow and awkward. As you get better, you will be able to zoom through this process.

Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.

Special Request

This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.

There is a simple form in Substack that you can fill up for it. Here it is. Thank you.

https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform

To get your Substack URL, follow the following steps-

Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.

Click on the circled place to get your URL

You will be redirected to your URL. Please put that in to the survey. Appreciate your help.

In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs

If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.

https://forms.gle/XfTXSjnC8W2wR9qT9

Happy Prep. I’ll see you at your dream job.

Go kill all you magnificent maestro,

Devansh <3

To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below

Get 20% off for 1 year