The Recursive Function Template[Technique Tuesdays]

How to implement any recursive function

Oct 12, 2022

To learn more about the newsletter, check our detailed About Page + FAQs

To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.

Recommend this publication to Substack over here

Take the next step by subscribing here

In last week’s solution, I shared my template for solving recursive functions.

It’s something I’ve shared with a lot of the students who I’ve tutored. Turns out a lot of you found that to be extremely helpful, so I’m sharing it here.

Technology Made Simple

[Solution]Problem 59:Invert Binary Tree [Google]

To learn more about the newsletter, check our detailed About Page + FAQs To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email. Recommend this publication to Substack over here…

2 years ago · Devansh

The biggest reason that a lot of people struggle with recursive code is all the moving parts involved in making sure things work. In high-stress, time-bound environments like interviews or exams, this can often get overwhelming. This template allows you to avoid this problem by giving you a clear step-by-step guide to work through. By focusing on one step at a time, you will be able to solve the problems in a clear and smooth manner. And this is a huge green flag for your interviewers.

Your Leetcode interviews test for the first 4 pillars. Going step by step is a great way to highlight all of them.

The template goes as follows-

Check for termination cases- The first thing you check in every recursive function is the termination/base cases. These cases tend to be easy to implement, so you can get them out of the way relatively easily. And once you have gone through these, you just need to worry about the recursive cases. Taking care of the base cases first also allows you to implement the recursive leap of faith, which we covered on this Technique Tuesday.
Do the processing- This is generally associated with the outcome that we are expected to produce. For our invert function, this means swapping right and left nodes with each other. If your solution involves backtracking, you want to mark your current state as visited.
Move on to the recursive case- Notice how long we took to get here. We have eliminated a lot of the other moving parts, so we can focus on the recursion itself. You can now call the recursive function on all the variants you need to deal with. In graph traversal, this means calling it on all the neighbors. Etc etc.
Reset side effects- Sometimes you would have made changes to your code/states that you want to undo. This might involve resetting values of global variables. In your Leetcode style interviews/competitive programming, this would become a factor with backtracking.

Take a look at the following recursive function and identify the different parts of the functions. Notice how implementing this template will allow you to solve this very tricky coding problem. If you want to see the full problem, check out the post [Solution]Problem 18: Pack Words on Board [Google]. This was a sample solution shared with everybody, so even my free subs will be able to access it.

def max_words(board, n, m, words, visited, r, c, curr_word):
    if r < 0 or r >= n or c < 0 or c >= m or visited[r][c]:
        return []

    curr_word += board[r][c]
    # if no words in |words| start with |curr_word|, then return early.
    if not any(word.startswith(curr_word) for word in words):
        return []

    visited[r][c] = True

    max_word_set = []
    if curr_word in words:
        # A valid words has been found: terminate current word search and start a new one
        for r, row in enumerate(board):
            for c, val in enumerate(row):
                curr_word_set = max_words(board, n, m, words, visited, r, c, '')
                if len(curr_word_set) > len(max_word_set):
                    max_word_set = curr_word_set
        max_word_set.append(curr_word)
    else:
        for dr, dc in DIRECTIONS:
            curr_word_set = max_words(board, n, m, words, visited, r + dr, c + dc, curr_word)
            if len(curr_word_set) > len(max_word_set):
                max_word_set = curr_word_set

    visited[r][c] = False
    return max_word_set

If you found this content valuable, consider becoming a premium member of this newsletter. Premium members get access to many such solutions along with other exclusive content on the Tech Industry, Interviewing secrets, and Building an amazing career in tech. You can get two weeks for free by using the following link. Keep in mind that this newsletter has a complete satisfaction guarantee. If within the first 60 days, you’re not happy with the newsletter, all you have to do is reach out to me. I will give you a complete refund, no strings attached. So there’s no risk to you.

One final point- The template works best when you isolate the recursion to helper functions. This makes your whole code much neater. Will do a separate Technique Tuesdays on Helper Functions, since they are such a powerful tool.

Make sure you go through the archives on the Substack website to read through the older posts. They have a lot of knowledge in them.

I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.

Get 20% off for 1 year

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. 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

I see you living the dream.

Go kill all and Stay Woke,

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