"aparatuuriks" - 1 õppematerjal

REKURSIOON - Recursion

Ta elas XIII ja XIV sajandi vahetusel. Tema "Arvutamise raamatus" on kuulus küülikute paljunemise ülesanne: Mitu küülikupaari tekib ühest paarist aasta jooksul, kui (1) iga paar annab ühes kuus ühe paari järeltulijaid, (2) iga uus paar saab suguküpseks ühekuuseks saamisel, (3) küülikud ei sure kunagi? Selle ülesande lahendamine viib Fibonacci arvudeni. Fibonacci arvudel on teadusajaloos tähtis koht. Muu hulgas on nad aparatuuriks algoritmide keerukuse hindamisel. Fibonacci arvude iteratiivne algoritm Fibo(n) leidmiseks: IF (N = 0) OR (N = 1) THEN Fibo := N Eelmine := 0 Järgmine := 1 FOR I := 2 TO N Abi := Eelmine Eelmine := Järgmine Järgmine := Abi + Eelmine END FOR Fibo := Järgmine Rekursiivne definitsioon: ¦ n, kui n = 0 vôi n = 1 Fibo(n) = ¦ Fibo(n - 2) + Fibo(n - 1), kui n > 1 Protsess n = 5 puhul: F5 = F3 + F4 = F1 + F2 + F4 = ...