1
00:00:00,890 --> 00:00:01,820
Hey everyone.

2
00:00:01,820 --> 00:00:02,900
Welcome back.

3
00:00:02,900 --> 00:00:10,550
Another important term that you will see with respect to recursion is the recurrence relation.

4
00:00:10,550 --> 00:00:20,240
Now the recurrence relation is the expression that talks about the solution of a problem as the function

5
00:00:20,240 --> 00:00:24,440
of the solutions to smaller instances of the same problem.

6
00:00:24,440 --> 00:00:33,200
We have seen that recursion is appropriate to be used when you can solve the original problem by identifying

7
00:00:33,200 --> 00:00:35,480
the solution to subproblems.

8
00:00:35,480 --> 00:00:39,470
This is what the recurrence relation talks about.

9
00:00:39,470 --> 00:00:45,500
It expresses the solution of the problem as the solution of the subproblems.

10
00:00:45,500 --> 00:00:53,090
For example, if you want to find the factorial, as we have discussed previously, the recurrence relation

11
00:00:53,090 --> 00:00:58,820
would be f of n is equal to n into f of n minus one.

12
00:00:58,820 --> 00:01:05,210
Notice that this is the original problem, and this over here is the subproblem because.

13
00:01:05,210 --> 00:01:10,700
Remember n factorial is equal to n into n minus one factorial.

14
00:01:10,700 --> 00:01:13,100
Now let's take another example.

15
00:01:13,100 --> 00:01:20,510
We have discussed the case where you wanted to print the sequence 321123.

16
00:01:20,510 --> 00:01:22,760
What would be the recurrence relation?

17
00:01:22,760 --> 00:01:23,570
For this?

18
00:01:23,570 --> 00:01:31,640
We have seen that the recursive case for that was print n, and then do a recursive call for the same

19
00:01:31,640 --> 00:01:34,010
function and again print n.

20
00:01:34,010 --> 00:01:38,450
So this over here is the recurrence relation.

21
00:01:38,450 --> 00:01:41,420
And we have to do this when n is greater than zero.

22
00:01:41,420 --> 00:01:47,780
Notice that the recurrence relation actually talks about the recursive case.

23
00:01:47,780 --> 00:01:54,830
It does not talk about the base case, but it talks about how you can solve the original problem using

24
00:01:54,830 --> 00:01:57,770
the solutions to the subproblems.