En informática , la recursión es un método para resolver un problema computacional en el que la solución depende de soluciones a instancias más pequeñas del mismo problema. [1] [2] La recursión resuelve este tipo de problemas recursivos mediante el uso de funciones que se llaman a sí mismas desde su propio código. El enfoque se puede aplicar a muchos tipos de problemas y la recursión es una de las ideas centrales de la informática. [3]
El poder de la recursión reside evidentemente en la posibilidad de definir un conjunto infinito de objetos mediante un enunciado finito. De la misma manera, un número infinito de cálculos puede describirse mediante un programa recursivo finito, incluso si este programa no contiene repeticiones explícitas.
— Niklaus Wirth , Algoritmos + Estructuras de datos = Programas , 1976 [4]
La mayoría de los lenguajes de programación informática admiten la recursión al permitir que una función se llame a sí misma desde su propio código. Algunos lenguajes de programación funcional (por ejemplo, Clojure ) [5] no definen ninguna construcción de bucle, sino que se basan únicamente en la recursión para llamar repetidamente al código. Está demostrado en la teoría de la computabilidad que estos lenguajes exclusivamente recursivos son Turing completos ; esto significa que son tan potentes (se pueden utilizar para resolver los mismos problemas) como los lenguajes imperativos basados en estructuras de control como whiley for.
Llamar repetidamente a una función desde dentro de sí misma puede hacer que la pila de llamadas tenga un tamaño igual a la suma de los tamaños de entrada de todas las llamadas involucradas. De ello se deduce que, para los problemas que se pueden resolver fácilmente mediante iteración, la recursión es generalmente menos eficiente y, para ciertos problemas, las técnicas de optimización algorítmica o de compilación, como la optimización de llamadas de cola , pueden mejorar el rendimiento computacional en comparación con una implementación recursiva ingenua.
Una táctica común en el diseño de algoritmos es dividir un problema en subproblemas del mismo tipo que el original, resolver esos subproblemas y combinar los resultados. Esto se conoce a menudo como el método de dividir y vencer ; cuando se combina con una tabla de búsqueda que almacena los resultados de los subproblemas resueltos previamente (para evitar resolverlos repetidamente y generar tiempo de cálculo adicional), se puede denominar programación dinámica o memorización .
Una definición de función recursiva tiene uno o más casos base , es decir, entradas para las cuales la función produce un resultado trivialmente (sin recurrencia), y uno o más casos recursivos , es decir, entradas para las cuales el programa recurre (se llama a sí mismo). Por ejemplo, la función factorial se puede definir recursivamente mediante las ecuaciones 0! = 1 y, para todo n > 0 , n ! = n ( n − 1)! . Ninguna ecuación por sí sola constituye una definición completa; la primera es el caso base y la segunda es el caso recursivo. Debido a que el caso base rompe la cadena de recursión, a veces también se lo denomina "caso de terminación".
La función de los casos recursivos puede considerarse como la de descomponer entradas complejas en otras más simples. En una función recursiva correctamente diseñada, con cada llamada recursiva, el problema de entrada debe simplificarse de tal manera que, eventualmente, se alcance el caso base. (Las funciones que no están destinadas a terminar en circunstancias normales, por ejemplo, algunos procesos del sistema y del servidor , son una excepción a esto). No escribir un caso base o probarlo incorrectamente puede causar un bucle infinito .
Para algunas funciones (como una que calcula la serie para e = 1/0! + 1/1! + 1/2! + 1/3! + ... ) no hay un caso base obvio implícito en los datos de entrada; para estas, se puede agregar un parámetro (como el número de términos que se agregarán, en nuestro ejemplo de serie) para proporcionar un "criterio de detención" que establezca el caso base. Un ejemplo de este tipo se trata de manera más natural mediante la correcursión , [ ¿cómo? ] donde los términos sucesivos en la salida son las sumas parciales; esto se puede convertir en una recursión utilizando el parámetro de indexación para decir "calcular el término n º ( suma parcial n º)".
Muchos programas informáticos deben procesar o generar una cantidad arbitrariamente grande de datos . La recursión es una técnica para representar datos cuyo tamaño exacto es desconocido para el programador : el programador puede especificar estos datos con una definición autorreferencial . Existen dos tipos de definiciones autorreferenciales: definiciones inductivas y definiciones coinductivas .
Una definición de datos recursiva definida de forma inductiva es aquella que especifica cómo construir instancias de los datos. Por ejemplo, las listas enlazadas se pueden definir de forma inductiva (aquí, utilizando la sintaxis de Haskell ):
datos ListOfStrings = EmptyList | Contras String ListOfStrings El código anterior especifica que una lista de cadenas puede estar vacía o ser una estructura que contiene una cadena y una lista de cadenas. La autorreferencia en la definición permite la construcción de listas de cualquier número (finito) de cadenas.
Otro ejemplo de definición inductiva son los números naturales (o enteros positivos ):
Un número natural es 1 o n+1, donde n es un número natural.
De manera similar, las definiciones recursivas se utilizan a menudo para modelar la estructura de expresiones y sentencias en lenguajes de programación. Los diseñadores de lenguajes suelen expresar gramáticas en una sintaxis como la forma Backus-Naur ; a continuación se muestra una gramática de este tipo para un lenguaje simple de expresiones aritméticas con multiplicación y suma:
< expr > ::= < número > | ( < expr > * < expr > ) | ( < expr > + < expr > )Esto indica que una expresión es un número, un producto de dos expresiones o una suma de dos expresiones. Al hacer referencia recursiva a expresiones en la segunda y tercera líneas, la gramática permite expresiones aritméticas arbitrariamente complicadas, como (5 * ((3 * 6) + 8)), con más de una operación de producto o suma en una sola expresión.
Una definición de datos coinductivos es aquella que especifica las operaciones que se pueden realizar en un fragmento de datos; normalmente, las definiciones coinductivas autorreferenciales se utilizan para estructuras de datos de tamaño infinito.
Una definición coinductiva de flujos infinitos de cadenas, dada de manera informal, podría verse así:
Un flujo de cadenas es un objeto tal que: cabeza(s) es una cadena, y tail(s) es un flujo de cadenas.
Esto es muy similar a una definición inductiva de listas de cadenas; la diferencia es que esta definición especifica cómo acceder al contenido de la estructura de datos (es decir, a través de las funciones de accesohead y tail) y cuáles pueden ser esos contenidos, mientras que la definición inductiva especifica cómo crear la estructura y a partir de qué se puede crear.
La recursión correccional está relacionada con la coinducción y se puede utilizar para calcular instancias particulares de objetos (posiblemente) infinitos. Como técnica de programación, se utiliza con mayor frecuencia en el contexto de lenguajes de programación perezosos y puede ser preferible a la recursión cuando se desconoce el tamaño o la precisión deseados de la salida de un programa. En tales casos, el programa requiere tanto una definición para un resultado infinitamente grande (o infinitamente preciso) como un mecanismo para tomar una porción finita de ese resultado. El problema de calcular los primeros n números primos es uno que se puede resolver con un programa recursivo correccional (por ejemplo, aquí ).
La recursión que contiene sólo una única autorreferencia se conoce comorecursión única , mientras que la recursión que contiene múltiples autorreferencias se conoce comorecursión múltiple . Los ejemplos estándar de recursión simple incluyen el recorrido de una lista, como en una búsqueda lineal, o el cálculo de la función factorial, mientras que los ejemplos estándar de recursión múltiple incluyenel recorrido de un árbol, como en una búsqueda en profundidad.
La recursión simple suele ser mucho más eficiente que la recursión múltiple y, por lo general, se puede reemplazar por un cálculo iterativo, que se ejecuta en tiempo lineal y requiere un espacio constante. La recursión múltiple, por el contrario, puede requerir tiempo y espacio exponenciales y es fundamentalmente más recursiva, ya que no se puede reemplazar por iteración sin una pila explícita.
La recursión múltiple a veces se puede convertir en recursión simple (y, si se desea, de ahí a iteración). Por ejemplo, mientras que el cálculo de la secuencia de Fibonacci implica ingenuamente iteración múltiple, ya que cada valor requiere dos valores previos, se puede calcular mediante recursión simple pasando dos valores sucesivos como parámetros. Esto se enmarca de manera más natural como corecursión, que se construye a partir de los valores iniciales, mientras se rastrean dos valores sucesivos en cada paso; consulte corecursión: ejemplos . Un ejemplo más sofisticado implica el uso de un árbol binario enhebrado , que permite el recorrido iterativo del árbol, en lugar de recursión múltiple.
La mayoría de los ejemplos básicos de recursión, y la mayoría de los ejemplos presentados aquí, demuestranrecursión directa , en la que una función se llama a sí misma. La recursión indirecta ocurre cuando una función no es llamada por ella misma sino por otra función a la que llamó (ya sea directa o indirectamente). Por ejemplo, si f llama a f, se trata de recursión directa, pero si f llama a g que llama a f, entonces se trata de recursión indirecta de f. Son posibles cadenas de tres o más funciones; por ejemplo, la función 1 llama a la función 2, la función 2 llama a la función 3 y la función 3 llama a la función 1 nuevamente.
La recursión indirecta también se denomina recursión mutua , que es un término más simétrico, aunque esto es simplemente una diferencia de énfasis, no una noción diferente. Es decir, si f llama a g y luego g llama a f, que a su vez llama a g nuevamente, desde el punto de vista de f solamente, f es recursiva indirectamente, mientras que desde el punto de vista de g solamente, es recursiva indirectamente, mientras que desde el punto de vista de ambos, f y g son mutuamente recursivas entre sí. De manera similar, un conjunto de tres o más funciones que se llaman entre sí puede llamarse un conjunto de funciones mutuamente recursivas.
La recursión se realiza normalmente llamando explícitamente a una función por su nombre. Sin embargo, la recursión también se puede realizar llamando implícitamente a una función en función del contexto actual, lo que resulta especialmente útil para funciones anónimas y se conoce como recursión anónima .
Algunos autores clasifican la recursión como "estructural" o "generativa". La distinción está relacionada con el lugar de donde un procedimiento recursivo obtiene los datos con los que trabaja y cómo los procesa:
[Las funciones que consumen datos estructurados] normalmente descomponen sus argumentos en sus componentes estructurales inmediatos y luego procesan esos componentes. Si uno de los componentes inmediatos pertenece a la misma clase de datos que la entrada, la función es recursiva. Por ese motivo, nos referimos a estas funciones como FUNCIONES (ESTRUCTURALMENTE) RECURSIVAS.
— Felleisen, Findler, Flatt y Krishnaurthi, Cómo diseñar programas , 2001 [6]
Por lo tanto, la característica definitoria de una función recursiva estructural es que el argumento de cada llamada recursiva es el contenido de un campo de la entrada original. La recursión estructural incluye casi todos los recorridos de árboles, incluido el procesamiento XML, la creación y búsqueda de árboles binarios, etc. Si se considera la estructura algebraica de los números naturales (es decir, un número natural es cero o el sucesor de un número natural), las funciones como factorial también pueden considerarse recursión estructural.
La recursión generativa es la alternativa:
Muchos algoritmos recursivos conocidos generan un conjunto de datos completamente nuevo a partir de los datos dados y recurren a ellos. HtDP ( How to Design Programs ) se refiere a este tipo como recursión generativa. Algunos ejemplos de recursión generativa incluyen: gcd , quicksort , búsqueda binaria , mergesort , método de Newton , fractales e integración adaptativa .
— Matthias Felleisen, Programación funcional avanzada , 2002 [7]
Esta distinción es importante para probar la terminación de una función.
En la implementación real, en lugar de una función recursiva pura (una única comprobación para el caso base, de lo contrario un paso recursivo), se pueden realizar una serie de modificaciones, con fines de claridad o eficiencia. Estas incluyen:
En términos de elegancia, las funciones envolventes suelen ser aprobadas, mientras que la eliminación del caso base está mal vista, en particular en el ámbito académico. Los algoritmos híbridos se utilizan a menudo por razones de eficiencia, para reducir la sobrecarga de la recursión en casos pequeños, y la recursión a distancia es un caso especial de esto.
Una función envolvente es una función que se llama directamente pero que no recurre a sí misma, sino que llama a una función auxiliar separada que realmente realiza la recursión.
Las funciones contenedoras se pueden utilizar para validar parámetros (de modo que la función recursiva pueda omitirlos), realizar inicializaciones (asignar memoria, inicializar variables), en particular para variables auxiliares como "nivel de recursión" o cálculos parciales para memorización , y manejar excepciones y errores. En lenguajes que admiten funciones anidadas , la función auxiliar se puede anidar dentro de la función contenedora y utilizar un ámbito compartido. En ausencia de funciones anidadas, las funciones auxiliares son en cambio una función separada, si es posible privada (ya que no se las llama directamente), y la información se comparte con la función contenedora mediante el uso de paso por referencia .
El cortocircuito del caso base, también conocido como recursión a distancia , consiste en comprobar el caso base antes de realizar una llamada recursiva, es decir, comprobar si la siguiente llamada será el caso base, en lugar de llamar y luego comprobar el caso base. El cortocircuito se realiza particularmente por razones de eficiencia, para evitar la sobrecarga de una llamada de función que retorna inmediatamente. Tenga en cuenta que, dado que el caso base ya se ha comprobado (inmediatamente antes del paso recursivo), no es necesario comprobarlo por separado, pero es necesario utilizar una función contenedora para el caso cuando la recursión general comienza con el caso base en sí. Por ejemplo, en la función factorial, correctamente el caso base es 0! = 1, mientras que devolver inmediatamente 1 para 1! es un cortocircuito y puede perder 0; esto se puede mitigar con una función contenedora. El cuadro muestra el código C para abreviar los casos factoriales 0 y 1.
El cortocircuito es principalmente una preocupación cuando se encuentran muchos casos base, como punteros nulos en un árbol, que pueden ser lineales en el número de llamadas de función, por lo tanto, ahorros significativos para algoritmos O ( n ) ; esto se ilustra a continuación para una búsqueda en profundidad. El cortocircuito en un árbol corresponde a considerar una hoja (nodo no vacío sin hijos) como el caso base, en lugar de considerar un nodo vacío como el caso base. Si solo hay un solo caso base, como en el cálculo del factorial, el cortocircuito proporciona solo ahorros O (1) .
Conceptualmente, se puede considerar que el cortocircuito tiene el mismo caso base y el mismo paso recursivo, comprobando el caso base solo antes de la recursión, o se puede considerar que tiene un caso base diferente (un paso eliminado del caso base estándar) y un paso recursivo más complejo, es decir, "verificar si es válido y luego recurrir", como al considerar nodos de hoja en lugar de nodos nulos como casos base en un árbol. Debido a que el cortocircuito tiene un flujo más complicado, en comparación con la clara separación del caso base y el paso recursivo en la recursión estándar, a menudo se considera un estilo deficiente, particularmente en el ámbito académico. [8]
Un ejemplo básico de cortocircuito se da en la búsqueda en profundidad (DFS) de un árbol binario; consulte la sección de árboles binarios para una discusión recursiva estándar.
El algoritmo recursivo estándar para un DFS es:
En cortocircuito, esto es en cambio:
En términos de los pasos estándar, esto mueve la verificación del caso base antes del paso recursivo. Alternativamente, estos pueden considerarse una forma diferente de caso base y paso recursivo, respectivamente. Tenga en cuenta que esto requiere una función contenedora para manejar el caso cuando el árbol en sí está vacío (el nodo raíz es nulo).
En el caso de un árbol binario perfecto de altura h, hay 2 nodos h +1 −1 y 2 punteros nulos h +1 como hijos (2 para cada una de las 2 hojas h ), por lo que el cortocircuito reduce a la mitad el número de llamadas de función en el peor de los casos.
En C, el algoritmo recursivo estándar se puede implementar como:
bool tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) return false ; // caso base de lo contrario if ( tree_node -> data == i ) return true ; de lo contrario return tree_contains ( tree_node -> left , i ) || tree_contains ( tree_node -> right , i ); } El algoritmo de cortocircuito se puede implementar como:
// Función contenedora para manejar el árbol vacío bool tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) return false ; // árbol vacío else return tree_contains_do ( tree_node , i ); // llamar a la función auxiliar } // Supone que tree_node != NULL bool tree_contains_do ( struct node * tree_node , int i ) { if ( tree_node -> data == i ) return true ; // encontrado de lo contrario // recurse return ( tree_node -> left && tree_contains_do ( tree_node -> left , i )) || ( tree_node -> right && tree_contains_do ( tree_node -> right , i )); } Tenga en cuenta el uso de la evaluación de cortocircuito de los operadores booleanos && (AND), de modo que la llamada recursiva se realiza solo si el nodo es válido (no nulo). Tenga en cuenta que, si bien el primer término en AND es un puntero a un nodo, el segundo término es un booleano, por lo que la expresión general se evalúa como un booleano. Este es un modismo común en el cortocircuito recursivo. Esto se suma a la evaluación de cortocircuito del operador booleano || (OR), para verificar solo el hijo derecho si el hijo izquierdo falla. De hecho, todo el flujo de control de estas funciones se puede reemplazar con una sola expresión booleana en una declaración de retorno, pero la legibilidad se ve afectada sin beneficio para la eficiencia.
Los algoritmos recursivos suelen ser ineficientes para datos pequeños, debido a la sobrecarga de las llamadas y devoluciones de funciones repetidas. Por esta razón, las implementaciones eficientes de algoritmos recursivos a menudo comienzan con el algoritmo recursivo, pero luego cambian a un algoritmo diferente cuando la entrada se vuelve pequeña. Un ejemplo importante es la ordenación por fusión , que a menudo se implementa cambiando a la ordenación por inserción no recursiva cuando los datos son suficientemente pequeños, como en la ordenación por fusión en mosaico . Los algoritmos recursivos híbridos a menudo se pueden refinar aún más, como en Timsort , derivado de una ordenación por fusión/inserción híbrida.
La recursión y la iteración son igualmente expresivas: la recursión se puede reemplazar por iteración con una pila de llamadas explícita , mientras que la iteración se puede reemplazar con recursión de cola . Qué enfoque es preferible depende del problema en consideración y del lenguaje utilizado. En la programación imperativa , se prefiere la iteración, particularmente para la recursión simple, ya que evita la sobrecarga de las llamadas a funciones y la gestión de la pila de llamadas, pero la recursión se usa generalmente para la recursión múltiple. Por el contrario, en los lenguajes funcionales se prefiere la recursión, con la optimización de la recursión de cola que conduce a poca sobrecarga. Implementar un algoritmo usando iteración puede no ser fácil de lograr.
Compare las plantillas para calcular x n definido por x n = f(n, x n-1 ) a partir de x base :
Para un lenguaje imperativo, la sobrecarga es definir la función, y para un lenguaje funcional, la sobrecarga es definir la variable acumuladora x.
Por ejemplo, una función factorial se puede implementar iterativamente en C asignándola a una variable de índice de bucle y a una variable de acumulador, en lugar de pasar argumentos y devolver valores por recursión:
unsigned int factorial ( unsigned int n ) { unsigned int producto = 1 ; // el producto vacío es 1 while ( n ) { producto *= n ; -- n ; } return producto ; } La mayoría de los lenguajes de programación que se utilizan hoy en día permiten la especificación directa de funciones y procedimientos recursivos. Cuando se llama a una función de este tipo, el entorno de ejecución del programa realiza un seguimiento de las distintas instancias de la función (a menudo utilizando una pila de llamadas , aunque se pueden utilizar otros métodos). Cada función recursiva se puede transformar en una función iterativa reemplazando las llamadas recursivas con construcciones de control iterativas y simulando la pila de llamadas con una pila gestionada explícitamente por el programa. [9] [10]
Por el contrario, todas las funciones y procedimientos iterativos que pueden ser evaluados por una computadora (ver completitud de Turing ) pueden ser expresados en términos de funciones recursivas; las construcciones de control iterativas como los bucles while y for son rutinariamente reescritas en forma recursiva en lenguajes funcionales . [11] [12] Sin embargo, en la práctica esta reescritura depende de la eliminación de llamadas de cola , que no es una característica de todos los lenguajes. C , Java y Python son lenguajes convencionales notables en los que todas las llamadas de función, incluyendo las llamadas de cola , pueden causar una asignación de pila que no ocurriría con el uso de construcciones de bucle; en estos lenguajes, un programa iterativo funcional reescrito en forma recursiva puede desbordar la pila de llamadas , aunque la eliminación de llamadas de cola puede ser una característica que no está cubierta por la especificación de un lenguaje, y diferentes implementaciones del mismo lenguaje pueden diferir en las capacidades de eliminación de llamadas de cola.
En lenguajes (como C y Java ) que favorecen construcciones de bucles iterativos, generalmente hay un costo significativo de tiempo y espacio asociado con los programas recursivos, debido a la sobrecarga requerida para administrar la pila y la relativa lentitud de las llamadas de función; en lenguajes funcionales , una llamada de función (particularmente una llamada de cola ) es típicamente una operación muy rápida, y la diferencia generalmente es menos notoria.
Como ejemplo concreto, la diferencia de rendimiento entre las implementaciones recursivas e iterativas del ejemplo "factorial" anterior depende en gran medida del compilador utilizado. En lenguajes en los que se prefieren las construcciones de bucle, la versión iterativa puede ser hasta varios órdenes de magnitud más rápida que la recursiva. En lenguajes funcionales, la diferencia de tiempo total entre las dos implementaciones puede ser insignificante; de hecho, el costo de multiplicar primero los números más grandes en lugar de los números más pequeños (que es lo que hace la versión iterativa que se da aquí) puede superar cualquier tiempo ahorrado al elegir la iteración.
En algunos lenguajes de programación, el tamaño máximo de la pila de llamadas es mucho menor que el espacio disponible en el montón , y los algoritmos recursivos tienden a requerir más espacio en la pila que los algoritmos iterativos. En consecuencia, estos lenguajes a veces imponen un límite a la profundidad de la recursión para evitar desbordamientos de pila ; Python es uno de esos lenguajes. [13] Tenga en cuenta la advertencia a continuación con respecto al caso especial de la recursión de cola .
Debido a que los algoritmos recursivos pueden estar sujetos a desbordamientos de pila, pueden ser vulnerables a entradas patológicas o maliciosas . [14] Algunos programas maliciosos apuntan específicamente a la pila de llamadas de un programa y se aprovechan de la naturaleza inherentemente recursiva de la pila. [15] Incluso en ausencia de malware, un desbordamiento de pila causado por una recursión ilimitada puede ser fatal para el programa, y la lógica de manejo de excepciones puede no evitar que se finalice el proceso correspondiente . [16]
Los problemas recursivos multiplicativos son inherentemente recursivos, debido al estado anterior que necesitan rastrear. Un ejemplo es el recorrido de árboles como en la búsqueda en profundidad ; aunque se utilizan métodos recursivos e iterativos, [17] contrastan con el recorrido de listas y la búsqueda lineal en una lista, que es un método recursivo simple y, por lo tanto, naturalmente iterativo. Otros ejemplos incluyen algoritmos de divide y vencerás como Quicksort y funciones como la función de Ackermann . Todos estos algoritmos se pueden implementar de forma iterativa con la ayuda de una pila explícita , pero el esfuerzo del programador involucrado en la gestión de la pila y la complejidad del programa resultante posiblemente superen cualquier ventaja de la solución iterativa.
Los algoritmos recursivos pueden ser reemplazados por contrapartes no recursivas. [18] Un método para reemplazar algoritmos recursivos es simularlos usando memoria heap en lugar de memoria stack . [19] Una alternativa es desarrollar un algoritmo de reemplazo basado completamente en métodos no recursivos, lo que puede ser un desafío. [20] Por ejemplo, los algoritmos recursivos para hacer coincidir comodines , como el algoritmo wildmat de Rich Salz , [21] alguna vez fueron típicos. Los algoritmos no recursivos para el mismo propósito, como el algoritmo de comodines de coincidencia de Krauss , se han desarrollado para evitar los inconvenientes de la recursión [22] y han mejorado solo gradualmente en función de técnicas como la recopilación de pruebas y el perfil del rendimiento. [23]
Las funciones recursivas de cola son funciones en las que todas las llamadas recursivas son llamadas de cola y, por lo tanto, no generan operaciones diferidas. Por ejemplo, la función gcd (que se muestra nuevamente a continuación) es recursiva de cola. En contraste, la función factorial (también a continuación) no es recursiva de cola; debido a que su llamada recursiva no está en la posición de cola, genera operaciones de multiplicación diferidas que deben realizarse después de que se complete la llamada recursiva final. Con un compilador o intérprete que trata las llamadas recursivas de cola como saltos en lugar de llamadas de función, una función recursiva de cola como gcd se ejecutará utilizando espacio constante. Por lo tanto, el programa es esencialmente iterativo, equivalente a utilizar estructuras de control de lenguaje imperativas como los bucles "for" y "while".
La importancia de la recursión de cola es que cuando se realiza una llamada recursiva de cola (o cualquier llamada de cola), no es necesario guardar la posición de retorno del invocador en la pila de llamadas ; cuando la llamada recursiva retorna, se ramificará directamente en la posición de retorno guardada previamente. Por lo tanto, en lenguajes que reconocen esta propiedad de las llamadas de cola, la recursión de cola ahorra espacio y tiempo.
Considere estas dos funciones:
void funcionRecursiva ( int num ) { printf ( "%d \n " , num ); if ( num < 4 ) funcionRecursiva ( num + 1 ); } 
void funcionRecursiva ( int num ) { if ( num < 4 ) funcionRecursiva ( num + 1 ); printf ( "%d \n " , num ); } 
La salida de la función 2 es la de la función 1 con las líneas intercambiadas.
En el caso de una función que se llama a sí misma solo una vez, las instrucciones colocadas antes de la llamada recursiva se ejecutan una vez por recursión antes que cualquiera de las instrucciones colocadas después de la llamada recursiva. Estas últimas se ejecutan repetidamente después de que se haya alcanzado la recursión máxima.
Tenga en cuenta también que el orden de las declaraciones de impresión está invertido, lo que se debe a la forma en que las funciones y declaraciones se almacenan en la pila de llamadas .
Un ejemplo clásico de procedimiento recursivo es la función utilizada para calcular el factorial de un número natural :
La función también se puede escribir como una relación de recurrencia :
Esta evaluación de la relación de recurrencia demuestra el cálculo que se realizaría al evaluar el pseudocódigo anterior:
Esta función factorial también se puede describir sin utilizar recursión haciendo uso de las construcciones de bucle típicas que se encuentran en los lenguajes de programación imperativos:
El código imperativo anterior es equivalente a esta definición matemática utilizando una variable acumuladora t :
La definición anterior se traduce directamente a lenguajes de programación funcional como Scheme ; este es un ejemplo de iteración implementada de forma recursiva.
El algoritmo euclidiano , que calcula el máximo común divisor de dos números enteros, se puede escribir de forma recursiva.
Definición de función :
Relación de recurrencia para el máximo común divisor, donde expresa el resto de :
El programa recursivo anterior es recursivo de cola ; es equivalente a un algoritmo iterativo, y el cálculo que se muestra arriba muestra los pasos de evaluación que se realizarían con un lenguaje que elimina las llamadas de cola. A continuación se muestra una versión del mismo algoritmo que utiliza iteración explícita, adecuada para un lenguaje que no elimina las llamadas de cola. Al mantener su estado completamente en las variables x e y y al utilizar una construcción de bucle, el programa evita realizar llamadas recursivas y hacer crecer la pila de llamadas.
El algoritmo iterativo requiere una variable temporal, e incluso conociendo el algoritmo euclidiano es más difícil entender el proceso mediante una simple inspección, aunque los dos algoritmos son muy similares en sus pasos.
Las Torres de Hanoi es un rompecabezas matemático cuya solución ilustra la recursión. [24] [25] Hay tres clavijas que pueden sostener pilas de discos de diferentes diámetros. Un disco más grande nunca puede apilarse sobre uno más pequeño. Comenzando con n discos en una clavija, deben moverse a otra clavija uno a la vez. ¿Cuál es el menor número de pasos para mover la pila?
Definición de función :
Relación de recurrencia para Hanoi :
Implementaciones de ejemplo:
Aunque no todas las funciones recursivas tienen una solución explícita, la secuencia de la Torre de Hanoi se puede reducir a una fórmula explícita. [26]
El algoritmo de búsqueda binaria es un método para buscar un solo elemento en una matriz ordenada , dividiendo la matriz por la mitad en cada pasada recursiva. El truco consiste en elegir un punto medio cerca del centro de la matriz, comparar los datos en ese punto con los datos que se están buscando y luego responder a una de las tres condiciones posibles: los datos se encuentran en el punto medio, los datos en el punto medio son mayores que los datos que se están buscando o los datos en el punto medio son menores que los datos que se están buscando.
En este algoritmo se utiliza la recursión porque con cada pasada se crea una nueva matriz cortando la anterior a la mitad. Luego se llama al procedimiento de búsqueda binaria de forma recursiva, esta vez sobre la nueva matriz (más pequeña). Normalmente, el tamaño de la matriz se ajusta manipulando un índice inicial y uno final. El algoritmo muestra un orden de crecimiento logarítmico porque, en esencia, divide el dominio del problema a la mitad con cada pasada.
Ejemplo de implementación de búsqueda binaria en C:
/* Llamar a binary_search con las condiciones iniciales adecuadas. ENTRADA: data es una matriz de números enteros ORDENADOS en orden ASCENDENTE, toFind es el número entero a buscar, count es el número total de elementos en la matriz SALIDA: resultado de la búsqueda binaria*/ int search ( int * data , int toFind , int count ) { // Inicio = 0 (índice inicial) // Fin = count - 1 (índice superior) return binary_search ( data , toFind , 0 , count -1 ); } /* Algoritmo de búsqueda binaria. ENTRADA: data es una matriz de números enteros ORDENADOS en orden ASCENDENTE, toFind es el número entero a buscar, start es el índice mínimo de la matriz, end es el índice máximo de la matriz SALIDA: posición del número entero toFind dentro de la matriz data, -1 si no se encuentra */ int binary_search ( int * data , int toFind , int start , int end ) { //Obtener el punto medio. int mid = start + ( end - start ) / 2 ; //División de números enteros if ( start > end ) //Condición de detención (caso base) return -1 ; else if ( data [ mid ] == toFind ) //Encontrado, devuelve índice return mid ; else if ( data [ mid ] > toFind ) //Los datos son mayores que toFind, busca en la mitad inferior return binary_search ( data , toFind , start , mid -1 ); else //Los datos son menores que toFind, busca en la mitad superior return binary_search ( data , toFind , mid + 1 , end ); } Una aplicación importante de la recursión en la informática es la definición de estructuras de datos dinámicas, como listas y árboles . Las estructuras de datos recursivas pueden crecer dinámicamente hasta alcanzar un tamaño teóricamente infinito en respuesta a los requisitos de tiempo de ejecución; por el contrario, el tamaño de una matriz estática debe establecerse en el momento de la compilación.
"Los algoritmos recursivos son particularmente apropiados cuando el problema subyacente o los datos a tratar se definen en términos recursivos". [27]
Los ejemplos de esta sección ilustran lo que se conoce como "recursión estructural". Este término se refiere al hecho de que los procedimientos recursivos actúan sobre datos que se definen de forma recursiva.
Siempre que un programador derive la plantilla a partir de una definición de datos, las funciones emplean la recursión estructural, es decir, las recursiones en el cuerpo de una función consumen una parte inmediata de un valor compuesto dado. [7]
A continuación se muestra una definición en C de una estructura de nodo de lista enlazada. Observe especialmente cómo se define el nodo en términos de sí mismo. El elemento "next" de struct node es un puntero a otro struct node , lo que crea efectivamente un tipo de lista.
struct node { int data ; // algunos datos enteros struct node * next ; // puntero a otro struct node }; Debido a que la estructura de datos del nodo struct se define de forma recursiva, los procedimientos que operan sobre ella se pueden implementar de forma natural como procedimientos recursivos. El procedimiento list_print definido a continuación recorre la lista hasta que esta se vacía (es decir, el puntero de lista tiene un valor NULL). Para cada nodo, imprime el elemento de datos (un entero). En la implementación de C, la lista permanece sin cambios mediante el procedimiento list_print .
void list_print ( struct node * list ) { if ( list != NULL ) // caso base { printf ( "%d" , list -> data ); // imprime datos enteros seguidos de un espacio list_print ( list -> next ); // llamada recursiva en el siguiente nodo } } A continuación se muestra una definición sencilla de un nodo de árbol binario. Al igual que el nodo de las listas enlazadas, se define en términos de sí mismo, de forma recursiva. Hay dos punteros autorreferenciales: izquierdo (que apunta al subárbol izquierdo) y derecho (que apunta al subárbol derecho).
struct node { int data ; // algunos datos enteros struct node * left ; // puntero al subárbol izquierdo struct node * right ; // apunta al subárbol derecho }; Las operaciones en el árbol se pueden implementar mediante recursión. Tenga en cuenta que, dado que hay dos punteros autorreferenciales (izquierdo y derecho), las operaciones en el árbol pueden requerir dos llamadas recursivas:
// Prueba si tree_node contiene i; devuelve 1 si es así, 0 si no. int tree_contains ( struct node * tree_node , int i ) { if ( tree_node == NULL ) devuelve 0 ; // caso base de lo contrario if ( tree_node -> data == i ) devuelve 1 ; de lo contrario devuelve tree_contains ( tree_node -> left , i ) || tree_contains ( tree_node -> right , i ); } Se realizarán como máximo dos llamadas recursivas para cualquier llamada dada a tree_contains como se definió anteriormente.
// Recorrido en orden: void tree_print ( struct node * tree_node ) { if ( tree_node != NULL ) { // caso base tree_print ( tree_node -> left ); // ir a la izquierda printf ( "%d " , tree_node -> data ); // imprimir el entero seguido de un espacio tree_print ( tree_node -> right ); // ir a la derecha } } El ejemplo anterior ilustra un recorrido en orden del árbol binario. Un árbol binario de búsqueda es un caso especial del árbol binario en el que los elementos de datos de cada nodo están en orden.
Dado que la cantidad de archivos en un sistema de archivos puede variar, la recursión es la única forma práctica de recorrer y, por lo tanto, enumerar su contenido. Recorrer un sistema de archivos es muy similar a recorrer un árbol , por lo tanto, los conceptos detrás del recorrido de un árbol son aplicables a recorrer un sistema de archivos. Más específicamente, el código a continuación sería un ejemplo de un recorrido en preorden de un sistema de archivos.
importar java.io.File ; clase pública Sistema de archivos { public static void principal ( cadena [] argumentos ) { atravesar ();}/** * Obtiene las raíces del sistema de archivos * Continúa con el recorrido recursivo del sistema de archivos. */privado estático void traverse () { Archivo [] fs = Archivo . listRoots (); para ( int i = 0 ; i < fs . length ; i ++ ) { Sistema .out .println ( fs [ i ] ) ;si ( fs [ i ] .isDirectory ( ) y fs [ i ] .canRead ( )) { rtraverse ( fs [ i ] );}}}/** * Recorrer recursivamente un directorio determinado * * @param fd indica el punto de inicio del recorrido */void estático privado rtraverse ( Archivo fd ) { Archivo [] fss = fd . listFiles (); para ( int i = 0 ; i < fss . length ; i ++ ) { Sistema .out .println ( fss [ i ] ) ;si ( fss [ i ] .isDirectory ( ) y fss [ i ] .canRead ( )) { rtraverse ( fss [ i ] );}}}}Este código es a la vez recursión e iteración : los archivos y directorios se iteran y cada directorio se abre de forma recursiva.
El método "rtraverse" es un ejemplo de recursión directa, mientras que el método "traverse" es una función envolvente.
El escenario del "caso base" es que siempre habrá una cantidad fija de archivos y/o directorios en un sistema de archivos determinado.
La eficiencia temporal de los algoritmos recursivos se puede expresar en una relación de recurrencia de notación Big O. Luego, se pueden simplificar (por lo general) en un solo término Big-O.
Si la complejidad temporal de la función está en la forma
Entonces el gran O de la complejidad temporal es así:
donde a representa el número de llamadas recursivas en cada nivel de recursión, b representa en qué factor se hace más pequeña la entrada para el siguiente nivel de recursión (es decir, el número de partes en las que se divide el problema) y f ( n ) representa el trabajo que la función realiza independientemente de cualquier recursión (por ejemplo, partición, recombinación) en cada nivel de recursión.
En la interpretación procedimental de programas lógicos , las cláusulas (o reglas) de la forma se tratan como procedimientos, que reducen los objetivos de la forma a subobjetivos de la forma . Por ejemplo, las cláusulas de Prolog :A :- BAB
ruta ( X , Y ) :- arco ( X , Y ). ruta ( X , Y ) :- arco ( X , Z ), ruta ( Z , Y ).define un procedimiento que se puede utilizar para buscar una ruta de X a Y , ya sea encontrando un arco directo de X a Y , o encontrando un arco de X a Z , y luego buscando recursivamente una ruta de Z a Y . Prolog ejecuta el procedimiento razonando de arriba hacia abajo (o hacia atrás ) y buscando en el espacio de posibles rutas en profundidad, una rama a la vez. Si intenta la segunda cláusula y falla finitamente en encontrar una ruta de Z a Y , retrocede e intenta encontrar un arco de X a otro nodo, y luego busca una ruta desde ese otro nodo a Y .
Sin embargo, en la lectura lógica de los programas lógicos, las cláusulas se entienden declarativamente como condicionales cuantificados universalmente. Por ejemplo, la cláusula recursiva del procedimiento de búsqueda de ruta se entiende como la representación del conocimiento de que, para cada X , Y y Z , si hay un arco de X a Z y un camino de Z a Y, entonces hay un camino de X a Y. En forma simbólica:
La lectura lógica libera al lector de la necesidad de saber cómo se utiliza la cláusula para resolver problemas. La cláusula se puede utilizar de arriba hacia abajo, como en Prolog, para reducir los problemas a subproblemas. O se puede utilizar de abajo hacia arriba (o hacia adelante ), como en Datalog , para derivar conclusiones de las condiciones. Esta separación de preocupaciones es una forma de abstracción , que separa el conocimiento declarativo de los métodos de resolución de problemas (véase Algoritmo#Algoritmo = Lógica + Control ). [28]
