Sabarekursioon

Funktsioonis on sabarekursioon siis, kui selle sama funktsiooni väljakutse on viimane tegevus.

def foo():
    ...
    foo()
    # no more actions

Koodinäide: Faktoriaali arvutamine

Kirjutame funktsiooni, mis arvutab arvu faktoriaali.

Faktoriaal n! on kõikide eelnevate arvude korrutis.

n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
5! = 5 * 4 * 3 * 2 * 1 = 120
3! = 3 * 2 * 1 = 6

Kus siin võiks olla rekursioon? On vaja leida seos faktoriaalide jadast nii, et iga järgmine liige sõltuks eelmisest liikmest.

5! = 5 * 4 * 3 * 2 * 1
4! =     4 * 3 * 2 * 1

Näeme, et nendel kahel avaldisel on ühisosa. Võime kirjutada nii: 5! = 4! * 5 ehk n! = n * (n-1)!

Vaatame, kas see ikkagi kehtib üldjuhul:

n!     = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
(n-1)! =     (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1

n! = n * (n-1)!

Ikka kehtib. Nüüd on meil valem olemas.

n! = n * (n-1)!

Praegu on vaja tingimust, mil saame anda vastuse ilma rekursioonita. Matemaatikas on tõestatud, et 0! = 1. Seda ongi meil vaja!

Nüüd kirjutame funktsiooni. On selge, et funktsioonil peab olema üks sisendargument. See on mingi arv n, mille jaoks me faktoriaali arvutame.

def factorial(n):

Praegu tasub kohe kirja panna tingimus, et kui n võrdub 0-ga, siis funktsioon tagastab 1.

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

Kui n ei võrdu 0-ga, siis me leidsime, et n! = n * (n-1)!

def factorial(n):
    if n == 0:
        return 1 # get here if only n equals 0

    return n * factorial(n - 1)

Kuidas funktsioon töötab:

Nt. factorial(3)

factorial(3):
1. 3 = 0? => False
2. return 3 * factorial(2)
    Nüüd on vaja arvutada factorial(2)
    factorial(2):
    2.1. 2 = 0? => False
    2.2. return 2 * factorial(1)
        Nüüd on vaja arvutada factorial(1)
        factorial(1):
        2.2.1. 1 = 0? => False
        2.2.2. return 1 * factorial(0)
            Nüüd on vaja arvutada factorial(0)
            factorial(0):
            2.2.2.1. 0 = 0? True => return 1
            factorial(0) = 1
        2.2.3. return 1 * 1
        factorial(1) = 1
    2.3. return 2 * 1
    factorial(2) = 2
3. return 3 * 2
factorial(3) = 6

Kokkuvõte

1. Leia seos eelmise ja järgmise väärtuste vahel.

2. Määra tingimus(ed), mille korral võib kohe vastuse anda.