Recurrence with recursion tree method
Solving Recurrence with recursion tree method
To understand Recurrence Relation lets take the following code in c language:
void Test(int num)
{
if(num>0)
{
printf("%d",num);
Test(num-1);
}
}
In the above code, the recurrence relation tree will be:
Lets input num as 3.
Here, when the value of num is 3, the algorithm will print the number 3 and call itself with value 3-1=2.
Similarly again the condition num>0 will be true.
So it will again print the current value i.e. 2 and call itself with value 2-1=1.
Since the condition num>0 is true again, then it will print the value 1 and again call itself with value now 1-1=0.
This time the condition num>0 will go false and the code will terminate.
So, for input 3, the number of calls made by the funtion will be 4 (Test(3), Test(2), Test(1), Test(0)).
And the number of results printed will be 3 (i.e. 3,2,1)
And for input n, the number of call will be n+1 and the number of times the result will be printed is n.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
