Obliczanie wartości potęgi o podstawie i wykładniku naturalnym

Specyfikacja problemu:

Dane:

• p – liczba naturalna; podstawa potęgi; $p>0$

• w – liczba naturalna; wykładnik potęgi; $w>0$

Wynik:

• program zwraca wynik potęgowania $p^w$

Sposób iteracyjny

def potega_iter(p, w):
    wynik = 1
	while w > 0:
		wynik = wynik * p
		w -= 1

	return wynik

Sposób rekurencyjny

def potega_rekur(p, w):
	if w == 1:
		return p

	return p * potega_rekur(p, w - 1)

Obliczanie silni

Specyfikacja problemu:

Dane:

• liczba – liczba naturalna

Wynik:

• program zwraca wartość silni podanej liczby naturalnej

Sposób iteracyjny

def silnia(liczba):  
	if liczba < 2: 
		return 1
	else:
		for i in range(2,liczba):
			liczba *= i
		return liczba

Sposób rekurencyjny

def silnia (liczba):
	if liczba < 1:
		return 1
	else:
		return liczba * silnia(liczba - 1)

Analiza i porównanie

Możemy zauważyć, że liczba operacji mnożenia, jaką wykonują obie wersje funkcji, jest identyczna. Natomiast różny jest czas niezbędny do ich wykonania. W przypadku funkcji rekurencyjnej obserwujemy znacznie większy czas niezbędny do wykonania obliczenia. Wynika to z faktu, że wykonywanie funkcji rekurencyjnych obarczone jest zawsze narzutem czasowym związanym z obsługą stosustosstosu, a więc dostępem do pamięci, w której zapamiętywane są adresy powrotu z kolejnych wywołań rekurencyjnych. W przypadku wersji iteracyjnej czas niezbędny na wykonywanie mnożeń jest znacznie krótszy. W obu przypadkach obserwujemy liniowy wzrost czasu wraz ze wzrostem liczby mnożeń, co jest normalną sytuacją.

Możemy również zauważyć, że w wersji rekurencyjnej funkcja ma krótszy kod (choć w tym przypadku nie jest on znacznie krótszy).

Słownik