PDF de programación - 10. Introducción a la recuersión

Fundamentos de la programación

10

Grado en Ingeniería Informática
Grado en Ingeniería del Software
Grado en Ingeniería de Computadores
Facultad de Informática
Luis Hernández Yáñez
Universidad Complutense

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

Fundamentos de la programación: Introducción a la recursión

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

983
986
987
989
990
992
994
1005
1018
1019
1020
1022
1026
1027
1032
1034
1035
1038
1043
1045

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Introducción a la recursión

Página 983

Recursión (recursividad, recurrencia)

Factorial(N) = N xFactorial(N‐1)

Definición recursiva: En la definición aparece lo que se define

(N >= 0)

Cada triángulo está
Cada triángulo está
formado por otros
formado por otros
triángulos más pequeños
triángulos más pequeños

La cámara graba lo que graba
La cámara graba lo que graba
(http://farm1.static.flickr.com/83
(http://farm1.static.flickr.com/83
/229219543_edf740535b.jpg)
/229219543_edf740535b.jpg)
La imagen del paquete
La imagen del paquete
aparece dentro del propio
aparece dentro del propio
paquete,... ¡hasta el infinito!
paquete,... ¡hasta el infinito!

(wikipedia.org)
(wikipedia.org)
Las matrioskasrusas
Las matrioskasrusas

(wikipedia.org)
(wikipedia.org)

Fundamentos de la programación: Introducción a la recursión

Página 984

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:
N xFactorial(N‐1) si N > 0
Factorial(N)
si N = 0
1
El valor de N se va aproximando al valor del caso base (0)

Caso recursivo (inducción)

Caso base (o de parada)

Fundamentos de la programación: Introducción a la recursión

Página 985

Fundamentos de la programación: Introducción a la recursión

Página 986

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

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
Factorial(N)

1
N xFactorial(N‐1)

si N = 0
si N > 0

long long int factorial(int n) {

long long int resultado;
if (n == 0) { // Caso base

resultado = 1;

resultado = n * factorial(n ‐ 1);

}
else {

}
return resultado;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Fundamentos de la programación: Introducción a la recursión

Página 987

Funciones recursivas

factorial.cpp
factorial.cpp

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 xfactorial(4) 5 x4 xfactorial(3)
5 x4 x3 xfactorial(2) 5 x4 x3 x2 xfactorial(1)
5 x4 x3 x2 x1 xfactorial(0) 5 x4 x3 x2 x1 x1
120

Caso base
Caso base

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Introducción a la recursión

Página 988

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
si N = 0
Factorial(N)
si N > 0
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)

1
N xFactorial(N‐1)

Fundamentos de la programación: Introducción a la recursión

Página 989

Fundamentos de la programación: Introducción a la recursión

Página 990

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

long long int factorial(int n) {

long long int resultado;
if (n == 0) { // Caso base

resultado = 1;

}
else {

}
return resultado;

resultado = n * factorial(n ‐ 1);

}Cada llamada recursiva fuerza una nueva ejecución de la función
Cada llamada utiliza sus propios parámetros por valor
y variables locales (ny resultadoen 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

Fundamentos de la programación: Introducción a la recursión

Página 991

Regiones de memoria que distingue el sistema operativo:
Llamadas a subprogramas
Llamadas a subprogramas
Memoria dinámica (Tema 9)
Memoria dinámica (Tema 9)
Memoria principal
Memoria principal

Datos del programa

Montón (Heap)

Código del programa

Pila (Stack)

S.O.

Fundamentos de la programación: Introducción a la recursión

Página 992

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

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:
Entra 2Entra 2

Entra7Entra7

Entra4Entra4

Sale 2Sale 2

4

7
4

2
7
4

7
4

Fundamentos de la programación: Introducción a la recursión

Página 993

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);
...

Llamada a función:
Llamada a función:
Entra la dirección de vuelta
Entra la dirección de vuelta

PilaPila

<DIR2>
<DIR2>

<DIR1>
<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 994

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

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

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 995

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

Llamada a función:
Llamada a función:
Entra la dirección de vuelta
Entra la dirección de vuelta

b
a

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 996

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Datos locales y direcciones de vuelta

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

...
int funcB(int x) {

...
return x;

}
int funcA(int a) {

int b;
...
b = funcB(a);
...   
return b;

}
int main() {

...
cout << funcA(4);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 997

<DIR2>

b
a

PilaPila

<DIR1>

x

<DIR2>

b
a

PilaPila

<DIR1>

Vuelta de la función:
Vuelta de la función:
Se eliminan los datos locales
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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 998

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Vuelta de la función:
Vuelta de la función:
Sale la dirección de vuelta
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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

<DIR2>

b
a

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 999

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

La ejecución continúa
La ejecución continúa
en esa dirección
en esa dirección

b
a

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 1000

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

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

b
a

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 1001

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

Vuelta de la función:
Vuelta de la función:
Sale la dirección de vuelta
Sale la dirección de vuelta

PilaPila

<DIR1>

Fundamentos de la programación: Introducción a la recursión

Página 1002

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

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);
...

<DIR2>
<DIR2>

<DIR1>
<DIR1>

La ejecución continúa