Recurrence Relation

Question

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 1

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.