Рекуррентное соотношение для времени выполнения рекурсивного алгоритма нахождения факториала (n)

Question

Попробуйте записать рекуррентное отношение для времени выполнения рекурсивного алгоритма нахождения факториала (n). Предложите базовые случаи для этого рекуррентного отношения.

Я не смог решить эту проблему, может кто-нибудь объяснить это?

Answer 1

Факториал можно определить с помощью этого алгоритма

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

Короче, если мы запишем это по рекуррентному соотношению, то оно будет -

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

В основном факториал числа num будет факториалом Fact[num - 1] * num.

Так что мы можем написать это так -

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]);