2012-01-20 14 views
26

Sono un neofita del clojure che voleva vedere di cosa si tratta. Immaginare il modo migliore per farsi un'idea è scrivere un codice semplice, ho pensato di iniziare con una funzione di Fibonacci.una funzione ricorsiva di Fibonacci in Clojure

Il mio primo sforzo è stato:

(defn fib [x, n] 
    (if (< (count x) n) 
    (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n) 
    x)) 

di utilizzare questo ho bisogno di seminare x con [0 1] quando si chiama la funzione. La mia domanda è, senza avvolgerla in una funzione separata, è possibile scrivere una singola funzione che richiede solo il numero di elementi da restituire?

Facendo qualche lettura intorno a me portato ad alcuni modi migliori per raggiungere lo stesso funcionality:

(defn fib2 [n] 
    (loop [ x [0 1]] 
    (if (< (count x) n) 
     (recur (conj x (+ (last x) (nth x (- (count x) 2))))) 
     x))) 

e

(defn fib3 [n] 
    (take n 
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))) 

In ogni caso, più per il bene del l'esercizio di ogni altra cosa, qualcuno può aiutarmi con una versione migliore di una funzione di Fibonacci puramente ricorsiva? O forse condividere una funzione migliore/diversa?

+5

fib3 è il più Clojure'ish di questi –

risposta

16

di rispondervi prima domanda:

(defn fib 
    ([n] 
    (fib [0 1] n)) 
    ([x, n] 
    (if (< (count x) n) 
     (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n) 
     x))) 

Questo tipo di definizione di funzione viene chiamata definizione di funzione multi-arity. Potete saperne di più qui: http://clojure.org/functional_programming

Come per una migliore funzione di Fib, penso che la vostra funzione di fib3 sia abbastanza impressionante e mostri molti concetti di programmazione funzionale.

+0

Se ho capito correttamente, sembra un nome di fantasia per una funzione sovraccaricata. Funziona alla grande, grazie. – richc

+11

"Multi-arity" è più specifico di "overloaded". "Multi-arity" significa "distinto dal numero di argomenti", mentre "sovraccarico" significa in genere "distinto dal numero * o dal tipo * degli argomenti." Quindi multi-arity è un sottoinsieme di metodi di overloading. –

+2

Come possiamo scrivere una versione immutabile senza ricorsione? – Dinesh

5

Questo è veloce e fresco:

(def fib (lazy-cat [0 1] (map + fib (rest fib)))) 

da: http://squirrel.pl/blog/2010/07/26/corecursion-in-clojure/

+0

Grazie Nickik, difficile da capire ma molto interessante. – richc

+0

(def fib (lazy-cat [0 1] (map + fib (resto fib)))) e (prendi 5 fib) restituirà i primi 5 termini. Ancora una volta sto lottando per scrivere questo come una funzione: (defn fib ([n] (take n fib)) ([] (lazy-cat [0 1] (map + fib (resto fib))))) doesn ' lavoro. – richc

+0

Se la difficoltà di comprendere quelle 5 linee di codice (sto parlando dell'algoritmo dell'albero) non genera nessuna bandiera rossa su questo linguaggio per te .... inoltre, puoi contare il numero di allocazioni in quel codice? È dannatamente alto. Solo perché il tempo di esecuzione scala in modo lineare, non significa che sia veloce. –

1

Una buona definizione ricorsiva è:

(def fib 
    (memoize 
    (fn [x] 
     (if (< x 2) 1 
     (+ (fib (dec (dec x))) (fib (dec x))))))) 

Ciò restituirà un termine specifico. Espansione questo per tornare termini primi n è banale:

(take n (map fib (iterate inc 0))) 
3

