Solving a recurrence relation

[tragicallylost]

Hi. The problem is to write a recursive function for n!, give the recurrence relation, and solve it.

For the recurrence relation, I have:
Fact(0) = 1
Fact(1) = 1
Fact(n) = n*Fact(n-1)

In the text, it gives a formula to use when the recurrence relation is of the form S(n) = cS(n-1) + g(n).

The formula is S(n) = c^(n-1)*S(1) + sum{i = 2 to n} c^(n-i)*g(i).

When I try to apply it to my problem, I come up with n as c and obtain:
n^(n-1) +sum{i=2 to n} n^(n-i).

I have no idea on how to solve this. If someone could lead me in the right direction, it would help GREATLY! thanks.

 

[tkhunny]

You have it.

Here it is in mostly words.

Define Fact(n)
--- If n = 1
--- Then Return with 1
--- Else Return with n*Fact(n-1)
--- End If
End Define