PDF de programación - Tema 2 - Diseño de algoritmos recursivos

TEMA 2

DISEÑO DE ALGORITMOS RECURSIVOS


1. Introducción a la recursión
2. Diseño de algoritmos recursivos
3. Análisis de algoritmos recursivos
4. Transformación de la recursión final a forma iterativa
5. Técnicas de generalización



Bibliografía:



Fundamentals of Data Structures in C++
E. Horowitz, S. Sahni, D. Mehta
Computer Science Press, 1995
Data Abstraction and Problem Solving with C++, Second
Edition
Carrano, Helman y Veroff



Diseño de algoritmos recursivos



1

2.1 Introducción a la recursión
Optamos por una solución recursiva cuando sabemos cómo resolver de mane-
ra directa un problema para un cierto conjunto de datos, y para el resto de los
datos somos capaces de resolverlo utilizando la solución al mismo problema
con unos datos “más simples”.


Cualquier solución recursiva se basa en un análisis (clasificación) de los datos,
xr , para distinguir los casos de solución directa y los casos de solución recursi-
va:
— caso(s) directo(s): xr es tal que el resultado yr puede calcularse directamente

de forma sencilla.

— caso(s) recursivo(s): sabemos cómo calcular a partir de xr otros datos más
pequeños xr ’, y sabemos además cómo calcular el resultado yr para xr supo-
niendo conocido el resultado yr ’ para xr ’.


Para implementar soluciones recursivas en un lenguaje de programación tene-
mos que utilizar una acción que se invoque a sí misma −con datos cada vez
“más simples”−: funciones o procedimientos.


Para entender la recursividad, a veces resulta útil considerar cómo se ejecutan
las acciones recursivas en una computadora, como si se crearan múltiples co-
pias del mismo código, operando sobre datos diferentes (en realidad sólo se
copian las variables locales y los parámetros por valor).
El ejemplo clásico del factorial:

int fact ( int n ) {

// P : n >= 0


int r;

if ( n == 0 ) r = 1;
else if ( n > 0 ) r = n * fact(n–1);
return r;

// Q : devuelve n!
}

¿Cómo se ejecuta la llamada fact(2)?



Diseño de algoritmos recursivos



2

Programa
principal

.
.
.

x := fact(2)

Programa
principal

.
.
.

fact(2)

.
.
.

x := fact(2)

r := n * fact(n-1)

Programa
principal

.
.
.

fact(2)

.
.
.

fact(1)

.
.
.

x := fact(2)

r := n * fact(n-1)

r := n * fact(n-1)

Programa
principal

.
.
.

fact(2)

.
.
.

fact(1)

.
.
.

x := fact(2)

r := n * fact(n-1)

r := n * fact(n-1)

fact(0)

.
.
.

r := 1



Diseño de algoritmos recursivos



3

Programa
principal

.
.
.

fact(2)

.
.
.

fact(1)

.
.
.

x := fact(2)

r := n * fact(n-1)

r := n * fact(n-1)

Programa
principal

.
.
.

fact(2)

.
.
.

x := fact(2)

r := n * fact(n-1)

Programa
principal

.
.
.

x := fact(2)



¿La recursión es importante?
— Un método muy potente de diseño y razonamiento formal.
— Tiene una relación natural con la inducción y, por ello, facilita conceptual-

mente la resolución de problemas y el diseño de algoritmos.

— Algunos lenguajes no incluyen instrucciones iterativas.



Diseño de algoritmos recursivos



4



2.1.1 Recursión simple
Decimos que una acción recursiva tiene recursión simple si cada caso recursivo
realiza exactamente una llamada recursiva. Abusando de la notación en las
asignaciones, podemos describirlo mediante el esquema general:



void nombreProc ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
// declaración de constantes
τ1 x1’ ; ... ; τn xn’ ; // xr ’
δ1 y1’ ; ... ; δm ym’ ; // yr ’

if ( d(xr ) )
yr = g(xr );
else if ( ¬d(xr ) ) {
xr ‘ = s(xr );
nombreProc(xr ‘, yr ‘);
yr = c(xr , yr ‘);
}
// Postcondición
}

donde:

— xr representa a los parámetros de entrada x1, ... , xn, xr ’ a los parámetros de
la llamada recursiva x1’, ... , xn’, yr ’ a los resultados de la llamada recursiva y1’,
... , ym’, e yr a los parámetros de salida y1, ... , ym.

— d(xr ) es la condición que determina el caso directo
— ¬d(xr ) es la condición que determina el caso recursivo
— g calcula el resultado en el caso directo
—

s, la función sucesor, calcula los argumentos para la siguiente llamada recursiva
c, la función de combinación, obtiene la combinación de los resultados de la lla-
mada recursiva yr ’ junto con los datos de entrada xr , proporcionando así el
resultado yr .

—



A la recursión simple también se la conoce como recursión lineal porque el nú-

mero de llamadas recursivas depende linealmente del tamaño de los datos.



Veamos cómo la función factorial se ajusta a este esquema de declaración:

Diseño de algoritmos recursivos



5

int fact ( int n ) {

// P : n >= 0



int r;

if ( n == 0 ) r = 1;
else if ( n > 0 ) r = n * fact(n–1);
return r;

// Q : devuelve n!
}
d(n) ⇔ n == 0
g(n) = 1
¬d(n) ⇔ n > 0
s(n) = n−1
c(n, fact(s(n))) = n * fact(s(n))


d(xr ) y ¬d(xr ) pueden desdoblarse en una alternativa con varios casos.



Ejemplo: multiplicación de dos naturales por el método del campesino egipcio

