Rekursiivne vs iteratiivne meetod

Iteratiivne meetod tähendab, et kasutatakse tsükleid. Rekursiivset funktsiooni on alati võimalik ümber kirjutada nii, et see oleks iteratiivne.

Faktoriaali iteratiivne arvutamine

def factorial_iter(n):
    if n == 0:
        return 1

    answer = 1
    for i in range(1, n + 1): # range(1, n + 1) => [1, 2, 3, 4, 5, 6, ..., n - 1, n]
        answer = answer * i

    return answer

Sellel juhul on see meetod efektiivsem, kuna see suudab suurte arvude faktoriaali arvutada. Rekursiivne meetod viskab aga suurte arvude korral RecursionError, sest on liiga palju rekursiivseid väljakutseid.

Koodinäide: Fibonacci arvud

Meil on piisavalt teadmisi Fibobacci arvudest.

F[n] = F[n-1] + F[n-2]
F[0] = 0, F[1] = 1, F[2] = 1

Kirjutame funktsiooni.

Sisend: n - indeks Fibonacci arvujadas. Väljund: Fibonacci arv, mis vastab indeksile n.

def fib(n):
     if n == 0:
         return 0

     if n == 1 or n == 2:
         return 1

     return fib(n - 1) + fib(n - 2)

Iteratiivne funktsioon

Siin kasutame kahte muutujat, et hoida mälus kahte viimast liiget. Iga kord, kui arvutame uut väärtust cur, paneme prev2 väärtuse muutujasse prev1 ja cur väärtuse paneme muutujasse prev2. Võiks ka kasutada list-i, aga see võtab rohkem mälu.

def fib_iter(n):
    if n == 0:
        return 0

    if n == 1:
        return 1

    prev1 = 0 # num0
    prev2 = 1 # num1

    # if n < 2 answer is already given
    for i in range(2, n + 1):
        cur = prev1 + prev2 # new value (num2)
        prev1 = prev2 # num1 becomes num0
        prev2 = cur   # num2 becomes num1

    return prev2

Efektiivsus

Iteratiivne meetod töötab kiiremini kui rekursiivne, sest rekursiivne ei jäta meelde kahte viimast väärtust ja arvutab neid kogu aeg uuesti. Nüüd on meil idee, kuidas teha rekursiivset lahendust kiiremaks: jätame meelde vanu väärtusi ja anname need väljakutsel lisaargumendina.

def fib(n, cache={0: 0, 1: 1, 2: 1}): # cache already contains 3 known values
    if n in cache: # if value is in the cache, return it
        return cache[n]

    # if the value is not in the cache, add and return it
    # notice that we add new value to the cache and give it as the additional argument
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

Parem kood:

def fib(n, cache=None):
    if cache is None:
        cache = {0: 0, 1: 1, 2: 1} # cache already contains 3 known values

    if n in cache: # if value is in the cache, return it
        return cache[n]

    # if the value is not in the cache, add and return it
    # notice that we add new value to the cache and give it as the additional argument
    cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
    return cache[n]

Võrdleme kiirust. Selleks arvutame 500 väärtust ja vaatame, kui palju aega see kummalgi meetodil võtab.

Kood võrdlemiseks:

import time

if __name__ == '__main__':
    print("test for recursive method")
    started = time.time()
    for i in range(500):
        fib(i)

    print("Total: " + str(time.time() - started) + " secs")

    print("test for iterative method")
    started = time.time()
    for i in range(500):
        fib_iter(i)

    print("Total: " + str(time.time() - started) + " secs")

test for recursive method
Total: 0.0004994869232177734 secs
test for iterative method
Total: 0.021016836166381836 secs

Rekursiivne meetod, mis jätab väärtusi meelde, osutus kiiremaks kui iteratiivne. Kuid on arusaadav, et rekursiivne meetod kasutab ka palju mälu. Kui mälu ei kasuta, siis on arvutil juba raske 30. väärtust arvutada. Võite proovida sama asja faktoriaali lahenduse jaoks.