Introducción a la recursión (página 2)

(Gp:) Llamadas a subprogramas

(Gp:) Memoria dinámica (Tema 9)

(Gp:) Memoria principal

Title: La pila del sistema (stack) Other Placeholder: 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

Title: La pila y las llamadas a función Other Placeholder: 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

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Entrada en la función: Se alojan los datos locales

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Llamada a función: Entra la dirección de vuelta

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Entrada en la función: Se alojan los datos locales

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Vuelta de la función: Se eliminan los datos locales

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Vuelta de la función: Sale la dirección de vuelta

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) La ejecución continúaen esa dirección

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Vuelta de la función: Se eliminan los datos locales

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) Vuelta de la función: Sale la dirección de vuelta

Other Placeholder: 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); … Title: La pila y las llamadas a función Pila

(Gp:) La ejecución continúaen esa dirección

Title: La pila y las llamadas a función Other Placeholder: Mecanismo de pila adecuado para llamadas a funciones anidadas: Las llamadas terminan en el orden contrario a como se llaman … int funcC(…) { … } int funcB(…) { … … funcC(…) } int funcA(…) { … … funcB(…) } int main() { … cout << funcA(…); …

Pila LLAMADAS VUELTAS

Title: Ejecución de la función factorial() 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; }

cout << factorial(5) << endl;

(Gp:) Obviaremos las direcciones de vuelta en la pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5)

Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3)

Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 1

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 1 1

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 1 1 2

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 1 1 2 6

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 1 1 2 6 24

Title: Ejecución de la función factorial() Other Placeholder: factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)

Pila 120 1 1 2 6 24

Title: Fundamentos de la programación Tipos de recursión

Title: Recursión simple Other Placeholder: 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

Title: Recursión múltiple Other Placeholder: Varias llamadas recursivas Ejemplo: Cálculo de los números de Fibonacci

1 si n = 1 Fib(n) 0 si n = 0 Fib(n-1) + Fib(n-2) si n > 1 (Gp:) Dos llamadas recursivas

Title: Recursión múltiple Other Placeholder: … int main() { for (int i = 0; i < 20; i++) { cout << fibonacci(i) << endl; } return 0; }

int fibonacci(int n) { int resultado; if (n == 0) { resultado = 0; } else if (n == 1) { resultado = 1; } else { resultado = fibonacci(n – 1) + fibonacci(n – 2); } return resultado; } 1 si n = 1 Fib(n) 0 si n = 0 Fib(n-1) + Fib(n-2) si n > 1 fibonacci.cpp