Ricorsione di coda clojure con fattori primi

Question

Sto cercando di insegnarmi clojure e sto usando i principi di Prime Factors Kata e TDD per farlo.

Attraverso una serie di test Midje come questo:

(fact (primefactors 1) => (list)) 

(fact (primefactors 2) => (list 2)) 

(fact (primefactors 3) => (list 3)) 

(fact (primefactors 4) => (list 2 2)) 

sono stato in grado di creare la seguente funzione:

(defn primefactors 
    ([n] (primefactors n 2)) 
    ([n candidate] 
     (cond (<= n 1) (list) 
       (= 0 (rem n candidate)) (conj (primefactors (/ n candidate)) candidate) 
       :else (primefactors n (inc candidate)) 
     ) 
    ) 
) 

Questa grande opera fino a quando mi passi il seguente test caso limite a questo:

(fact (primefactors 1000001) => (list 101 9901)) 

Finisco con un errore di overflow dello stack. So che ho bisogno di trasformare questo in un vero e proprio ricorsivo, ma tutti gli esempi che vedo sembrano troppo semplicistici e puntano solo a un contatore o una variabile numerica come focus. Come faccio a renderlo ricorsivo?

Grazie!

Answer 1

Ecco una coda ricorsiva attuazione della procedura primefactors, dovrebbe funzionare senza lanciare un errore di stack overflow:

(defn primefactors 
    ([n] 
    (primefactors n 2 '())) 
    ([n candidate acc] 
    (cond (<= n 1) (reverse acc) 
      (zero? (rem n candidate)) (recur (/ n candidate) candidate (cons candidate acc)) 
      :else (recur n (inc candidate) acc)))) 

Il trucco sta utilizzando un parametro accumulatore per memorizzare il risultato. Nota che la chiamata reverse alla fine della ricorsione è facoltativa, a patto che non ti interessi se i fattori vengono elencati nell'ordine inverso in cui sono stati trovati.

Answer 2

La seconda chiamata ricorsiva è già nelle posizioni di coda, è possibile semplicemente sostituirla con recur.

(primefactors n (inc candidate)) 

diventa

(recur n (inc candidate)) 

Qualsiasi sovraccarico funzione apre un loop blocco implicita, quindi non c'è bisogno di inserire manualmente. Questo dovrebbe già migliorare la situazione dello stack, in quanto questo ramo verrà preso più comunemente.

La prima ricorsività

(primefactors (/ n candidate)) 

non è nella posizione di coda come suo risultato viene passato a conj. Per metterlo in posizione di coda, è necessario raccogliere i fattori primi in un argomento aggiuntivo di accumulatore sul quale si ottiene il valore di ricorsione attuale e quindi passare a recur per ogni chiamata. Dovrai modificare la tua condizione di terminazione per restituire l'accumulatore.

Answer 3

Il modo tipico è includere un accumulatore come uno degli argomenti della funzione. Aggiungere una versione 3-arity alla definizione di funzione:

(defn primefactors 
    ([n] (primefactors n 2 '())) 
    ([n candidate acc] 
    ...) 

quindi modificare il modulo (conj ...) di chiamare (recur ...) e superare (conj acc candidate) come terzo argomento. Assicurati di inoltrare gli argomenti tre a recur, ad esempio (recur (/ n candidate) 2 (conj acc candidate)), in modo da chiamare la versione 3-arity di primefactors.

E la custodia (<= n 1) deve restituire acc anziché una lista vuota.

Posso entrare più nel dettaglio se non riesci a capire da solo la soluzione, ma ho pensato che dovrei darti la possibilità di provare prima a risolverlo.

Answer 4

Una coda ricorsiva, privo di accumulatore, soluzione minimale sequenza: chiamate

(defn prime-factors [n] 
    (letfn [(step [n div] 
      (when (< 1 n) 
       (let [q (quot n div)] 
       (cond 
        (< q div)   (cons n nil) 
        (zero? (rem n div)) (cons div (lazy-step q div)) 
        :else    (recur n (inc div)))))) 
      (lazy-step [n div] 
      (lazy-seq 
       (step n div)))] 
    (lazy-step n 2))) 

ricorsivi incorporati in lazy-seq non vengono valutate prima iterazione dalla sequenza, eliminando i rischi di stack troppopieno senza ricorrere ad un accumulatore .

Answer 5

Questa funzione in realtà non dovrebbe essere ricorsiva in coda: dovrebbe invece creare una sequenza pigra. Dopo tutto, non sarebbe bello sapere che 4611686018427387902 non è un numero primo (è divisibile per due), senza dover crimpare i numeri e scoprire che il suo altro fattore principale è 2305843009213693951?

(defn prime-factors 
    ([n] (prime-factors n 2)) 
    ([n candidate] 
    (cond (<= n 1)() 
      (zero? (rem n candidate)) (cons candidate (lazy-seq (prime-factors (/ n candidate) 
                       candidate))) 
      :else (recur n (inc candidate))))) 

Quanto sopra è una traduzione abbastanza priva di fantasia dell'algoritmo inviato; Ovviamente esistono algoritmi migliori, ma questo ti dà la correttezza e la pigrizia e corregge l'overflow dello stack.