Concepto de recursión 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)
Definiciones recursivas 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)
Algoritmos recursivos 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
Algoritmos recursivos 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
Algoritmos recursivos 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
Modelo de ejecución 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
La pila del sistema (stack) Regiones de memoria que distingue el sistema operativo:
(Gp:) Llamadas a subprogramas
(Gp:) Memoria dinámica (Tema 9)
(Gp:) Memoria principal
La pila del sistema (stack) Mantiene los datos locales de la función y la dirección de vuelta Estructura de tipo pila: lista LIFO (last-in first-out) El último que entra es el primero que sale:
Entra4 Entra7 Entra 2 Sale 2
La pila y las llamadas a función Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … Pila
(Gp:) Llamada a función: Entra la dirección de vuelta
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) Entrada en la función: Se alojan los datos locales
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) Llamada a función: Entra la dirección de vuelta
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) Entrada en la función: Se alojan los datos locales
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) Vuelta de la función: Se eliminan los datos locales
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) Vuelta de la función: Sale la dirección de vuelta
Datos locales y direcciones de vuelta … int funcB(int x) { … return x; } int funcA(int a) { int b; … b = funcB(a); … return b; } int main() { … cout << funcA(4); … La pila y las llamadas a función Pila
(Gp:) La ejecución continúaen esa dirección
Recursión simple Sólo hay una llamada recursiva Ejemplo: Cálculo del factorial de un número entero positivo 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:) Una sola llamada recursiva
| Página siguiente |