Recursión (informática)

El caso base especifica los valores de entrada para los cuales la función puede proporcionar un resultado directamente, sin recursión adicional. ^{[ 11 ]} Estos suelen ser los valores de entrada más simples o pequeños posibles (que se pueden resolver trivialmente), lo que permite que el cálculo finalice. Los casos base son esenciales porque evitan la regresión infinita. En otras palabras, definen una condición de parada que finaliza la recursión.

Un ejemplo es el cálculo del factorial de un entero n, que es el producto de todos los enteros desde 0 hasta n. Para este problema, la definición 0! = 1 es un caso base. Sin ella, la recursión podría continuar indefinidamente, lo que provocaría errores de no terminación o incluso desbordamiento de pila en implementaciones reales.

Diseñar un caso base correcto es crucial tanto por razones teóricas como prácticas. Algunos problemas tienen un caso base natural (por ejemplo, la lista vacía es un caso base en algunas funciones recursivas de procesamiento de listas), mientras que otros requieren un parámetro adicional para proporcionar un criterio de parada (por ejemplo, usar un contador de profundidad en el recorrido recursivo de árboles ).

En la programación recursiva , omitir el caso base o definirlo incorrectamente puede provocar una recursión infinita no deseada. En un estudio, los investigadores demostraron que muchos estudiantes tienen dificultades para identificar los casos base adecuados. ^{[ 11 ]}

El caso recursivo describe cómo dividir un problema en subproblemas más pequeños de la misma forma. ^{[ 11 ]} Cada paso recursivo transforma la entrada de manera que se aproxime a un caso base, asegurando el progreso hacia la terminación. Si el paso de reducción no logra progresar hacia un caso base, el algoritmo puede quedar atrapado en un bucle infinito .

En el ejemplo del factorial , el caso recursivo se define como: ${\displaystyle n!=n\cdot (n-1)!\,,\forall n>0.}$ Aquí, cada invocación de la función disminuye la entrada.${\displaystyle n}$por 1. De este modo, se asegura de que la recursión finalmente alcance el caso base de${\displaystyle n=0}$.

El caso recursivo es análogo al paso inductivo en una demostración por inducción : parte de la premisa de que la función funciona para una instancia menor y luego extiende esta premisa a la entrada actual. Por lo tanto, las definiciones y algoritmos recursivos guardan un estrecho paralelismo con los argumentos inductivos en matemáticas , y su corrección a menudo se basa en técnicas de razonamiento similares.

Existen diversas aplicaciones prácticas de la recursión que siguen la estructura de caso base y caso recursivo. Estas se utilizan ampliamente para resolver problemas complejos en informática.

• Los recorridos de árboles , como la búsqueda en profundidad , utilizan un caso recursivo para procesar cada subárbol (el caso recursivo), deteniéndose finalmente en los nodos hoja (el caso base). ^{[ 12 ]}
• El algoritmo de ordenación por fusión es un algoritmo de ordenación que ordena y fusiona recursivamente subarreglos divididos (el caso recursivo) hasta que cada subarreglo consta de un solo elemento (el caso base). ^{[ 13 ]}
• La sucesión de Fibonacci se define sumando los dos números anteriores de la sucesión (el caso recursivo), deteniéndose cuando n = 0 o n = 1 (los casos base).
• La búsqueda binaria divide repetidamente el intervalo de búsqueda por la mitad (caso recursivo) hasta que se encuentra el objetivo o el intervalo está vacío (casos base).

Una definición de datos recursiva definida inductivamente es aquella que especifica cómo construir instancias de los datos. Por ejemplo, las listas enlazadas se pueden definir inductivamente (aquí, usando la sintaxis de Haskell ):

datos ListaDeCadenas = ListaVacía | Cons Cadena ListaDeCadenas

