Hey everyone.
Welcome back.
Another important term that you will see with respect to recursion is the recurrence relation.
Now the recurrence relation is the expression that talks about the solution of a problem as the function
of the solutions to smaller instances of the same problem.
We have seen that recursion is appropriate to be used when you can solve the original problem by identifying
the solution to subproblems.
This is what the recurrence relation talks about.
It expresses the solution of the problem as the solution of the subproblems.
For example, if you want to find the factorial, as we have discussed previously, the recurrence relation
would be f of n is equal to n into f of n minus one.
Notice that this is the original problem, and this over here is the subproblem because.
Remember n factorial is equal to n into n minus one factorial.
Now let's take another example.
We have discussed the case where you wanted to print the sequence 321123.
What would be the recurrence relation?
For this?
We have seen that the recursive case for that was print n, and then do a recursive call for the same
function and again print n.
So this over here is the recurrence relation.
And we have to do this when n is greater than zero.
Notice that the recurrence relation actually talks about the recursive case.
It does not talk about the base case, but it talks about how you can solve the original problem using
the solutions to the subproblems.