Introducción a la recursión

Title: Fundamentos de la programación
Recursión

Title: Concepto de recursión
Other Placeholder: Recursión (recursividad, recurrencia)
Definición recursiva: En la definición aparece lo que se define
Factorial(N) = N x Factorial(N-1) (N >= 0)

(Gp:) (wikipedia.org)
(Gp:) La imagen del paqueteaparece dentro del propiopaquete,… ¡hasta el infinito!

(Gp:) (wikipedia.org)
(Gp:) Cada triángulo estáformado por otros triángulos más pequeños

(Gp:) La cámara graba lo que graba
(http://farm1.static.flickr.com/83/229219543_edf740535b.jpg)

(Gp:) Las matrioskas rusas

Title: Definiciones recursivas
Other Placeholder: Factorial(N) = N x Factorial(N-1)
El factorial se define en función de sí mismo
Los programas no pueden manejar la recursión infinita
La definición recursiva debe adjuntar uno o más casos base
Caso base: aquel en el que no se utiliza la definición recursiva
Proporcionan puntos finales de cálculo:

El valor de N se va aproximando al valor del caso base (0)
N x Factorial(N-1) si N > 0 Caso recursivo (inducción)
Factorial(N)
1 si N = 0 Caso base (o de parada)

Title: Fundamentos de la programación
Algoritmos recursivos

Title: Algoritmos recursivos
Other Placeholder: Funciones recursivas
Una función puede implementar un algoritmo recursivo
La función se llamará a sí misma si no se ha llegado al caso base

long long int factorial(int n) {
long long int resultado;
if (n == 0) { // Caso base
resultado = 1;
}
else {
resultado = n * factorial(n – 1);
}
return resultado;
}
(Gp:) N x Factorial(N-1) si N > 0
(Gp:) Factorial(N)
(Gp:) 1 si N = 0

Title: Algoritmos recursivos
Other Placeholder: Funciones recursivas
long long int factorial(int n) {
long long int resultado;
if (n == 0) { // Caso base
resultado = 1;
}
else {
resultado = n * factorial(n – 1);
}
return resultado;
}
factorial(5) ? 5 x factorial(4) ? 5 x 4 x factorial(3)
? 5 x 4 x 3 x factorial(2) ? 5 x 4 x 3 x 2 x factorial(1)
? 5 x 4 x 3 x 2 x 1 x factorial(0) ? 5 x 4 x 3 x 2 x 1 x 1
? 120
(Gp:) Caso base

factorial.cpp

Title: Algoritmos recursivos
Other Placeholder: Diseño de funciones recursivas
Una función recursiva debe satisfacer tres condiciones:
Caso(s) base: Debe haber al menos un caso base de parada
Inducción: Paso recursivo que provoca una llamada recursiva
Debe ser correcto para distintos parámetros de entrada
Convergencia: Cada paso recursivo debe acercar a un caso base
Se describe el problema en términos de problemas más sencillos

Función factorial(): tiene caso base (N = 0), siendo correcta para N es correcta para N+1 (inducción) y se acerca cada vez más al caso base (N-1 está más cerca de 0 que N)
(Gp:) N x Factorial(N-1) si N > 0
(Gp:) Factorial(N)
(Gp:) 1 si N = 0

Title: Fundamentos de la programación
Modelo de ejecución

Title: Modelo de ejecución
Other Placeholder: long long int factorial(int n) {
long long int resultado;
if (n == 0) { // Caso base
resultado = 1;
}
else {
resultado = n * factorial(n – 1);
}
return resultado;
}
Cada llamada recursiva fuerza una nueva ejecución de la función
Cada llamada utiliza sus propios parámetros por valor y variables locales (n y resultado en este caso)
En las llamadas a la función se utiliza la pila del sistema para mantener los datos locales y la dirección de vuelta