El código anterior especifica una lista de cadenas que 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 forma 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 las gramáticas en una sintaxis como la de Backus-Naur ; aquí se muestra una gramática de este tipo para un lenguaje sencillo 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, el producto de dos expresiones o la suma de dos expresiones. Al referirse recursivamente a las expresiones en la segunda y tercera línea, la gramática permite expresiones aritméticas arbitrariamente complejas, 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 coinductiva es aquella que especifica las operaciones que se pueden realizar sobre un dato; normalmente, las definiciones coinductivas autorreferenciales se utilizan para estructuras de datos de tamaño infinito.

Una definición coinductiva de secuencias infinitas de cadenas, dada de manera informal, podría verse así:

Una secuencia de cadenas es un objeto s tal que: cabeza(s) es una cadena, y tail(s) es una secuencia 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 —a saber, a través de las funciones de accesohead y— y tailcuál puede ser ese contenido, mientras que la definición inductiva especifica cómo crear la estructura y de qué se puede crear.

La corecursión está relacionada con la coinducción y puede utilizarse para calcular instancias particulares de objetos (posiblemente) infinitos. Como técnica de programación, se usa 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 puede resolverse con un programa corecursivo (por ejemplo, aquí ).

La recursión que contiene una sola autorreferencia se conoce comorecursión simple , 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 listas, 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 árboles, 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, puede sustituirse por un cálculo iterativo que se ejecuta en tiempo lineal y requiere espacio constante. La recursión múltiple, en cambio, puede requerir tiempo y espacio exponenciales y es fundamentalmente recursiva, ya que no puede sustituirse por iteración sin una pila explícita.

En ocasiones, la recursión múltiple puede convertirse en recursión simple (y, si se desea, posteriormente en iteración). Por ejemplo, si bien el cálculo de la secuencia de Fibonacci implica ingenuamente múltiples iteraciones, ya que cada valor requiere dos valores previos, puede calcularse mediante recursión simple pasando dos valores sucesivos como parámetros.

La mayoría de los ejemplos básicos de recursión, y la mayoría de los ejemplos presentados aquí, demuestranLa recursión directa se produce cuando una función se llama a sí misma. La recursión indirecta ocurre cuando una función no es llamada por sí misma, sino por otra función a la que llamó (directa o indirectamente). Por ejemplo, si f llama a f, se trata de recursión directa; pero si f llama a g, que a su vez 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 vuelve a llamar a la función 1.

La recursión indirecta también se denomina recursión mutua , un término más simétrico, aunque se trata simplemente de una diferencia de énfasis, no de un concepto distinto. Es decir, si f llama a g y luego g llama a f, que a su vez vuelve a llamar a g , desde el punto de vista de f , f es indirectamente recursiva, mientras que desde el punto de vista de g , también lo es indirectamente, y desde el punto de vista de ambas, f y g son mutuamente recursivas. De forma similar, un conjunto de tres o más funciones que se llaman entre sí puede denominarse conjunto de funciones mutuamente recursivas.

La recursión se suele realizar llamando explícitamente a una función por su nombre. Sin embargo, también se puede realizar llamando implícitamente a una función en función del contexto actual, lo cual es 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 radica en de dónde obtiene un procedimiento recursivo los datos con los que trabaja y cómo los procesa.

Las funciones que consumen datos estructurados suelen descomponer sus argumentos en sus componentes estructurales inmediatos y luego procesarlos. Si alguno de los componentes inmediatos pertenece a la misma clase de datos que la entrada, la función es recursiva. Por ello, nos referimos a estas funciones como FUNCIONES RECURSIVAS (ESTRUCTURALMENTE).

Así, 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 abarca casi todos los recorridos de árboles, incluyendo el procesamiento de XML, la creación y búsqueda de árboles binarios, etc. Al considerar la estructura algebraica de los números naturales (es decir, un número natural es cero o el sucesor de un número natural), funciones como el factorial también pueden considerarse recursión estructural.

La recursión generativa es la alternativa:

