Tietorakenteet ja algoritmit syksy 2020

Rekursiivinen algoritmi

Fibonaccin luvut ovat 0, 1, 1, 2, 3, 5, 8, 13, jne. Ideana on, että kahden ensimmäisen luvun jälkeen jokainen luku on kahden edellisen luvun summa.

Seuraava rekursiivinen funktio laskee Fibonaccin lukuja:

function fibo(n)
    if n <= 1
        return n
    else
        return fibo(n-1) + fibo(n-2)

Esimerkiksi kun n = 10, funktio palauttaa arvon 55. Tässä tapauksessa funktiota kutsutaan laskennan aikana yhteensä 177 kertaa.

Toteuta algoritmi pseudokoodin perusteella Javalla tai Pythonilla ja vastaa sitten seuraaviin kysymyksiin:

Kun n = 20, funktio palauttaa arvon , sitä kutsutaan laskennan aikana yhteensä kertaa ja aikaa kuluu sekuntia.

Kun n = 30, funktio palauttaa arvon , sitä kutsutaan laskennan aikana yhteensä kertaa ja aikaa kuluu sekuntia.

Kun n = 40, funktio palauttaa arvon , sitä kutsutaan laskennan aikana yhteensä kertaa ja aikaa kuluu sekuntia.

Kirjoita tähän toteuttamasi algoritmin koodi:

The deadline for this task has passed but you can still check your answers