Programación recursiva

Programación recursiva

La estructura de un algoritmo recursivo es:

 algo () {condición 1 condición 2 ... condición n}

Las condiciones son generalmente ifs, incluyen las condiciones de parada (no devuelve la función) o las condiciones de continuidad (reinicia la función o devuelve la función). Las condiciones de continuidad modifican las entradas de la función reiniciada. Una función recursiva debe tener al menos una condición de parada.

Recursividad simple

El programa matemático es del siguiente tipo (ejemplo para el cálculo de una potencia):

Aquí hay un ejemplo simple para calcular el factorial de n:

 int fact (n) {if (n == 0) return 1; de lo contrario, devuelve n * hecho (n-1); }

Aquí podemos ver el hecho de que la recursividad se comporta como un bucle.

Recursividad múltiple

El programa matemático es del siguiente tipo (ejemplo para la relación de Pascal):

Dará por programa:

 int pascal (n, p) {if (p == 0 || p == n) return 1; de lo contrario, devuelve pascal (p, n-1) + pascal (p-1, n-1); }

Otros tipos

Pila de ejecución

La pila de ejecución del programa actual es una ubicación de memoria destinada a memorizar los parámetros, las variables locales así como las direcciones de retorno de las funciones que se están ejecutando.

Esta pila funciona según el principio LIFO (último en entrar, primero en salir) y tiene un tamaño fijo. Aquí está la pila para el factorial simple, tan pronto como el programa lee un método, lo ejecuta, manteniendo el resto de la información en la pila, y agrega los nuevos resultados a la parte superior de la pila. Dado que es LIFO, esta última información se leerá primero, por lo que da la impresión de una pirámide de ejecución:

Llamada a un hecho (3) 3 * hecho (2) Llamado a un hecho (2) 2 * hecho (1) Llamado a un hecho (1) 1 * hecho (0) Llamado a un hecho (0) Devuelve el valor 1 Devuelve 1 * 1 Devuelve 2 * 1 Devuelve 3 * 2 Devuelve 6

La pila de ejecución de la secuencia de Fibonacci sigue el mismo principio:

int fibo (n) {return (n <2)? 1: fibo (n-1) + fibo (n-2); }

Fibo (3) Fibo (2) + esperar Llamar a Fibo (2) Fibo (1) + esperar Llamar a Fibo (1) Retorna 1 1 + Fibo (0) Llamar a Fibo (0) Retorna 1 Retorna 1 + 1 2+ Fibonacci (1) Llamada a Fibonacci (1) Devuelve 1 Devuelve 2 + 1 Devuelve 3

Vemos claramente aquí un efecto de montaña rusa debido a la aparición sucesiva de la función a la izquierda tan pronto como se encuentra. Es más fácil representar la pila de una función recursiva múltiple mediante una viaje en profundidad (vamos más lejos en los sucesores) de su árbol de llamadas recursivo:

Recursividad terminal

Por lo tanto, la pila no tiene nada en la memoria durante la recursividad. Esto significa que el valor devuelto es directamente el valor obtenido sin que exista ninguna operación adicional. Tomemos el ejemplo del factorial de forma recursiva terminal:

 int fact (n, a) {if (n == 0) return a; de lo contrario, devuelve hecho (n-1, n * a); } // ten cuidado, el valor de a al principio es muy importante

Esto es exactamente lo mismo que escribir el siguiente ciclo:

 mientras que (n! = 0 {n * = a; n--;}