1
00:00:00,600 --> 00:00:04,830
We have discussed various topics with respect to recursion.

2
00:00:04,830 --> 00:00:11,250
Remember, recursion is very, very important to ace coding interviews.

3
00:00:11,280 --> 00:00:19,800
Now recursion, as we will see in the future part of this course, is in fact the parent of various

4
00:00:19,800 --> 00:00:27,780
other topics such as backtracking, dynamic programming, greedy algorithms, divide and conquer approaches,

5
00:00:27,780 --> 00:00:34,200
etc. now, backtracking basically is just a guided form of recursion.

6
00:00:34,200 --> 00:00:35,760
More of that later.

7
00:00:35,760 --> 00:00:39,750
When it comes to dynamic programming, we will see that.

8
00:00:39,750 --> 00:00:47,760
First we will write the recursive solution before we go ahead and build the top down dynamic programming

9
00:00:47,760 --> 00:00:49,440
approach for questions.

10
00:00:49,440 --> 00:00:53,130
Now the top down approach is what is called memoization.

11
00:00:53,130 --> 00:00:55,680
And this also uses recursion.

12
00:00:55,680 --> 00:01:01,320
Now once we have come up with this approach, we will again use the intuition that we will get from

13
00:01:01,320 --> 00:01:09,090
this to go ahead and build the iterative approach or the bottom up or tabulation approach in dynamic

14
00:01:09,090 --> 00:01:18,030
programming, when it comes to greedy algorithms, recursion is where you try to optimize the next step.

15
00:01:18,030 --> 00:01:20,400
Again, we use recursion for this.

16
00:01:20,400 --> 00:01:22,920
In divide and conquer algorithms.

17
00:01:22,920 --> 00:01:29,160
Again, you will see that we will use recursion to divide the problem into subproblems, and we will

18
00:01:29,160 --> 00:01:33,390
come up with the solution by solving each subproblem independently.

19
00:01:33,390 --> 00:01:37,920
So notice that recursion is a very, very important topic.

20
00:01:37,920 --> 00:01:42,840
And you have to master this to be able to ace coding interview questions.

21
00:01:42,840 --> 00:01:50,910
Also remember, if the question at hand is such that there is a tree or you are having multiple branches,

22
00:01:50,910 --> 00:01:53,130
for example, something like this.

23
00:01:53,130 --> 00:01:58,860
Okay, so in this case probably you can use recursion to solve the question.

24
00:01:58,860 --> 00:02:05,850
Another way of thinking about recursion is that if the question at hand is such that you can divide

25
00:02:05,850 --> 00:02:12,030
the original problem into similar subproblems, again, consider using recursion.

26
00:02:12,030 --> 00:02:18,870
Let's now proceed and take a look at some interesting coding interview questions, such as the Josephus

27
00:02:18,870 --> 00:02:24,000
problem, the kth grammar problem, the Tower of Hanoi problem, etc..