Clojure: Simple factorielle provoque un débordement de pile

Ce que je fais mal? Simple récursivité quelques milliers d'appels profonde jette un StackOverflowError.

Si la limite de Clojure récurrences est si bas, comment puis-je compter sur elle?

(defn fact[x]
  (if (<= x 1) 1 (* x  (fact (- x 1))  )))

user=> (fact 2)
2

user=> (fact 4)
24

user=> (fact 4000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

InformationsquelleAutor GabiMe | 2009-11-02

40

La taille de la pile, je comprends, dépend de la JVM vous utilisez ainsi que la plate-forme. Si vous utilisez la JVM de Sun, vous pouvez utiliser le -Xss et -XThreadStackSize paramètres pour définir la taille de la pile.

La meilleure façon de faire de la récursivité en Clojure est bien pour utiliser loop/recur:
```
(defn fact [x]
    (loop [n x f 1]
        (if (= n 1)
            f
            (recur (dec n) (* f n)))))
```
Clojure va faire la queue-appel d'optimisation pour cela; ceci assure que vous ne serez jamais à court dans StackOverflowErrors.

Et en raison défn implique un boucle de liaison, vous pouvez omettre le loop expression, et d'utiliser ses arguments comme argument de la fonction. Et pour en faire un 1 argument de la fonction, l'utilisation le multiary caractéristiques des fonctions:
```
(defn fact
  ([n] (fact n 1))
  ([n f]
  (if (<= n 1)
    f
    (recur (dec n) (* f n)))))
```
Edit: Pour l'histoire, voici un Clojure une fonction qui retourne un paresseux ordre de tous les factorielles:
```
(defn factorials []
    (letfn [(factorial-seq [n fact]
                           (lazy-seq
                             (cons fact (factorial-seq (inc n) (* (inc n) fact)))))]
      (factorial-seq 1 1)))

(take 5 (factorials)) ; will return (1 2 6 24 120)
```
- Voici une façon plus élégante de définir une séquence infinie de factorielles: (def facts (lazy-cat [1] (map * facts (iterate inc 2)))). Puis (take 5 facts) produit (1 2 6 24 120).
- une autre façon de dire la même chose (depuis Clojure 1.3): (def facts (reductions * (iterate inc 1)))
- that ensures that you’ll never run into StackOverflowErrors jamais? vraiment?
InformationsquelleAutor Siddhartha Reddy
75

Voici une autre façon:
```
(defn factorial [n]
  (reduce * (range 1 (inc n))))
```
Ce ne sera pas le coup de la pile car range retourne un paresseux seq, et reduce des promenades à travers la seq sans se tenant sur la tête.

reduce rend l'utilisation de fragments de seqs si l'on peut, si cela peut réellement faire mieux que l'aide recur vous-même. À l'aide de Siddhartha Reddy recurversion et ce reduceversion:
```
user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil
```
Une légère différence. J'aime bien laisser mon recuranneau de map et reduce et les amis, qui sont à la fois plus lisible et explicite, et l'utilisation recur à l'interne un peu plus élégamment que je suis susceptible de le faire à la main. Il ya des moments où vous avez besoin de recur manuellement, mais pas beaucoup dans mon expérience.
- Je suis complètement d'accord. Je pense que c'est une meilleure approche que l'utilisation de la boucle/se reproduire directement, même si la différence de vitesse n'existent pas. Je serais personnellement utiliser cette approche. J'ai donné la boucle/reproduire la version principalement à démontrer la récursivité en Clojure.
- J'aime qu'il était bien. BTW, pourrait aussi être: (defn factorial [n] (apply * (range 1 (inc n))))
- En Clojure 1.3.0 j'ai fait ce travail pour le calcul de n > 20 par écrit (defn factorial [n] (reduce *' (range 1 (inc n)))) Note la " marque à côté de l' *.
- Mais c'est votre version de la tête de retenue? Imaginez que votre gamme de mettre à l'intérieur les arguments d'une autre fonction.
InformationsquelleAutor Brian Carper
16

Clojure a plusieurs façons de le contournement de la récursivité
- explicite queue appels avec réapparaître. (ils doivent être vraiment la queue appelle donc cela ne marchera pas)
- Paresseux séquences comme mentionné ci-dessus.
- trampoline lorsque vous retournez une fonction qui fait le travail au lieu de le faire directement, et ensuite appeler un trampoline fonction qui appelle à plusieurs reprises sa suite jusqu'à ce qu'il turnes en une valeur réelle au lieu d'une fonction.
- memoizing l'affaire de fait, cela peut vraiment raccourcir la pile de profondeur, mais il n'est généralement pas le cas.
  
  ps: je n'ai pas de repl sur moi, donc quelqu'un de bien vouloir tester-fixer le trapoline fait fonction?
InformationsquelleAutor Arthur Ulfeldt
3

