haskell - programacion - ¿La recursividad de cola necesariamente necesita un acumulador?

recursividad directa e indirecta

Question

Por ejemplo, dado que la siguiente función no tiene un acumulador, ¿sigue siendo cola recursiva?

belong:: (Ord a) => a -> [a] -> Bool
belong a [] = False
belong a (h:t)
| a == h = True
| otherwise = belong a t

Todos los cálculos en la función se procesan antes de la llamada recursiva, ¿es una condición suficiente para ser considerado recursivo de cola?

Answer 1

La recurrencia de la cola no necesita necesariamente un acumulador. Los acumuladores se utilizan en recursividad de cola como una forma de comunicar un resultado parcial hacia abajo a través de la cadena recursiva de llamadas sin requerir espacio adicional para ser utilizado en cada nivel de la recursión. Por ejemplo, la función factorial recursiva de cola canónica necesita un acumulador para propagar el producto parcial acumulado hasta ahora. Sin embargo, si no necesita comunicar ninguna información de una llamada recursiva a su subllamada, entonces el acumulador no es necesario.

La función que ha proporcionado es recursiva de cola, pero no necesita ni utiliza un acumulador. Al buscar un elemento en una lista, la recursión no necesita recordar que todos los elementos que ha examinado hasta ahora no son iguales al elemento particular que se está buscando. Solo necesita saber qué elemento buscar y qué lista buscar.

¡Espero que esto ayude!

Answer 2

La recurrencia de la cola no necesita necesariamente un acumulador. Sin embargo, a menudo se usa un acumulador. Sugerencia, busque en el artículo de la wikipedia "acumulador".