Title: Índice Other Placeholder: Concepto de recursión Algoritmos recursivos Funciones recursivas Diseño de funciones recursivas Modelo de ejecución La pila del sistema La pila y las llamadas a función Ejecución de la función factorial() Tipos de recursión Recursión simple Recursión múltiple Recursión anidada Recursión cruzada Código del subprograma recursivo Parámetros y recursión Ejemplos de algoritmos recursivos Búsqueda binaria Torres de Hanoi Recursión frente a iteración Estructuras de datos recursivas
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
| Página siguiente |