Recursion Made Easy !

The term "recursion" & "dynamic programming" might make you feel uneasy at first. One of the main reasons people struggle with it is that they lack a clear framework for understanding and approaching it effectively.

This article will explore six fundamental recursive patterns that can classify nearly all recursive problems. These patterns can be applied to most recursive questions.

---

Framework of Recursion :

There are generally three frameworks to solve a recursive problem , BTW we can identify a recursive problem when we are given a decision space and the inputs are made smaller by the choices & decisions.

Based on this idea there are generally two frameworks for recursion:

1. Induction-Hypothesis-Base Condition - This basically is derived from Mathematical Induction(Class 10) & proving mathematical theorems 🫠. It works when you are not given choices & need to make input smaller eventually,

• Base Condition - This is the rule imposed to stop the recursion calls and exit the function. Generally smallest valid or smallest invalid input are considered as base conditions.

• Hypothesis - So if we have to calculate sum of first 10 natural numbers by a function sum1(10) [sum1(n)] for e.g., we have to device the calculation till 9 natural numbers till sum1(9) [sum1(n-1)] which is our hypothesis.

• Induction - This is where the recursive calls are returned till the base condition were met and return the sum of all 10 natural numbers [sum1(10)].

2. Recursive Tree - works when you are given the decisions to be made.

In this method we are having an input space and we have choices to make consider the input or not. To reach the optimal solution, we have to take decisions to make these choices to the input space. As the decisons are made the input space is being restricted or reduced , and the inputs eventually get smaller in recursion .

This would be easier if it could be deduced into a tree form.

This Tree has child nodes for each node which are all the choices to be made for reaching a optimal decision.

For example we need to find the fibonacci of 4 :

             Fib(4)
            /    \
         Fib(3)    Fib(2)
        /    \       /   \
     Fib(2) Fib(1) Fib(1)  Fib(0)
    /    \
  Fib(1)   Fib(0)

This is the recursive tree where there is a choice can be made to make the input smaller , and the base conditions here are Fib(1),Fib(0) where the recursive calls are exited and solution is returned by the function for given input space.

---

Most recursive problems follow core patterns which make it more easier and faster to solve a problem in a interview 🚀.

The six patterns are: Iteration, Subproblems, Selection, Ordering, Divide & Conquer, and Depth-First Search.

Core Recursive Patterns

1. Iteration (Recursion as a Loop)
   • Some problems that are commonly solved using loops can also be solved recursively.
   • Example: Printing numbers from 1 to N using recursion instead of a loop.
   • Key Idea: Instead of iterating explicitly, use recursion to repeatedly call the function with a reduced problem size.

How it works: The function keeps calling itself with n-1 until n reaches 0, then prints the numbers in reverse order.

---

1. Subproblems (Breaking into Smaller Problems)
   • Many recursive problems can be solved by breaking them into smaller subproblems that follow the same pattern.
   • Example: Factorial, Fibonacci sequence.
   • Key Idea: Express the solution in terms of a smaller instance of the same problem.

How it works: Each call reduces the problem by 1 until it reaches the base case (factorial(1) = 1). Then, results are combined while returning from recursive calls.

---

1. Selection (Choosing Among Options)
   • Some problems require exploring multiple possibilities and choosing the best one.
   • Example: Subset generation, coin change problem.
   • Key Idea: Try different choices recursively and select the best or valid one.

How it works: At each step, we either include the current element in the subset or exclude it, recursively generating all possible subsets.

---

1. Ordering (Arranging Elements Recursively)
   • Some problems involve arranging elements in different orders.
   • Example: Generating permutations of a string or array.
   • Key Idea: Swap elements and recursively generate all possible orders.

How it works: We recursively swap characters at different positions to generate all permutations.

---

1. Divide & Conquer (Splitting problem into smaller parts)
   • This is a powerful approach where we divide a problem into smaller independent parts, solve them recursively, and combine results.
   • Example: Merge Sort, Quick Sort, Binary Search.
   • Key Idea: Divide the problem into two or more parts, solve them independently, and merge the results.

How it works: The array is split into halves, sorted recursively, and merged back together.

---

1. Depth-First Search (Exploring Recursive Paths in Trees & Graphs)

   • Used for problems related to trees and graphs, where we explore one path deeply before backtracking.
   • Example: Traversing a binary tree (Preorder, Inorder, Postorder), solving mazes.
   • Key Idea: Recursively visit nodes or paths until a base condition is met.

   How it works: We recursively visit the left subtree, process the node, and then visit the right subtree.

---

Conclusion

By categorizing recursion problems into these six patterns, you can approach recursion systematically:

• Iteration: Use recursion as a loop.
• Subproblems: Solve a smaller version of the problem.
• Selection: Explore different choices.
• Ordering: Arrange elements recursively.
• Divide & Conquer: Break the problem into independent parts.
• Depth-First Search: Explore recursive paths in graphs/trees.

Once you recognize the pattern in a problem, it becomes much easier to solve it using recursion! 🚀

---

Important Questions

Climbing Stairs, Subsequences of String, Coin Change, Cut into Segments, Maximum Sum of Non-adjacent Elements, Last Occurrence of a Character in a String, Reverse a String, Add Strings, String is Palindrome or Not, Print All Subarrays Using Recursion, House Robber, Integer to English Words, Wildcard Matching, Perfect Squares, Minimum Cost for Tickets, Number of Dice Rolls with Target Sum.

---

Resources

• ***Aditya Verma Recursion Playlist,
• **Striver Playlist,
• *Neetcode

I hope recursion is really made easy now 😁 !

 Do follow me !

Understanding DSA Patterns -Do Visit