Muchos algoritmos recursivos conocidos generan un dato completamente nuevo a partir de los datos dados y lo procesan recursivamente. HtDP ( How to Design Programs ) se refiere a este tipo como recursión generativa. Algunos ejemplos de recursión generativa son: el máximo común divisor (MCD) , el algoritmo de ordenación rápida (Quicksort) , la búsqueda binaria , el algoritmo de ordenación por fusión (Mergesort) , el método de Newton , los fractales y la integración adaptativa .

Esta distinción es importante para demostrar la terminación de una función.

• Se puede demostrar fácilmente, mediante inducción estructural , que todas las funciones recursivas estructurales sobre estructuras de datos finitas ( definidas inductivamente ) terminan : intuitivamente, cada llamada recursiva recibe una porción más pequeña de datos de entrada, hasta que se alcanza un caso base.
• En cambio, las funciones generativamente recursivas no necesariamente alimentan sus llamadas recursivas con datos de entrada cada vez más pequeños, por lo que demostrar su terminación no es tan sencillo y evitar bucles infinitos requiere mayor cuidado. Estas funciones generativamente recursivas a menudo pueden interpretarse como funciones correcursivas: cada paso genera nuevos datos, como la aproximación sucesiva en el método de Newton, y para terminar esta correcursión se requiere que los datos finalmente satisfagan alguna condición, lo cual no está necesariamente garantizado.
• En términos de variantes de bucle , la recursión estructural se da cuando existe una variante de bucle obvia, concretamente en tamaño o complejidad, que comienza siendo finita y disminuye en cada paso recursivo.
• Por el contrario, la recursión generativa se da cuando no existe una variante de bucle tan obvia, y la terminación depende de una función, como el "error de aproximación", que no necesariamente disminuye a cero, por lo que la terminación no está garantizada sin un análisis adicional.

Una función contenedora es una función que se llama directamente pero que no realiza la recursión por sí misma, sino que llama a una función auxiliar separada que es la que realmente realiza la recursión.

Las funciones de envoltura se pueden usar para validar parámetros (de modo que la función recursiva pueda omitirlos), realizar la inicialización (asignar memoria, inicializar variables), particularmente para variables auxiliares como el "nivel de recursión" o cálculos parciales para la memorización , y manejar excepciones y errores. En lenguajes que admiten funciones anidadas , la función auxiliar puede anidarse dentro de la función de envoltura y usar 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 llaman directamente), y la información se comparte con la función de envoltura usando paso por referencia .

La recursión de cortocircuito, también conocida como recursión de alcance limitado , 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 a la función y luego comprobarlo. El cortocircuito se realiza principalmente por razones de eficiencia, para evitar la sobrecarga de una llamada a función que devuelve un valor inmediatamente. Cabe destacar que, dado que el caso base ya se ha comprobado (inmediatamente antes del paso recursivo), no es necesario comprobarlo por separado, pero sí se debe utilizar una función envoltorio para el caso en que la recursión general comience con el propio caso base. Por ejemplo, en la función factorial, el caso base correcto es 0! = 1, mientras que devolver inmediatamente 1 para 1! es un cortocircuito y puede omitir el 0; esto se puede mitigar mediante una función envoltorio. El recuadro muestra código C para atajar los casos 0 y 1 del factorial.

El cortocircuito es una preocupación principal cuando se encuentran muchos casos base, como los punteros nulos en un árbol, que pueden ser lineales en el número de llamadas a funciones, lo que supone un ahorro significativo para los 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 caso base, en lugar de considerar un nodo vacío como caso base. Si solo hay un caso base, como en el cálculo del factorial, el cortocircuito proporciona un ahorro de solo O (1) .

Conceptualmente, el cortocircuito puede considerarse como tener el mismo caso base y paso recursivo, verificando el caso base solo antes de la recursión, o puede considerarse como tener un caso base diferente (un paso separado del caso base estándar) y un paso recursivo más complejo, a saber, "verificar válido y luego recursar", como al considerar nodos 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. ^{[ 16 ]}

bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // caso base } else if ( node- > data == i ) { return true ; } else { return tree_contains ( node- > left , i ) || tree_contains ( node- > right , i ); } }

#incluir <assert.h>// Función envoltorio para manejar árboles vacíos bool tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return false ; // árbol vacío } else { return tree_contains_aux ( node , i ); // llamar a la función auxiliar } }// Se asume que nodo != NULL bool tree_contains_aux ( struct BinaryTree * nodo , int i ) { assert ( nodo ); if ( nodo -> datos == i ) { return true ; // encontrado } else { // recursión return ( nodo -> izquierda && tree_contains_aux ( nodo -> izquierda , i )) || ( nodo -> derecha && tree_contains_aux ( nodo -> derecha , i )); } }

Los algoritmos recursivos suelen ser ineficientes para conjuntos de datos pequeños, debido a la sobrecarga que suponen las llamadas y devoluciones repetidas de funciones. Por este motivo, las implementaciones eficientes de algoritmos recursivos suelen comenzar con el algoritmo recursivo, pero luego cambian a otro algoritmo cuando la entrada se reduce. Un ejemplo importante es el ordenamiento por fusión (merge sort) , que a menudo se implementa cambiando al ordenamiento por inserción no recursivo cuando los datos son suficientemente pequeños, como en el ordenamiento por fusión en mosaico (tilesed merge sort ). Los algoritmos recursivos híbridos a menudo se pueden refinar aún más, como en Timsort , derivado de un ordenamiento por fusión/inserción híbrido.

La mayoría de los lenguajes de programación actuales 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 mediante una pila de llamadas , aunque pueden utilizarse otros métodos). Toda función recursiva puede transformarse en una función iterativa sustituyendo las llamadas recursivas por estructuras de control iterativas y simulando la pila de llamadas con una pila gestionada explícitamente por el programa. ^{[ 17 ] [ 18 ]}

Por el contrario, todas las funciones y procedimientos iterativos que pueden ser evaluados por una computadora (ver Completitud de Turing ) pueden expresarse en términos de funciones recursivas; las construcciones de control iterativas como los bucles while y for se reescriben rutinariamente en forma recursiva en lenguajes funcionales . ^{[ 19 ] [ 20 ]} 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 principales notables en los que todas las llamadas a funciones, incluidas las llamadas de cola , pueden causar 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 las estructuras de bucle iterativas, los programas recursivos suelen tener un coste significativo en tiempo y espacio debido a la sobrecarga necesaria para gestionar la pila y la relativa lentitud de las llamadas a funciones; en los lenguajes funcionales , una llamada a una función (en particular una llamada recursiva ) suele ser una operación muy rápida, y la diferencia suele ser menos perceptible.

Como ejemplo concreto, la diferencia de rendimiento entre las implementaciones recursiva e iterativa del ejemplo del factorial anterior depende en gran medida del compilador utilizado. En lenguajes donde se prefieren las estructuras 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 ambas implementaciones puede ser insignificante; de ​​hecho, el coste de multiplicar primero los números mayores en lugar de los menores (como ocurre en la versión iterativa que se presenta aquí) puede anular cualquier ahorro de tiempo derivado de 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. ^{[ 21 ]} Nótese 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 . ^{[ 22 ]} Algunos programas maliciosos atacan específicamente la pila de llamadas de un programa y aprovechan su naturaleza inherentemente recursiva. ^{[ 23 ]} Incluso en ausencia de malware, un desbordamiento de pila causado por recursión ilimitada puede ser fatal para el programa, y ​​la lógica de manejo de excepciones puede no impedir que el proceso correspondiente se termine . ^{[ 24 ]}

