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  |