int prod ( int a, int b ) {
// P : ( a >= 0 ) && ( b >= 0 )
int r;
if ( b == 0 ) r = 0;
else if ( b == 1 ) r = a;
else if ( b > 1 && (b % 2 == 0) ) r = prod(2*a, b/2);
else if ( b > 1 && (b % 2 == 1) ) r = prod(2*a, b/2) + a;
return r;
// Q : r = a * b
}



d1(a, b) ⇔ b == 0
g1(a, b) = 0
¬d1(a, b) ⇔ b > 1 && par(b)
s1(a, b) = (2*a, b/2)
c1(a, b, prod(s1(a, b))) = prod(s1(a, b)) c2(a, b, prod(s2(a, b))) = prod(s2(a, b))+a

d2(a, b) ⇔ b == 1
g2(a, b) = 1
¬d2(a, b) ⇔ b > 1 && impar(b)
s2(a, b) = (2*a, b/2)

Recursión final
La recursión final (tail recursion) es un caso particular de recursión simple donde la
función de combinación se limita a transmitir el resultado de la llamada recur-



Diseño de algoritmos recursivos



6

siva. Se llama final porque lo último que se hace en cada pasada es la llamada
recursiva.
El resultado será siempre el obtenido en uno de los casos base.
Los algoritmos recursivos finales tienen la interesante propiedad de que pue-
den ser traducidos de manera directa a soluciones iterativas, más eficientes.


Como ejemplo de función recursiva final veamos el algoritmo de cálculo del

máximo común divisor por el método de Euclides.

int mcd( int a, int b ){
// P : ( a > 0 ) && ( b > 0 )

int m;

if ( a == b ) m = a;
else if ( a > b ) m = mcd(a–b, b);
else if ( a < b ) m = mcd(a, b–a);
return m;
// Q : devuelve mcd(a, b)
}

que se ajusta al esquema de recursión simple:


d(a, b) ⇔ a == b
g(a, b) = a
¬d1(a, b) ⇔ a > b
s1(a, b) = (a−b, a)


¬d2(a, b) ⇔ a < b
s2(a, b) = (a, b−a)

y donde las funciones de combinación se limitan a devolver el resultado de la
llamada recursiva


c1(a, b, mcd(s1(a, b))) = mcd(s1(a, b))
c2(a, b, mcd(s2(a, b))) = mcd(s2(a, b))



Diseño de algoritmos recursivos



7

2.1.2 Recursión múltiple
Este tipo de recursión se caracteriza por que, al menos en un caso recursivo, se



realizan varias llamadas recursivas. El esquema correspondiente:


void nombreProc ( τ1 x1 , … , τn xn , δ1 & y1 , … , δm & ym ) {
// Precondición
// declaración de constantes
τ1 x11 ; ... ; τn x1n ; ... τ1 xk1 ; ... ; τn xkn ;
δ1 y11 ; ... ; δm y1m ; ... δ1 yk1 ; ... ; δm ykm ;

if ( d(xr ) )
yr = g(xr );
else if ( ¬d(xr ) ) {
xr 1 = s1(xr );
nombreProc(xr 1, yr 1);
...
xr k = sk(xr );
nombreProc(xr k, yr k);
yr = c(xr , yr 1, ... , yr k);
}
// postcondición
}



donde

— k > 1, indica el número de llamadas recursivas
— xr representa a los parámetros de entrada x1,..., xn, xr

i-ésima llamada recursiva xi1,..., xin, yr
cursiva yi1,..., yim, para i = 1,..., k, e yr a los parámetros de salida y1,..., ym

i a los parámetros de la
i a los resultados de la i-ésima llamada re-

— d(xr ) es la condición que determina el caso directo
— ¬d(xr ) es la condición que determina el caso recursivo
— g calcula el resultado en el caso directo
—

si , las funciones sucesor, calculan la descomposición de los datos de entrada pa-
ra realizar la i-ésima llamada recursiva, para i = 1, ... , k
c, la función de combinación, obtiene la combinación de los resultados yr
i de las
llamadas recursivas, para i = 1, ... , k, junto con los datos de entrada xr , pro-
porcionando así el resultado yr .

—



Otro ejemplo clásico, los números de Fibonacci:



Diseño de algoritmos recursivos



8

int fibo( int n ) {
// Pre: n >= 0

int r;

if ( n == 0 ) r = 0;
else if ( n == 1 ) r = 1;
else if ( n > 1 ) r = fibo(n-1) + fibo(n-2);
return r;
// Post: devuelve fib(n)
}


que se ajusta al esquema de recursión múltiple (k = 2)


d2(n) ⇔ n == 1
g(1) == 1

d1(n) ⇔ n == 0
g(0) == 0

¬d(n) ⇔ n > 1
s1(n) = n−1
c(n, fibo(s1(n)), fibo(s2(n))) = fibo(s1(n)) + fibo(s2(n))

s2(n) = n−2


tamaño de los datos. Por ejemplo, el cómputo de fib(4)



1+2=3

En la recursión múltiple, el número de llamadas no depende linealmente del

0+1=1

fib(4)

1+1=2

0

fib(2)

1

1

fib(3)

0+1=1

fib(0)

fib(1)

fib(1)

0

1

fib(2)

fib(0)

fib(1)


Nótese que algunos valores se computan más de una vez.

nes recursivas que hemos presentado:

— Simple. Una llamada recursiva en cada caso recursivo

Para terminar con la introducción, recapitulamos los distintos tipos de funcio-

— No final. Requiere combinación de resultados
— Final. No requiere combinación de resultados

— Múltiple. Más de una llamada recursiva en algún caso recursivo.



Diseño de algoritmos recursivos



9

2.2 Diseño de algoritmos recursivos

Dada la especificación { P } A { Q }, he