Czy funkcje rekurencyjne opłacają się w pythonie?

Question

Witam, napisałem sobie dwie funkcje liczące kolejne potęgi dwójki, jedną iteracyjnie za pomocą for'a, drugą rekurencyjnie, zaimplementowałem timery żeby sprawdzić jaka będzie różnica w czasie i ku mojemu zdziwieniu pokazują że funkcja licząca za pomocą for'a działa szybciej, dodatkowo maksymalna potęga dwójki jaką jest w stanie policzyć mój komputer rekurencyjnie to 997(8gb ramu), może mi ktoś przybliżyć jak to wygląda z funkcjami rekurencyjnymi w pythonie? Czy biblioteki tego języka są napisane jakoś inaczej w taki sposób że funkcje rekurencyjne się po prostu nie opłacają? Prosiłbym jeszcze o rady na co warto zwrócić uwagę przy przenoszeniu się z innego języka.

import time

def pot(podstawa, potega):
    wynik=podstawa
    for i in range(potega-1):
        wynik=wynik*podstawa
    return wynik


def potreku(podstawa, potega):
    if potega==0: return 1
    else: return podstawa*potreku(podstawa, potega-1)


start=0.0
stop=0.0
czas=0.0

start = time.time()
pot(2,997)
stop = time.time()
czas = stop-start
print(czas)


start = time.time()
potreku(2,997)
stop = time.time()
czas=stop-start
print(czas)

 

Comments

(pewnie wiesz, ale na wszelki wypadek dla przyszłych czytających: potęgi w Pythonie można policzyć też po prostu tak:)

wynik = 2 ** 997

 

Answer 1

Przy rekurencji za każdym razem, gdy wywołujesz rekurencyjnie funkcję komputer musi zadeklarować nowy obszar w pamięci. Pamięć jest tutaj dużym ograniczeniem określającym jaki zakres liczb możesz obliczać w ten sposób. Dodatkowo operacja przydzielania pamięci jest powolna i mało wydajna. Przy wykorzystaniu pętli tylko raz deklarujesz wszystkie zmienne i działasz na nich w obrębie jednej funkcji - obliczenia są znacznie szybsze.

Wnioski: kopiowanie pamięci jest powolne i warto o tym pamiętać.

Answer 2

Rekurencja w ogóle jest mniej opłacalna jeśli chodzi o złożoność obliczeniową a im większe liczby, tym mniej się opłaca. Właśnie dlatego wymyślono programowanie dynamiczne.