Clojure - zliczanie ilości wywołań fib

0

Witam

Mam problem ze zrobieniem funkcji która będzie zliczać ilość wywołań fib. Główny problem to zapis w Clojure :/

(defn Fib [h]
(if (< h 2)
h
(+ (Fib (dec h)) (Fib (dec (dec h))))))

trzeba by dodać jakąś zmienną która zliczała te wywołania
do Fib nie mogę dodać kolejnego argumentu
mogę zrobić (let [ilosc 0] ...)
tylko jak dodać inkrementacje ilosc (inc ilosc) przy wywołaniu ciągu (czyli tu/ po (+ (Fib (- n 1)) (Fib (- n 2)))) tak aby nie przeszkadzało to w sumowaniu

ma ktoś pomysł jak to zrobić ?

EDIT:
drugie pytanie: z tego co rozpisałem na kartce to dla (Fib 5) mamy 7 wywołań rekurencyjnych
coś tam ulepiłem w clojure i dla 5 wychodzi mi 11 wywołań

teraz kto się myli clojure i ja (ja w sensie że źle napisałem) czy ja bo nie umiem liczyć :P ?

0

Zależy jak liczyć te wywołania rekurencyjne :>.

W Haskellu bym to zrobił tak:

fib :: Num a => Int -> Writer (Sum Int) a
fib 0 = writer (0, Sum 1)
fib 1 = writer (1, Sum 1)
fib n = do
    a <- fib (n - 1)
    b <- fib (n - 2)
    tell (Sum 1)
    return (a + b)

Dla takiego kodu, i to bym uznał za prawdę. ilość wywołań rekurencyjnych wyjdzie 15:

Licząc tylko liście,drzewa rekurencji: 8.

fib 0 = writer (1, Sum 1)
fib 1 = writer (1, Sum 1)
fib n = do
    a <- fib (n - 1)
    b <- fib (n - 2)
    return (a + b)

Pomijając liście: 7.

fib 0 = return 0
fib 1 = return 1
fib n = do
    a <- fib (n - 1)
    b <- fib (n - 2)
    tell (Sum 1)
    return (a + b)

Co do Clojure - nie możesz dodać kolejnego parametru, ale możesz zmienić znaczenie zwracanego paramtru? Jeśli tak, zwracaj wektor [wartość, suma wywołań rekurencyjnych], rozkładaj go za pomocą let i odpowiednio łącz.

0

w moim przypadku najlepszy moim zdaniem sposób (jaki wymyśliłem) to na początek definiowanie stałej ilosc
następnie w funkcji Fib definiowanie stałej ilosc o wartości inkrementowanej ilosc - czyli na koniec otrzymam stała która powinna mieć wartość ilości wywołań Fib
(wydaje mi się że poprawne jest określenie "ilosc" jako stała, zmienna trochę by inaczej działała)

w przypadku let jest więcej zabawy, bo chyba inny wynik mi wychodził

Wyniki które otrzymuje:
user=> (wynik 5)
"Fib (5) to 5 ilość wykonań rekurencyjnych to 15"
user=> (wynik 6)
"Fib (6) to 8 ilość wykonań rekurencyjnych to 25"
user=> (wynik 7)
"Fib (7) to 13 ilość wykonań rekurencyjnych to 41"

0

Wyniki które otrzymuje:
user=> (wynik 5)
"Fib (5) to 5 ilość wykonań rekurencyjnych to 15"
user=> (wynik 6)
"Fib (6) to 8 ilość wykonań rekurencyjnych to 25"
user=> (wynik 7)
"Fib (7) to 13 ilość wykonań rekurencyjnych to 41"

Tak jak pisałem, to samo mi wyszło i tak powinno być (przynajmniej dla Fib 5, reszty nie sprawdzałem).

Widzę że już sobie chyba poradziłeś, ale napiszę jeszcze raz to co poprzednio tylko tym razem z kodem, odkurzyłem swój interpreter clojure trochę :>

(defn Fib [h]
    (if (< h 2)
        [h 1]
        (let [f0 (Fib (dec h))
              f1 (Fib (dec (dec h)))]
            [(+ (first f0) (first f1)) (+ (second f0) (second f1) 1)])))

(pierwszy zwrócony element to wartość, drugi to ilość wywołań rekurencyjnych. Przyjmowany parametr nie zmieniony)

user=> (Fib 1)
[1 1]
user=> (Fib 2)
[1 3]
user=> (Fib 3)
[2 5]
user=> (Fib 4)
[3 9]
user=> (Fib 5)
[5 15]

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0