Recursión:
En términos de programación, una función recursiva se puede definir como una rutina que se llama a sí misma directa o indirectamente.
usando algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Torres de Hanoi (TOH) es uno de esos ejercicios de programación. Intenta escribir un algoritmo iterativo para TOH. Además, cada programa recursivo se puede escribir utilizando métodos iterativos (consulte estructuras de datos de Lipschutz).la recursión matemática ayuda a resolver pocos puzzles fácilmente.,
por ejemplo, una pregunta de entrevista de rutina,
en un grupo de N personas, cada persona estrechará su mano con la otra persona solo una vez. En total, ¿cuántos apretones de manos sucederían?
solución:
Se puede resolver de diferentes maneras, gráficos, recursión, etc. Veamos, cómo recursivamente se puede resolver.hay N personas. Cada persona se estrechan la mano una sola vez. Considerando N-ésima persona, (s)tiene que estrechar la mano con (N-1) personas. Ahora el problema se reduce a una pequeña instancia de (N-1) personas. Suponiendo que TN es un apretón de manos total, puede formularse recursivamente.,
TN = (N-1) + TN-1
resolverlo recursivamente produce una serie aritmética, que puede ser evaluada a N(N-1)/2.
ejercicio: en un grupo de N parejas, solo un género (ya sea masculino o femenino) puede estrechar la mano con cada uno. ¿Cuántos apretones de manos sucederían?
generalmente los programas recursivos resultan en complejidades de tiempo pobres. Un ejemplo es la serie de Fibonacci. La complejidad de tiempo de calcular el n-ésimo número de Fibonacci usando recursión es aproximadamente 1.6 n. significa que la misma computadora toma casi 60% más tiempo para el siguiente número de Fibonacci. El algoritmo recursivo de Fibonacci tiene subproblemas superpuestos., Hay otras técnicas como la programación dinámica para mejorar tales algoritmos superpuestos.
sin embargo, pocos algoritmos, (por ejemplo, merge sort, quick sort, etc)) resulta en una complejidad de tiempo óptima usando recursión.
caso Base:
un requisito crítico de las funciones recursivas es el punto de terminación o caso base. Cada programa recursivo debe tener un caso base para asegurarse de que la función terminará. La falta de caso base da lugar a un comportamiento inesperado.,
diferentes formas de escribir Funciones recursivas
función que se llama a sí misma: (forma directa)
La mayoría de Nosotros conscientes al menos dos formas diferentes de escribir programas recursivos. A continuación se muestra el código torres de Hanoi. Es un ejemplo de llamada directa.

salida:

Move the disk 1 from S to DMove the disk 2 from S to AMove the disk 1 from D to AMove the disk 3 from S to DMove the disk 1 from A to SMove the disk 2 from A to DMove the disk 1 from S to D

la complejidad de tiempo de TOH se puede calcular formulando el número de movimientos.necesitamos mover los primeros discos N-1 del origen al auxiliar y del auxiliar al destino, es decir, los primeros discos N-1 requieren dos movimientos. Un movimiento más del último disco de la fuente al destino., Matemáticamente se puede definir recursivamente.
MN = 2MN-1 + 1.podemos resolver fácilmente la relación recursiva anterior (2N-1), que es exponencial.
Recursión usando llamada a función mutua: (forma indirecta)
llamada indirecta. Aunque menos práctico, una función puede llamar a otra función que inturn llama a la función anterior. En este caso, ambas funciones deben tener el caso base.
programación defensiva:
podemos combinar técnicas de codificación defensiva con recursión para una funcionalidad elegante de la aplicación., Por lo general, la programación recursiva no está permitida en aplicaciones críticas de seguridad, como controles de vuelo, monitoreo de salud, etc. Sin embargo, se puede usar una técnica de conteo estático para evitar llamadas incontroladas (no en sistemas críticos de seguridad, se puede usar en sistemas de tiempo real suaves).

la profundidad callDepth depende del tamaño del marco de la pila de funciones y del tamaño máximo de la pila.
Recursión usando punteros de función: (forma indirecta)
la recursión también se puede implementar con punteros de función. Un ejemplo es signal handler in POSIX complaint systems., Si el controlador provoca el mismo evento debido al cual se llama al controlador, la función volverá a entrar.