We have discussed various topics with respect to recursion.
Remember, recursion is very, very important to ace coding interviews.
Now recursion, as we will see in the future part of this course, is in fact the parent of various
other topics such as backtracking, dynamic programming, greedy algorithms, divide and conquer approaches,
etc. now, backtracking basically is just a guided form of recursion.
More of that later.
When it comes to dynamic programming, we will see that.
First we will write the recursive solution before we go ahead and build the top down dynamic programming
approach for questions.
Now the top down approach is what is called memoization.
And this also uses recursion.
Now once we have come up with this approach, we will again use the intuition that we will get from
this to go ahead and build the iterative approach or the bottom up or tabulation approach in dynamic
programming, when it comes to greedy algorithms, recursion is where you try to optimize the next step.
Again, we use recursion for this.
In divide and conquer algorithms.
Again, you will see that we will use recursion to divide the problem into subproblems, and we will
come up with the solution by solving each subproblem independently.
So notice that recursion is a very, very important topic.
And you have to master this to be able to ace coding interview questions.
Also remember, if the question at hand is such that there is a tree or you are having multiple branches,
for example, something like this.
Okay, so in this case probably you can use recursion to solve the question.
Another way of thinking about recursion is that if the question at hand is such that you can divide
the original problem into similar subproblems, again, consider using recursion.
Let's now proceed and take a look at some interesting coding interview questions, such as the Josephus
problem, the kth grammar problem, the Tower of Hanoi problem, etc..