Los problemas recursivos múltiples son inherentemente recursivos, debido al estado previo que necesitan rastrear. Un ejemplo es el recorrido de árboles como en la búsqueda en profundidad ; aunque se utilizan métodos tanto recursivos como iterativos, ^{[ 25 ]} 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 pueden implementarse iterativamente con la ayuda de una pila explícita , pero el esfuerzo del programador involucrado en administrar la pila y la complejidad del programa resultante, posiblemente superan cualquier ventaja de la solución iterativa.

Los algoritmos recursivos pueden reemplazarse por contrapartes no recursivas. ^{[ 26 ]} Un método para reemplazar algoritmos recursivos es simularlos usando memoria heap en lugar de memoria stack . ^{[ 27 ]} Una alternativa es desarrollar un algoritmo de reemplazo basado completamente en métodos no recursivos, lo cual puede ser un desafío. ^{[ 28 ]} Por ejemplo, los algoritmos recursivos para la coincidencia de comodines , como el algoritmo wildmat de Rich Salz , ^{[ 29 ]} fueron típicos en el pasado. Se han desarrollado algoritmos no recursivos para el mismo propósito, como el algoritmo de coincidencia de comodines de Krauss , para evitar los inconvenientes de la recursión ^{[ 30 ]} y han mejorado solo gradualmente basándose en técnicas como la recopilación de pruebas y el perfilado del rendimiento. ^{[ 31 ]}

#include <stdio.h>void recursiveFunction ( int num ) { if ( num < 4 ) { recursiveFunction ( num + 1 ); } printf ( "%d \n " , num ); }

El resultado de la función 2 es el mismo que el de la función 1, pero 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 una vez que se ha alcanzado el número máximo de recursiones.

Tenga en cuenta también que el orden de las instrucciones de impresión está invertido, lo cual se debe a la forma en que las funciones y las instrucciones 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 :

${\displaystyle \operatorname {fact} (n)={\begin{cases}1&{\mbox{si }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{si }}n>0\\\end{cases}}}$

La función también se puede escribir como una relación de recurrencia :

${\displaystyle b_{n}=nb_{n-1}}$

${\displaystyle b_{0}=1}$

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 usar recursión, utilizando las estructuras 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 :

${\displaystyle {\begin{aligned}\operatorname {fact} (n)&=\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&={\begin{cases}t&{\mbox{si }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{si }}n>0\\\end{cases}}\end{aligned}}}$

La definición anterior se traduce fácilmente a lenguajes de programación funcional como Scheme ; este es un ejemplo de iteración implementada recursivamente.

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 la función :

${\displaystyle \gcd(x,y)={\begin{cases}x&{\mbox{si }}y=0\\\gcd(y,\operatorname {resto} (x,y))&{\mbox{si }}y>0\\\end{cases}}}$

Relación de recurrencia para el máximo común divisor, donde${\displaystyle x\%y}$expresa el resto de${\displaystyle x/y}$:

${\displaystyle \gcd(x,y)=\gcd(y,x\%y)}$si${\displaystyle y\neq 0}$

${\displaystyle \gcd(x,0)=x}$

El programa recursivo anterior es recursivo de cola ; es equivalente a un algoritmo iterativo, y el cálculo mostrado anteriormente ilustra los pasos de evaluación que realizaría un lenguaje que elimina las llamadas de cola. A continuación, se presenta 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 utilizar una estructura de bucle, el programa evita realizar llamadas recursivas y aumentar la pila de llamadas.

El algoritmo iterativo requiere una variable temporal, e incluso conociendo el algoritmo euclidiano, es más difícil comprender el proceso mediante una simple inspección, aunque ambos algoritmos son muy similares en sus pasos.

Las Torres de Hanoi es un rompecabezas matemático cuya solución ilustra la recursión. ^{[ 32 ] [ 33 ]} 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 por uno. ¿Cuál es el número mínimo de pasos para mover la pila?

Definición de la función :

${\displaystyle \operatorname {hanoi} (n)={\begin{cases}1&{\mbox{si }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{si }}n>1\\\end{cases}}}$

