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: 
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.
Where did you find the first one ? It's completely wrong.

It's only going to add 1 each time whatever the value is .