Actualizado el 12 de Enero del 2019 (Publicado el 17 de Diciembre del 2018)
1.210 visualizaciones desde el 17 de Diciembre del 2018
1,9 MB
35 paginas
Creado hace 10a (23/05/2014)
23/05/2014
Fundamentos de la programación
2013‐2014
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()
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
2
5
8
9
10
11
24
38
39
41
45
46
51
54
57
62
64
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 1
1
23/05/2014
2
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 2
Recursión (recursividad, recurrencia)
(N > 0)
Se dice que algo se define de forma recursiva cuando en la definición
aparece lo que se está definiendo.
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.
Factorial(N) = N x Factorial(N‐1)
(http://farm1.static.flickr.com/83
(http://farm1.static.flickr.com/83
/229219543_edf740535b.jpg)
/229219543_edf740535b.jpg)
La imagen del paquete aparece
La imagen del paquete aparece
dentro del propio paquete, que
dentro del propio paquete, que
a su vez contiene otra imagen
a su vez contiene otra imagen
del paquete... ¡hasta el infinito!
del 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 3
23/05/2014
Recursión
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,
que generaría un bucle infinito en el programa.
La definición recursiva ha de ir acompañada de uno o más casos base.
Un caso basees aquel en el que no se utiliza la definición recursiva,
sino que se proporciona un punto final de cálculo:
si N = 0
Factorial(N)=
si N > 0
Cada vez que se aplica el caso recursivo, el valor de N
se va aproximando al valor del caso base (0).
1
N xFactorial(N‐1)
Caso base (o de parada)
Caso recursivo (inducción)
Fundamentos de la programación: Introducción a la recursión
Página 4
Fundamentos de la programación: Introducción a la recursión
Página 5
3
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
23/05/2014
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;
else
resultado = n * factorial(n ‐ 1);
return resultado;
}
Fundamentos de la programación: Introducción a la recursión
Fundamentos de la programación: Introducción a la recursión
Página 7
4
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
23/05/2014
Diseño de funciones recursivas
Una función recursiva debe satisfacer tres condiciones
para estar bien diseñada:
Caso(s) base: Debe haber al menos un caso base de parada.
Inducción: Paso recursivo que provoca una llamada recursiva.
Se podrá demostrar que es correcto para distintos parámetros de entrada.
Convergencia: Cada paso recursivo debe acercarse al caso base.
Describimos el problema en términos de problemas más sencillos.
si N = 0
Factorial(N)=
si N > 0
La 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 8
Fundamentos de la programación: Introducción a la recursión
Página 9
5
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
23/05/2014
Modelo de ejecución
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,
quedando interrumpida la actual.
Cada llamada a la función 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 10
La pila del sistema (stack)
El SO dispone en la memoria de la computadora varias regiones
con diferentes propósitos:
Llamadas a funciones
Llamadas a funciones
Memoria dinámica (Tema 9)
Memoria dinámica (Tema 9)
Memoria principal
Memoria principal
Pila (Stack)
Montón (Heap)
Datos del
programa
Código del
programa
S.O.
Fundamentos de la programación: Introducción a la recursión
Página 11
6
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
23/05/2014
La pila del sistema (stack)
La pila se utiliza para guardar en cada llamada a función los datos
locales de la función y la dirección de vuelta.
Es una 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
PilaPila
4PilaPila
7
4PilaPila
2
7
4PilaPila
7
4PilaPila
Fundamentos de la programación: Introducción a la recursión
Página 12
La pila y las llamadas a función
Cada vez que se produce una llamada a una función se alojan en la pila
sus datos locales y la dirección 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:
Se guarda la dirección de vuelta
Se guarda la dirección de vuelta
PilaPila
<DIR2>
<DIR2>
<DIR1>
<DIR1>
Fundamentos de la programación: Introducción a la recursión
Página 13
7
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
23/05/2014
La pila y las llamadas a función
Cada vez que se produce una llamada a una función se alojan en la pila
sus datos locales y la dirección de vuelta.
Entrada en la función:
Entrada en la función:
Se alojan los datos locales
Se alojan los datos locales
}
int funcA(int a) {
...
int funcB(int x) {
...
return x;
PilaPila
<DIR1>
<DIR2>
<DIR2>
<DIR1>
<DIR1>
int b;
...
b = funcB(a);
...
return b;
}
int main() {
...
cout << funcA(4);
...
Fundamentos de la programación: Introducción a la recursión
Página 14
La pila y las llamadas a función
Cada vez que se produce una llamada a una función se alojan en la pila
sus datos locales y la dirección 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:
Se guarda la dirección de vuelta
Se guarda la dirección de vuelta
b
a
PilaPila
<DIR1>
Fundamentos de la programación: Introducción a la recursión
Página 15
8
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
23/05/2014
La pila y las llamadas a función
Cada vez que se produce una llamada a una función se alojan en la pila
sus datos locales y la dirección 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>
<DIR2>
b
a
PilaPila
<DIR1>
x
<DIR2>
b
a
PilaPila
<DIR1>
Fundamentos de la programación: Introducción a la recursión
Página 16
La pila y las llamadas a función
Cada vez que se vuelve de una llamada a una función se recupera
de la pila la dirección de vuelta de la función anterior.
Vuelta de la función:
Vuelta de la función:
Se eliminan los datos locales
Se eliminan 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 17
9
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
23/05/2014
La pila y las llamadas a función
Cada vez que se vuelve de una llamada a una función se recupera
de la pila la dirección de vuelta de la función anterior.
Vuelta de la función:
Vuelta de la función:
Se obtiene la dirección de vuelta
Se obtiene la dirección de vuelta
...
int funcB(int x) {
...
return x;
<DIR2>
b
a
PilaPila
<DIR1>
}
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 18
La pila y las llamadas a función
Cada vez que se vuelve de una llamada a una función se recupera
de la pila la dirección de vuelta de la función anterior.
...
int funcB(int x) {
...
return x;
}
int funcA(int a) {
int b;
...
b = funcB(a);
...
return b;
}
int main() {
...
cout << funcA(4);
...
<DIR2>
<DIR2
Links de descarga
http://lwp-l.com/pdf14565
Comentarios de: 10. Introducción a la recursión (0)
Crear cuenta
Comentarios de: 10. Introducción a la recursión (0)
No hay comentarios