1
00:00:00,140 --> 00:00:04,790
We have developed a good understanding of what backtracking is.

2
00:00:04,790 --> 00:00:08,870
Remember, backtracking is a recursive algorithm.

3
00:00:08,870 --> 00:00:13,880
But then let's discuss how it is different from simple recursion.

4
00:00:13,910 --> 00:00:22,160
Now recursion is, as we have discussed, just a function calling itself until a base condition or a

5
00:00:22,160 --> 00:00:23,540
terminating condition.

6
00:00:23,540 --> 00:00:29,030
When it comes to backtracking, backtracking is controlled recursion.

7
00:00:29,030 --> 00:00:34,520
And remember, in backtracking, the state of the problem is changed in place.

8
00:00:34,970 --> 00:00:42,770
So the way that recursion is implemented in backtracking, which is different from simple recursion,

9
00:00:42,770 --> 00:00:46,280
is that over here you have controlled recursion.

10
00:00:46,280 --> 00:00:47,810
And what does this mean?

11
00:00:47,810 --> 00:00:55,160
Controlled recursion means that whenever we identify that a path is not leading to the solution, we

12
00:00:55,160 --> 00:00:57,920
prune that path or we abandon it.

13
00:00:57,980 --> 00:01:03,080
So this is how backtracking is different from simple recursion.