recursion - Clojure: sólo puede recurrir desde la posición de la cola

Question

Estoy tratando de revertir recursivamente una lista, pero estoy obteniendo. Can only recur from tail position al ejecutar. ¿Qué significa esto exactamente y cómo puede mejorarse mi código para que funcione?

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) ''(coll)
      (conj (first coll) (recur (rest coll)))
      )))

EDITAR

Salida para la solución de Oscar. ¿Funciona para listas pero no para vectores?

user=> (= (recursive-reverse [1 2 3 4 5]) (recursive-reverse ''(1 2 3 4 5)))
false
user=> (= ''(1 2 3 4 5) [1 2 3 4 5])
true
user=> (recursive-reverse [1 2 3 4 5])
[1 2 3 4 5]
user=> (recursive-reverse ''(1 2 3 4 5))
(5 4 3 2 1)

Answer 1

El error Can only recur from tail position significa que no está llamando a recur como la última expresión en la parte recursiva de la función; de hecho, en su conj código está la última expresión.

Algunas mejoras para hacer que su código funcione:

• Pregunte si la colección está vacía como el caso base, en lugar de comparar si su longitud es menor que dos
• conj recibe una colección para su primer parámetro, no un elemento
• Es una mejor idea usar cons lugar de conj (lo que agrega nuevos elementos en diferentes lugares según el tipo concreto de la colección, según la documentation ). De esta manera, la colección devuelta se invertirá si la colección de entrada es una lista o un vector (aunque el tipo de la colección devuelta siempre será clojure.lang.Cons , sin importar el tipo de la colección de entrada)
• Tenga en cuenta que ''(coll) es una lista con un solo elemento (el símbolo coll ) y no la colección real
• Para revertir correctamente una lista necesita iterar sobre la lista de entrada y adjuntar cada elemento al principio de una lista de salida; usar un parametro acumulador para esto
• Para aprovechar la recursión de cola, la llamada se recur en la posición de cola de la función; de esta manera, cada invocación recursiva ocupa una cantidad constante de espacio y la pila no crecerá ilimitada

Creo que esto es lo que buscabas:

(defn recursive-reverse [coll]
  (loop [coll coll
         acc  (empty coll)]
        (if (empty? coll)
            acc
            (recur (rest coll) (cons (first coll) acc)))))

Answer 2

La forma más fácil de hacer que su código funcione es usar el nombre de la función en lugar de recur :

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) ''(coll)
      (conj (first coll) (recursive-reverse (rest coll)))
      )))

Por supuesto, hará que la pila de llamadas sea enorme y que se produzcan errores en las entradas suficientemente grandes.

Aquí hay otra forma de escribir una versión de recursive-reversa amigable con la cola:

(defn recursive-reverse [s]
  (letfn [
    (my-reverse [s c]
      (if (empty? s)
        c
        (recur (rest s) (conj c (first s)))))]
    (my-reverse s ''())))

Extrae elementos del encabezado de la lista de entrada y los agrega al encabezado de la lista de acumuladores.

''Posición de la cola'' solo significa que la recur es la última cosa que realiza la función antes de regresar. Esto difiere de su solución de ''recursión natural'' en la cual todavía se está trabajando por la función entre llamarse y regresar.

Answer 3

Solo puedes llamar recurrir desde la posición de cola en Clojure. Es parte del diseño del lenguaje y es una restricción relacionada con la JVM.

Puede llamar al nombre de su función (usando la recursividad) sin usar la repetición, y dependiendo de cómo estructure su programa, ya sea que use secuencias perezosas o no, es posible que no tenga la explosión de la pila. Pero es mejor usar Recur, y el uso de bucle con repetición te permite algunos enlaces locales.

Aquí hay un ejemplo de 4Clojure.com donde la recursión se usa sin recurrir.

(fn flt [coll]
  (let [l (first coll) r (next coll)]
    (concat 
      (if (sequential? l)
        (flt l)
        [l])
      (when (sequential? r)
        (flt r)))))