Relación de recurrencia para Hanoi :

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

Ejemplos de implementación:

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. ^{[ 34 ]}

El algoritmo de búsqueda binaria es un método para buscar un único elemento en un arreglo ordenado, dividiendo el arreglo por la mitad en cada iteración recursiva. El truco consiste en elegir un punto medio cercano al centro del arreglo, comparar los datos en ese punto con los datos que se buscan y, a continuación, responder a una de tres posibles condiciones: los datos se encuentran en el punto medio, los datos en el punto medio son mayores que los datos que se buscan, o los datos en el punto medio son menores que los datos que se buscan.

Este algoritmo utiliza la recursión porque, en cada iteración, se crea un nuevo array dividiendo el anterior por la mitad. A continuación, se llama recursivamente al procedimiento de búsqueda binaria, esta vez sobre el nuevo array (más pequeño). Normalmente, el tamaño del array se ajusta modificando un índice inicial y uno final. El algoritmo presenta un crecimiento logarítmico, ya que, en esencia, divide el dominio del problema por la mitad en cada iteración.

Ejemplo de implementación de búsqueda binaria en C:

/** * @brief Llama a binary_search con las condiciones iniciales adecuadas. * @param data un array de enteros ORDENADOS en orden ASCENDENTE * @param target el entero que se va a buscar * @param count el número total de elementos en el array * @returns el resultado de binary_search */ int search ( int data [], int target , int count ) { // Inicio = 0 (índice inicial) // Fin = count - 1 (índice superior) return binary_search ( data , target , 0 , count - 1 ); }/** * @brief Algoritmo de búsqueda binaria. * @param data un array de enteros ORDENADO en orden ASCENDENTE * @param target el entero a buscar * @param start el índice mínimo del array * @param end el índice máximo del array * @returns la posición del entero a encontrar dentro del array data, -1 si no se encuentra */ int binary_search ( int data [], int target , int start , int end ) { //Obtener el punto medio. int mid = start + ( end - start ) / 2 ; //División enteraif ( start > end ) { return -1 ; // Condición de parada (caso base) } else if ( data [ mid ] == target ) { return mid ; // Encontrado, devolver índice } else if ( data [ mid ] > target ) { // Los datos son mayores que el objetivo, buscar en la mitad inferior return binary_search ( data , target , start , mid - 1 ); } else { // Los datos son menores que el objetivo, buscar en la mitad superior return binary_search ( data , target , mid + 1 , end ); } }

A continuación se muestra la definición en C de la estructura de un nodo de lista enlazada. Nótese especialmente cómo se define el nodo en términos de sí mismo. El elemento "next" LinkedListes un puntero a otra lista enlazada, creando así un tipo de lista.

struct LinkedList { int data ; // algunos datos enteros struct LinkedList * next ; // puntero a otro nodo de la lista enlazada };

Dado que la estructura de datos `struct node` se define recursivamente, los procedimientos que operan sobre ella pueden implementarse de forma natural como procedimientos recursivos. El procedimiento `list_print` que se define a continuación recorre la lista hasta que esta queda vacía (es decir, el puntero a la lista tiene el valor NULL). Para cada nodo, imprime el elemento de datos (un número entero). En la implementación en C, la lista permanece sin cambios tras la ejecución del procedimiento `list_print` .

void list_print ( struct LinkedList * list ) { // caso base if ( list ) { printf ( "%d " , list -> data ); // imprime datos enteros seguidos de un espacio list_print ( list -> next ); // llamada recursiva al siguiente nodo } }

A continuación se presenta una definición sencilla para un nodo de árbol binario. Al igual que el nodo de las listas enlazadas, se define recursivamente en términos de sí mismo. Existen dos punteros autorreferenciales: izquierdo (que apunta al subárbol izquierdo) y derecho (que apunta al subárbol derecho).

struct BinaryTree { int data ; // algunos datos enteros struct BinaryTree * left ; // puntero al subárbol izquierdo struct BinaryTree * right ; // puntero al subárbol derecho };

Las operaciones en el árbol se pueden implementar mediante recursión. Tenga en cuenta que, debido a que hay dos punteros autorreferenciales (izquierdo y derecho), las operaciones en el árbol pueden requerir dos llamadas recursivas:

// Comprueba si tree_node contiene i; devuelve 1 si es así, 0 si no. int tree_contains ( struct BinaryTree * node , int i ) { if ( ! node ) { return 0 ; // caso base } else if ( node -> data == i ) { return 1 ; } else { return tree_contains ( node -> left , i ) || tree_contains ( node -> right , i ); } }

Se realizarán como máximo dos llamadas recursivas para cualquier llamada dada a tree_contains tal como se definió anteriormente.

// Recorrido en orden: void tree_print ( struct BinaryTree * node ) { // caso base if ( node ) { tree_print ( node -> left ); // ir a la izquierda printf ( "%d " , node -> data ); // imprimir el entero seguido de un espacio tree_print ( node -> right ); // ir a la derecha } }

El ejemplo anterior ilustra un recorrido en orden de un árbol binario. Un árbol de búsqueda binaria es un caso especial de árbol binario donde los elementos de datos de cada nodo están ordenados.

Dado que el número de archivos en un sistema de archivos puede variar, la recursión es la única forma práctica de recorrerlo y, por lo tanto, enumerar su contenido. Recorrer un sistema de archivos es muy similar a recorrer un árbol ; por consiguiente, los conceptos que subyacen al recorrido de árboles son aplicables al recorrido de un sistema de archivos. Más concretamente, el siguiente código sería un ejemplo de recorrido en preorden de un sistema de archivos.

paquete org.wikipedia.examples ;import java.io.File ;public class Example { /**  * Obtiene las raíces del sistema de archivos  * Procede con el recorrido recursivo del sistema de archivos  */ private static void traverse () { File [] fs = File . listRoots (); for ( int i = 0 ; i < fs . length ; i ++ ) { System . out . println ( fs [ i ] ); if ( fs [ i ] . isDirectory () && fs [ i ] . canRead ()) { rtraverse ( fs [ i ] ); } } }/**  * Recorre recursivamente un directorio dado  *  * @param fd indica el punto de inicio del recorrido  */ private static void rtraverse ( File fd ) { File [] fss = fd . listFiles ();for ( int i = 0 ; i < fss . length ; i ++ ) { System . out . println ( fss [ i ] ); if ( fss [ i ] . isDirectory () && fss [ i ] . canRead ()) { rtraverse ( fss [ i ] ); } } }public static void main ( String [] args ) { traverse (); } }

Este código utiliza tanto recursión como iteración : se itera sobre los archivos y directorios, 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 "base" es que siempre habrá un número fijo de archivos y/o directorios en un sistema de archivos determinado.

Si la complejidad temporal de la función tiene la forma $${\displaystyle T(n)=a\cdot T(n/b)+f(n)}$$

Entonces, la notación Big O de la complejidad temporal es la siguiente:

• Si${\displaystyle f(n)=O(n^{\log _{b}a-\varepsilon })}$por alguna constante${\displaystyle \varepsilon >0}$, entonces${\displaystyle T(n)=\Theta (n^{\log _{b}a})}$
• Si${\displaystyle f(n)=\Theta (n^{\log _{b}a})}$, entonces${\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}$
• Si${\displaystyle f(n)=\Omega (n^{\log _{b}a+\varepsilon })}$por alguna constante${\displaystyle \varepsilon >0}$y si${\displaystyle a\cdot f(n/b)\leq c\cdot f(n)}$para alguna constante c < 1 y para todos los n suficientemente grandes , entonces${\displaystyle T(n)=\Theta (f(n))}$

donde a representa el número de llamadas recursivas en cada nivel de recursión, b representa por qué factor menor es 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.