recursividad2

Metodolog´ıa de la Programaci´
on II

Recursividad

Objetivos

Entender el concepto de recursividad.
Conocer los fundamentos del dise˜
no de algoritmos
recursivos.
Comprender la ejecuci´
on de algoritmos recursivos.
Aprender a realizar trazas de algoritmos recursivos.
Comprender las ventajas e inconvenientes de la
recursividad.

Recursividad

2

3.1 Concepto de Recursividad

La recursividadconstituye una de las herramientas m´as potentes en programaci´
on. Es un concepto
matem´atico conocido. Por ejemplo,
Definici´
on recursiva
n! =

1
si n = 0
n · (n − 1)! si n > 0

Demostraci´
on por inducci´
on: demostrar para un
caso base y despu´es para un tama˜
no n, considerando que est´a demostrado para valores menores
que n.
✛

Una funci´
on que se llama a s´ı misma se
denomina recursiva

✚✘

✙

Podemos usar recursividad si la soluci´
on de un
problema est´a expresada en funci´
on de si misma,
aunque de menor tama˜
no y conocemos la soluci´
on
no-recursiva para un determinado caso.
Recursividad

3

Ventajas: No es necesario definir la secuencia de
pasos exacta para resolver el problema.
Desventajas: Podr´ıa ser menos eficiente.
Para que una definici´
on recursiva est´e completamenteidentificada es necesario tener un caso base
que no se calcule utilizando casos anteriores y que la
divisi´on del problema converja a ese caso base.
0! = 1

Ejemplo:
xn =

Recursividad

1
si n = 0
x · xn−1 si n > 0

4

Ejemplo: C´alculo del factorial con n=3.
3! = 3 * 2!

3! = 3 * 2!
2! = 2 * 1!

(1)

(2)

3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!

3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1
(caso base)(3)

(4)

3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 1

3! = 3 * 2!
2! = 2 * 1
1! = 1 * 1 = 1
1

(5)

(6)

3! = 3 * 2
2! = 2 * 1 = 2

3! = 3 * 2 = 6

(7)

(8)

Recursividad

5

3.2 Dise˜no de algoritmos recursivos

Para resolver un problema, el primer paso ser´a la
identificaci´
on de un algoritmo recursivo, es decir,
descomponer el problema de forma que su soluci´on
quede definida en funci´
on de ellamisma pero para
un tama˜
no menor y la tarea a realizar para un caso
simple. .
Tendremos que dise˜
nar: casos base, casos generales y la soluci´
on en t´erminos de ellos.
Casos base: Son los casos del problema que se
resuelve con un segmento de c´
odigo sin recursividad.
✓

✏

Siempre debe existir al menos un caso base
✒

✑

El n´
umero y forma de los casos base son hasta
cierto punto arbitrarios.La soluci´
on ser´a mejor
cuanto m´as simple y eficiente resulte el conjunto
de casos seleccionados.

Recursividad

6

Casos generales: Si el problema es suficientemente
complejo, la soluci´
on se expresa, de forma recursiva, como la uni´
on de
1. La soluci´
on de uno o m´as subproblemas (de
igual naturaleza pero menor tama˜
no).
2. Un conjunto de pasos adicionales. Estos pasos
junto con lassoluciones a los subproblemas
componen la soluci´
on al problema general que
queremos resolver.
✬

✩

Los casos generales siempre deben avanzar
hacia un caso base. Es decir, la llamada
recursiva se hace a un subproblema m´as
peque˜
no y, en u
´ltima instancia, los casos
generales alcanzar´an un caso base.
✫

Recursividad

✪

7

Ejemplo:
// Solucion no estructurada
int factorial (int n) {
if (n==0)//Caso base
return 1;
else
//Caso general
return n*factorial(n-1);
}
// Solucion estructurada
int factorial (int n) {
int resultado;
if (n==0)
//Caso base
resultado = 1;
else
//Caso general
resultado = n*factorial(n-1);
return resultado;
}

Recursividad

8

3.3 Ejecuci´on de un m´odulo recursivo
En general, en la pila se almacena el entorno asociado a las distintas funciones que se van activando.
Enparticular, en un m´
odulo recursivo, cada llamada recursiva genera una nueva zona de memoria
en la pila independiente del resto de llamadas.
Ejemplo: Ejecuci´
on del factorial con n=3.
1. Dentro de factorial, cada llamada
return n*factorial(n-1);
genera una nueva zona de memoria en la pila,
siendo n-1 el correspondiente par´ametro actual
para esta zona de memoria y queda pendiente
la...