zloznosc obliczeniowa rekurencyjnego algorytmu na silnie

0

Tak się zacząłem zastanawiać bo nie jestem pewien czy złozoność obliczeniowa rekurencyjnego wywołania silni jest θ(n) czy może jest wykładnicza a ja czegoś nie rozumiem?

 unsigned long long recFactorial(unsigned long long n)
{
	if (n == 0)
		return 1;
	else
	return n*recFactorial(n - 1);


}
1

Asymptotycznie oczywiscie jest liniowa. Pytanie tylko w czym to implementujesz, bo jeśli w języku bez optymaliacji rekurencji ogonowej to będzie się liczyło bardzo długo, ze względu na koszt wywołania funkcji. Bo masz tam tylko jedno porównanie i jedno mnożenie, czyli w asemblerze tam byłoby raptem cmp, je, mul, mov, ret, ale oprócz tego będzie tam niestety także tworzenie nowej ramki stosu i jej niszczenie, więc nagle narzut na samo wywołanie funkcji będzie większy niż to co funkcja robi. Co więcej jest język nie wspiera optymalizacji rekurencji ogonowej to stos będzie rósł bo wszystkie wywołania będą "wisieć" dopóki nie dojdziemy do dna rekurencji.

1 użytkowników online, w tym zalogowanych: 0, gości: 1