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

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

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

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

Página 6

Funciones recursivas

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

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