1

Try to write down the recurrence relation for running time of recursive algorithm for finding factorial(n). Suggest the base cases for that recurrence relation.

I could not solve this problem, Can someone explain it?

User9215122
  • 21
  • 4
  • what algo to compute `n!` (there are more than just naive one like swinging primes or [this one](https://stackoverflow.com/a/18333853/2521214))? what datatype (fixed bitwidth, arbitrary size)? What platform is this for as runtime depends heavily on HW used ... better is to use big O notations for this but if you insist on runtime then you can still measure it ... – Spektre Feb 07 '20 at 08:48

1 Answers1

2

Factorial can be determine by this algorithm

1: Read number n.
2. Initialize i and fact to 1.
3. Repeat step 4 and step 5 while i is not equal to n.
4. fact <- fact * i
5. i <- i +1
6. Return fact

In short if we write down this by recurrence relation then it will be -

int Fact(int num) {
    if(num <= 1) {
        return 1;
    }
    else {
        return num * Fact(num - 1);
    }
}

Basically factorial of a number num will be factorial of Fact[num - 1] * num.

So we can write it like this - 

int fact[num+1];
fact[0] = 1;
for(int i = 1; i <= num; i++) {
    fact[i] = fact[i-1] * i;    // recurrence relation is here
}
printf("%d\n", fact[num]);
Faruk Hossain
  • 1,205
  • 5
  • 12
  • I do not see any runntime recurence or big O here ... just `n!` results that is not what OP is asking about. However OP is missing crucial specifications to answer it correctly ... – Spektre Feb 07 '20 at 08:46