Que je m'apprêtais à poster la suite, je vois que c'est presque le même que le Schéma de l'exemple posté par JasonTrue... de toute façon, voici une implémentation en Clojure:
```
user=> (defn fact[x]
        ((fn [n so_far]
          (if (<= n 1)
              so_far
              (recur (dec n) (* so_far n)))) x 1))
#'user/fact
user=> (fact 0)
1
user=> (fact 1)
1
user=> (fact 2)
2
user=> (fact 3)
6
user=> (fact 4)
24
user=> (fact 5)
120
```
etc.
- Je n'arrive pas à le traduire en Clojure encore, donc j'apprécie que vous le pouvez, même si personne d'autre ne l'aime mon point de que la continuation passing style est la vraie solution 🙂
- Merci. Je ne suis pas un Régime de programmeur, donc je ne peux parler que pour ce Clojure code, ce qui me semblait être essentiellement ce que votre exemple est en train de faire. En cela, je ne suis pas le passage d'un maintien de la fonction, mais simplement (dans un intérieur "travailleur" fonction) le supplément de l'accumulateur de valeur qui est mise à jour à chaque appel. Ma compréhension de la continuation passing style, vient de ce que j'ai lu, c'est que toutes les fonctions supplémentaires fonction de prolongement de ce côté, et que les pc nécessite queue appel d'optimisation afin d'éviter la croissance de la pile, plutôt que d'être un travail autour de l'absence de queue appel d'optimisation.
InformationsquelleAutor Anon
1

Comme l0st3d suggéré, pensez à utiliser se reproduire ou paresseux-seq.

Aussi, essayez de faire de votre séquence paresseux, en le construisant à l'aide de l'séquence de formes comme une opposition à le faire directement.

Voici un exemple d'utilisation de l'intégré dans la séquence de formes pour créer un paresseux suite de Fibonacci (à partir de la Programmation Clojure livre):
```
(defn fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

=> (take 5 (fibo))
(0 1 1 2 3)
```
InformationsquelleAutor cdmckay
1

La pile de la profondeur est un petit ennui (configurable encore), mais même dans une langue avec de la queue de la récursivité comme Régime ou F# vous éventuellement d'exécuter hors de l'espace de pile avec votre code.

Aussi loin que je peux dire, votre code est peu probable que la queue de la récursivité optimisés, même dans un environnement qui prend en charge la récursion sur la queue de manière transparente. Vous voulez regarder une continuation passing style pour minimiser la profondeur de la pile.

Voici un exemple canonique dans le Schéma de Wikipédia, qui pourrait être traduit à Clojure, F# ou un autre langage fonctionnel sans trop de difficulté:
```
(define factorial
  (lambda (n)
      (let fact ([i n] [acc 1])
        (if (zero? i)
            acc
            (fact (- i 1) (* acc i))))))
```
InformationsquelleAutor JasonTrue
0

Un autre, récursive simple mise en œuvre simple pourrait être ceci:
```
(defn fac [x]
    "Returns the factorial of x"
    (if-not (zero? x) (* x (fac (- x 1))) 1))
```
InformationsquelleAutor Abhishek Bhattacharjee
0

À ajouter à Siddhartha Reddy réponse, vous pouvez également emprunter la fonction Factorielle forme La Structure Et l'Interprétation des Programmes d'Ordinateur, avec quelques Clojure-réglages spécifiques. Cela m'a donné une assez bonne performance, même pour de très grandes factorielle des calculs.
```
(defn fac [n]
  ((fn [product counter max-count]
     (if (> counter max-count)
         product
         (recur (apply *' [counter product])
                (inc counter)
                max-count)))
   1 1 n))
```
InformationsquelleAutor Carlos D
-8

Factorielle des nombres sont de par leur nature, très grand. Je ne suis pas sûr de savoir comment Clojure traite avec cette (mais je vois qu'il fonctionne avec java), mais toute application qui n'utilise pas les chiffres de dépassement de très vite.

Edit: C'est sans prendre en considération le fait que vous êtes en utilisant la récursivité pour ce, qui est également susceptible d'utiliser des ressources.

Modifier x2: Si la mise en œuvre est à l'aide de grands nombres, qui, autant que je sache, sont généralement des tableaux, couplé avec la récursivité (un grand nombre de copie par l'entrée de la fonction, toujours sauvegardés sur la pile en raison de la fonction d'appels) pourrait expliquer un débordement de pile. Essayez de le faire dans une boucle for pour voir si c'est bien le problème.
- Alors je m'attends à voir quelque chose comme "IntegerOverflow", pas "StackOverflow"
- La raison, c'est une StackOverflow est parce que votre code est essentiellement faire des appels de méthodes dans les appels de méthode jusqu'à épuisement de la pile d'images.
- Aussi, pour l'anecdote, Clojure a une précision arbitraire numérique types. Cela signifie que vous ne jamais obtenir une IntegerOverflow dans le plus pur Clojure code.
- Il n'y a pas de raison que les "grands entiers" sont stockées sur la pile. Peut-être une référence est stockée dans la pile, mais je doute que la totalité de la valeur.
- +1 Downvoted et elle avait raison. @cdmckay ;; Clojure 1.5.0-beta2 => (fact 400) ArithmeticException integer overflow clojure.lang.Numbers.throwIntOverflow (Numbers.java:1388)
- Si nous utilisons *' au lieu de * il ne jette pas de débordement, mais de manière dynamique utilise nécessaire type.
InformationsquelleAutor laura

Vous devez vous connecter pour publier un commentaire.