Recursión (ciencias de computación)

Los lenguajes imperativos definen las estructuras de loops como while y for que son usadas para realizar tareas repetitivas.En esa situación diremos que estamos ante un caso base de la recursividad.Las claves para construir un subprograma recurrente son: Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.Resulta evidente que no todas las evaluaciones de funciones se prestan a un acercamiento recursivo.A modo de ilustración: Si se encuentra una palabra desconocida en un libro, el lector puede anotar la página actual en un papel y ponerlo en una pila (hasta entonces vacía).El lector retorna entonces a la última página y continua la lectura desde ahí, y así hasta que se retira la última nota de la pila retornando entonces al libro original.La distinción se hace según de donde provengan los datos con los que trabaja la subrutina.Se basa únicamente en la recursión para ejecutar todo tipo de loops.Dado que scheme es recursivo de cola, se puede definir una subrutina recursiva que implementa la subrutina factorial como un proceso iterativo, es decir, usa espacio constante pero tiempo lineal.Definición de la función: Relación recurrente para Fibonacci: bn = bn-1 + bn-2 b1 = 1, b0 = 0 Este algoritmo de Fibonacci es especialmente malo pues cada vez que se ejecuta la función, realizará dos llamadas a la función a sí misma, cada una de las cuales hará a la vez dos llamadas más y así sucesivamente hasta que terminen en 0 o en 1.Definición de la función: Relación recursiva del máximo común denominador, dondeEn el ejemplo siguiente se muestra el mismo algoritmo usando explícitamente iteración.No acumula una cadena de operaciones deferred, sino que su estado es, más bien, mantenido completamente en las variables x e y.El tamaño del vector se ajusta normalmente cambiando el índice inicial y final.El algoritmo muestra un orden logaritmo de crecimiento porque divide esencialmente el dominio del problema en dos tras cada pasada."[12]​ Los ejemplos en esta sección ilustran lo que se conoce como "recursión estructural".[13]​ A continuación se describe una definición simple del nodo de una lista enlazada.La subrutina printList definida a continuación recorre la lista hacia abajo hasta que ésta se vacía (NULL), para cada nodo imprime el dato (un número entero).Para un ejemplo similar, véase la función de Fibonacci y la explicación siguiente.En el ejemplo "factorial" la implementación iterativa es probablemente más rápida en la práctica que la recursiva.Hay otros tipos de problemas cuyas soluciones son inherentemente recursivas, porque estar al tanto del estado anterior.Con un compilador que automáticamente optimiza llamadas recursivas de cola, una función recursiva de cola, como por ejemplo gcd, se ejecutará usando un espacio constante.De esta forma es posible crear largas cadenas y ramificaciones, véase Parser descendente recursivo.