Why is the recurrence relation of recursive factorial algorithm this?
T(n)=1 for n=0
T(n)=1+T(n-1) for n>0
Why is it not this?
T(n)=1 for n=0
T(n)=n*T(n-1) for n>0
Putting values of n i.e 1,2,3,4...... the second recurrence relation holds(The factorials are correctly calculated) not the first one.
Answer
we generally use recurrence relation to find the time complexity of algorithm.
Here, the function T(n) is not actually for calculating the value of an factorial but it is telling you about the time complexity of the factorial algorithm.
It means for finding a factorial of n it will take 1 more operation than factorial of n-1 (i.e. T(n)=T(n-1)+1) and so on.
so correct recurrence relation for a recursive factorial algorithm is T(n)=1 for n=0 T(n)=1+T(n-1) for n>0 not that you mentioned later.
like recurrence for tower of hanoi is T(n)=2T(n-1)+1 for n>0;
Update: It does not have anything to do with implementation generally. But recurrence can give an intuition of programming paradigm for eg if T(n)=2*T(n/2)+n (merge sort) this gives kind of intuition for divide and conquer because we are diving n into half.
Also, If you will solve the equation it will give you a bound on running time.eg big oh notation.