La recursión solo es divina si no causa un bucle infinito. Pero si no es así, es la forma más limpia de representar un problema, porque es una descripción pura, en lugar de una serie de pasos.
Intentemos crear una función que cuente el número de elementos en una lista: una función listLength . Nota: Uso el término “cola” para denotar la lista que obtenemos cuando tomamos alguna lista y eliminamos su primer elemento.
Ejemplo recursivo (Haskell-ish):
- ¿Cuál es el número más alto representable en la codificación de complemento a dos de 8 bits?
- ¿Qué libro debo usar para preguntas y soluciones para matemáticas discretas?
- ¿Por qué Matlab no le permite llamar a las funciones dos veces o indexarlas como en f (x) (y)?
- ¿Los ingenieros de software necesitan saber matemáticas?
- ¿Cómo se prueba algo (desde cero) que es NP-hard?
listLength list =
if listIsNotEmpty list entonces
1 + listLength (listTail list)
más
0 0
listIsNotEmpty list =
lista! = []
¿Cómo podría una explicación ser más simple que esto? Si no estamos tratando con una lista vacía, la longitud de la lista dada es igual a uno más la longitud de la lista dada con su primer elemento eliminado (la “cola” de la lista), de lo contrario es cero . ¿Alguien más ve hasta qué punto la oración anterior y el código anterior se parecen entre sí?
Ejemplo imperativo (Python):
def listLength (lista):
contador = 0
para el artículo en la lista:
contador = contador + 1
contador de devolución
Si alguien aquí ve el contador imperativo como más intuitivo, me sorprendería mucho. Veo lo contrario Esta función traducida a palabras sería algo así como: 1. escribir cero en una hoja de papel; 2. para cada elemento de la lista, uno a la vez, reemplace el número en el papel por sí mismo más uno ; 3. mira la hoja de papel para la respuesta .
Entonces, vemos que el código imperativo es más como ” una explicación de qué hacer , para calcular la longitud de una lista “, mientras que la definición recursiva en un grado superior se asemeja a ” una explicación de cuál es la longitud de una lista “.
Esta es la razón por la cual los compiladores para lenguajes de programación funcionales, como el GHC de Haskell, son sorprendentemente rápidos: porque reciben información sobre qué es algo en relación con otra cosa, ¿qué longitud tiene en relación con una lista ? – en lugar de simplemente cómo calcular algo cuando se me da algo más ( ¿cómo calculo una longitud cuando se me da una lista ? ). Cuanto más sepa un compilador sobre lo que realmente está tratando de hacer, más podrá optimizar el código de máquina resultante, lo que realmente no nos importa siempre que sea correcto, rápido y compacto.
Por diversión, aquí está la implementación recursiva en Python:
def listLength (lista):
if list! = []:
return 1 + listLength (listTail (list))
más:
volver 0
def listTail (lista):
lista de retorno [1:]
Y lo mismo para Haskell:
listLength list =
si list / = [] entonces
1 + listLength (lista de cola)
más
0 0
