Mastering Recursion & Backtracking Techniques

Day 1 Recording

Watch Day 1 Recording

Day 2 Recording

Watch Day 2 Recording

Introduction

Recursion is a programming technique that allows a function to call itself repeatedly. It's particularly useful for solving problems that have a recursive structure.

How Recursion Works

1. Recursion involves a function calling itself.
2. This process continues until a base case is reached, upon which the recursion stops.
3. Each recursive call contributes to solving a smaller instance of the problem until the base case is met.

Steps to Understand and Approach a Problem

1. Identify if a problem can be broken down into smaller problems.
2. Formulate the recurrence relation, if needed.
3. Visualize the recursive tree.
4. Analyze the function flow:
   • Understand the stack behavior.
   • Focus on left and right tree calls.
   • Utilize pen and paper to draw trees and pointers repeatedly.
5. Observe value returns at each step and identify the exit points.

When to Use Recursion

Use recursion when the problem has a recursive structure and can be broken down into similar subproblems.

When Not to Use Recursion

Avoid recursion for problems lacking a recursive structure, as it can lead to inefficiency.

Benefits of Recursion

• Concise and understandable code.
• Efficient solution for problems with recursive structure.

Recursion Problems

Easy

• Sum Triangle from Array GFG
• Maximum and Minimum value in an array GFG
• Binary Search using recursion leetcode
• First Uppercase Letter in a String GFG
• Reverse String leetcode
• Print 1 To N Without Loop GFG
• Fibonacci Number leetcode
• Special Fibonacci CodeChef
• Length of string using Recursion GFG
• Geek-onacci Number GFG
• Recursive Bubble Sort GFG
• Recursive Insertion Sort GFG
• Sum of digit of a number using Recursion GFG
• Product of two numbers using Recursion GFG
• Check Prime or not GFG
• Sum of Natural numbers using Recursion GFG
• Power of Two leetcode
• Power of Three leetcode
• Power of Four leetcode
• Write a recursive function for given n and a to determine x:

      n = a ^ x 
      a = 2, 3, 4
      (2 ^ -31) <= n <= (2 ^ 31) - 1      

• Write a recursive function that returns the factorial of a number. HackerRank
• Write a recursive function to check whether an array is sorted or not. GFG
• Number of Steps to Reduce a Number to Zero. leetcode
• Check for balanced paranthesis using recursion without stack. GFG
• Remove consecutive duplicate characters from a string. GFG
• Print all possible palindromic partitions of a string. GFG
• Power Set of permutations of a string in Lexicographic order. GFG

Medium

• Combination Sum leetcode
• Word Search leetcode
• Target sum leetcode
• Find Kth Bit in Nth Binary String leetcode
• K-th Symbol in Grammar leetcode
• Count Good Numbers leetcode
• N Digit numbers with digits in increasing order GFG
• Pow(x, n) leetcode
• Minimum Non-Zero Product of the Array Elements leetcode
• Handshakes GFG
• HackerRank
• Divisible Subset Codechef
• Perfect squaresleetcode
• decode stringleetcode
• find the winner of the circular game leetcode
• Different ways to add parantheses in the expression leetcode
• Letter Combinations of a Phone Number leetcode
• Predict the winner. leetcode
• Gray code GFG Google
• Combination Sum II leetcode
• combination Sum III leetcode
• Sudoku Solver leetcode
• Letter tile possibilities leetcode
• All Paths From Source to Target leetcode
• Sort a stack using recursion GFG
• Reverse a stack using recursion GFG
• Beautiful Arrangement leetcode
• Lowest Common Ancestor of a Binary Tree GFG Amex
• Prime numbers after prime P with sum S GFG
• Path with Maximum Gold leetcode
• Longest Possible Route in a Matrix with Hurdles GFG
• Tug of war GFG Adobe
• Rat in a maze GFG
• Reorder List leetcode

Hard

• Parsing A Boolean Expression leetcode
• Special Binary String leetcode
• Permutation Sequence leetcode
• Next Happy Number GFG
• Basic Calculator leetcode
• Integer to English Words leetcode
• Maximize Number of Nice Divisors leetcode
• N Queens leetcode
• N Queens II leetcode
• Word break II leetcode Google
• Unique paths III leetcode
• Find shortest safe route in a path with landmines GFG Google
• Minimum steps to destination GFG Amex Adobe
• Hamiltonian Cycle GFG
• M colorning problem GFG
• The Knight's tour GFG
• Maximum number possible by doing at-most K swaps GFG
• HackerRank
• Concatenated Wordsleetcode