Programación recursiva: sistemas complejos e inteligencia artificial

Contenido

Programación recursiva

La programación recursiva es una técnica de programación que reemplaza las declaraciones de bucle con llamadas a funciones. Por tanto, el mecanismo consiste, en la gran mayoría de los casos, en crear una función que se llama a sí misma una o más veces según diferentes criterios.

La estructura de un algoritmo recursivo es:

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

Las condiciones suelen ser si, incluyen condiciones de parada (no devolver la función) o condiciones de continuación (reiniciar la función o devolver 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

Una función simplemente recursiva se llama a sí misma como máximo una vez en cada condición.

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

Una función recursiva múltiple puede llamarse a sí misma varias veces en cada condición.

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

Dos algoritmos son "mutuamente" recursivos si uno llama al otro y viceversa.

Un algoritmo contiene una recursión "anidada" si un parámetro de la recursión es una llamada a sí mismo.

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 (last in first out) 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 reteniendo el resto de la información en la pila y agrega los nuevos resultados a la parte superior de la pila. Como 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

Se dice que una función es recursiva de cola si el resultado de esta llamada es el resultado de la función.

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

 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--;}