È possibile utilizzare l'operatore mughetto per ripulire 3 # un po '(a seconda di chi si chiede, alcune persone amano questo stile, altri lo odiano, io sono solo sottolineando che è un'opzione):

(defn fib [n] 
    (->> [0 1] 
    (iterate (fn [[a b]] [b (+ a b)])) 
    (map first) 
    (take n))) 

detto questo, probabilmente sarei estrarre il (take n) e solo la funzione fib una successione infinita pigro.

(def fib 
    (->> [0 1] 
    (iterate (fn [[a b]] [b (+ a b)])) 
    (map first))) 

;;usage 
(take 10 fib) 
;;output (0 1 1 2 3 5 8 13 21 34) 
(nth fib 9) 
;; output 34 
6

In Clojure In realtà è consigliabile evitare la ricorsione e di utilizzare invece le loop e recur forme speciali. Ciò trasforma quello che sembra un processo ricorsivo in uno iterativo, evitando lo stack overflow e migliorando le prestazioni.

Ecco un esempio di come si sarebbe implementare una sequenza di Fibonacci con questa tecnica:

(defn fib [n] 
    (loop [fib-nums [0 1]] 
    (if (>= (count fib-nums) n) 
     (subvec fib-nums 0 n) 
     (let [[n1 n2] (reverse fib-nums)] 
     (recur (conj fib-nums (+ n1 n2))))))) 

Il loop costrutto prende una serie di attacchi, che forniscono valori iniziali, e una o più forme del corpo. In una di queste forme del corpo, una chiamata a recur farà in modo che il ciclo venga chiamato in modo ricorsivo con gli argomenti forniti.

0

Per i ritardatari. risposta accettato è un'espressione un po 'complicato di questo:

(defn fib 
    ([n] 
    (fib [0 1] n)) 
    ([x, n] 
    (if (< (count x) n) 
     (recur (conj x (apply + (take-last 2 x))) n) 
     x))) 
0

Per quel che vale, ecco questi anni da qui, ecco la mia soluzione a 4Closure Problem #26: Fibonacci Sequence

(fn [x] 
    (loop [i '(1 1)] 
     (if (= x (count i)) 
      (reverse i) 
      (recur 
       (conj i (apply + (take 2 i))))))) 

non, con qualsiasi mezzo, che questo è l'approccio ottimale o più idiomatico. L'intera ragione per cui sto esaminando gli esercizi di 4Clojure ... e rimuginare sugli esempi di codice da Rosetta Code è imparare .

Incidentalmente sono ben consapevole del fatto che la sequenza di Fibonacci include formalmente 0 ... che questo esempio dovrebbe loop [i '(1 0)] ... ma che non corrisponderebbe alle loro specifiche. né superare i loro test unitari nonostante il modo in cui hanno etichettato questo esercizio. È scritto come una funzione ricorsiva anonima per conformarsi ai requisiti degli esercizi 4Clojure ... dove devi "riempire lo spazio vuoto" all'interno di una determinata espressione. (Sto scoprendo che l'intera nozione di ricorsione anonima è un po 'una bontà mentale, ho capito che il modulo speciale (loop ... (recur ... è limitato a ... ma è comunque una sintassi strana per me).

Prenderò il commento di @ [Arthur Ulfeldt], riguardante il fib3 nel post originale, anch'esso preso in considerazione. Ho usato solo Clojure iterate una volta, finora.

+0

Provare questa altra forma di riferimento utente: @ [Arthur Ulfeldt] –

+0

FWIW: (fn [n] (prendi n (mappa prima (iterate (fn [[ab]] [b (+ ab)]) '(1 1))))) ... funziona anche per la forma 4Clojure di questo problema. –

0

Ecco la funzione ricorsiva più breve mi è venuta in mente per il calcolo del numero di Fibonacci esimo:

(defn fib-nth [n] (if (< n 2) 
       n 
       (+ (fib-nth (- n 1)) (fib-nth (- n 2))))) 

Tuttavia, la soluzione con loop/ricorsione dovrebbe essere più veloce per tutti, ma i primi valori di ' Dal momento che Clojure ottimizza la coda su loop/ricorrenza.

Problemi correlati