PDF de programación - Capítulo 4 - Diseño de algoritmos recursivos

Diseño de algoritmos recursivos1

Capítulo 4

Para entender la recursividad
primero hay que entender la recursividad

Anónimo

Resumen: En este tema se presenta el mecanismo de la recursividad como una
manera de diseñar algoritmos fiables y fáciles de entender. Se introducen distintas
técnicas para diseñar algoritmos recursivos, analizar su complejidad, modificarlos para
mejorar esta complejidad y verificar su corrección.

1.

Introducción

⋆

⋆

⋆

⋆

⋆

La recursión aparece de forma natural en programación, tanto en la definición de
tipos de datos (como veremos en temas posteriores) como en el diseño de algoritmos.

Hay lenguajes (funcionales y lógicos) en los que no hay iteración (no hay bucles),
sólo hay recursión. En C++ tenemos la opción de elegir entre iteración y recursión.

Optamos por una solución recursiva cuando sabemos cómo resolver de manera 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, ~x, para
distinguir los casos de solución directa y los casos de solución recursiva:

caso(s) directo(s): ~x es tal que el resultado ~y puede calcularse directamente de
forma sencilla.

caso(s) recursivo(s): sabemos cómo calcular a partir de ~x otros datos más pe-
queños ~x′, y sabemos además cómo calcular el resultado ~y para ~x suponiendo
conocido el resultado ~y ′ para ~x ′.

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

1Gonzalo Méndez es el autor principal de este tema.

49

50

⋆

⋆

⋆

Capítulo 4. Diseño de algoritmos recursivos

Intuitivamente, el subprograma se invoca a sí mismo con datos cada vez más simples
hasta que son tan simples que la solución es inmediata. Posteriormente, la solución
se puede ir elaborando hasta obtener la solución para los datos iniciales.

Tres elementos básicos en la recursión:

Autoinvocación: el proceso se llama a sí mismo.
Caso directo: el proceso de autoinvocación eventualmente alcanza una solución
directa (sin invocarse a sí mismo) al problema.
Combinación: los resultados de la llamada precedente son utilizados para obte-
ner una solución, posiblemente combinados con otros datos.

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 copias del mis-
mo 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:

{n ≥ 0}
fun factorial (int n) return int r
{r = n!}

int factorial ( int n )
{

int r;

if
else

( n == 0 ) r = 1;

// n > 0

r = n * factorial(n-1);

return r;

}

¿Cómo se ejecuta la llamada factorial(3)?

Figura 1: Ejecución de factorial(3)

¿Y qué ocurre en memoria?

Estructura de Datos y Algoritmos

1. Introducción

51

Figura 2: Llamadas recursivas de factorial(3)

Figura 3: Vuelta de las llamadas recursivas de factorial(3)

⋆

¿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 conceptualmente
la resolución de problemas y el diseño de algoritmos.

1.1. Recursión simple

⋆

Una acción recursiva tiene recursión simple (o lineal) si cada caso recursivo realiza
exactamente una llamada recursiva. Puede describirse mediante el esquema general:

Facultad de Informática - UCM

52

Capítulo 4. Diseño de algoritmos recursivos

void nombreProc ( τ1x1 , ... , τnxn , δ1 & y1 , ... , δm & ym )
{
// P : P r e c o n d i c i ó n
// d e c l a r a c i ó n de c o n s t a n t e s

τ1x′
δ1y′

1 ; ... ; τnx′
1 ; ... ; δmy′

n ; // ~x′ , p a r á m e t r o s de l a l l a m a d a r e c u r s i v a
m ; // ~y′ ,
r e s u l t a d o s de l a l l a m a d a r e c u r s i v a

if ( d(~x) )
~y = g(~x);

else if ( r(~x) )
{

// c a s o d i r e c t o

// s o l u c i ó n a l c a s o d i r e c t o

// c a s o no d i r e c t o

~x′ = s(~x);
nombreProc(~x′, ~y′);// l l a m a d a r e c u r s i v a
~y = c(~x, ~y′); // f u n c i ó n de c o m b i n a c i ó n : c o m p o s i c i ó n de s o l u c i ó n

// f u n c i ó n s u c e s o r : d e s c o m p o s i c i ó n de d a t o s

}

// Q: P o s t c o n d i c i ó n
}

donde:

~x representa a los parámetros de entrada x1, ... , xn, ~x′ a los parámetros de la
llamada recursiva x′
1, ... ,
y′
m, e ~y a los parámetros de salida y1, ... , ym
d(~x) es la condición que determina el caso directo

n, ~y′ a los resultados de la llamada recursiva y′

1, ... , x′

r(~x) 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
llamada recursiva ~y′ junto con los datos de entrada ~x, proporcionando así el
resultado ~y.

⋆

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

{n ≥ 0}
fun factorial (int n) return int r
{r = n!}

int factorial ( int n )
{

int r;

if ( n == 0 ) r = 1;
else

// n > 0

r = n * factorial(n-1);

return r;

}

d(n) = (n == 0)
g(n) = 1

Estructura de Datos y Algoritmos

1. Introducción

53

r(n) = (n > 0)
s(n) = n − 1
c(n, f act(s(n))) = n ∗ f act(s(n))

⋆

El esquema de recursión simple puede ampliarse considerando varios casos directos
y también varias descomposiciones para el caso recursivo. d(~x) y r(~x) pueden des-
doblarse en una alternativa con varios casos. Lo importante es que las alternativas
sean exhaustivas y excluyentes, y que en cada caso sólo se ejecute una llamada
recursiva.

⋆

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

{(a ≥ 0) ∧ (b ≥ 0)}
fun prod (int a, int b) return int r
{r = a ∗ b}

int prod ( int a, int b )
{

int r;

if

( b == 0 )

{r = 0;}

else if ( b == 1 )

{r = a;}

else if (b % 2 == 0)

// b > 1

{r = prod(2*a, b/2);}

else

// b > 1 && ( b % 2 == 1 )

{r = prod(2*a, b/2) + a;}

return r;

}

d1(a, b) = (b == 0)
g1(a, b) = 0
r1(a, b) = ((b > 1) && par(b))
s1(a, b) = (2 ∗ a, b/2)
c1(a, b, prod(s1(a, b))) = prod(s1(a, b))

d2(a, b) = (b == 1)
g2(a, b) = 1
r2(a, b) = ((b > 1) && impar(b))
s2(a, b) = (2 ∗ a, b/2)
c2(a, b, prod(s2(a, b))) = prod(s2(a, b)) + a

1.2. Recursión final

⋆

⋆

⋆

La recursión final o de cola (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
recursiva. 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 pueden ser
traducidos de manera directa a soluciones iterativas, más eficientes.

Facultad de Informática - UCM

54

Capítulo 4. Diseño de algoritmos recursivos

void nombreProcItr ( τ1x1 , . . . , τnxn , δ1 & y1 , . . . , δm & ym ) {
// P r e c o n d i c i ó n
// d e c l a r a c i ó n de c o n s t a n t e s

τ1x′

1 ; ... ; τnx′

n ; // ~x′

~x′ = ~x;
while ( r(~x′) )

~x′ = s(~x′);

~y = g(~x′);
}

// P o s t c o n d i c i ó n
}

⋆

Como ejemplo de función recursiva final veamos el algoritmo de cálculo del máximo
común divisor por el algoritmo de Euclides.

{(a > 0) ∧ (b > 0)}
fun mcd (int a, int b) return int r
{r = mcd(a, b)}

int mcd( int a, int b )
{

int m;

( a == b ) m = a;

if
else if ( a >
else

// a < b

b ) m = mcd(a-b, b);

m = mcd(a, b-a);

return m;

}

que se ajusta al esquema de recursión simple:

d(a, b) = (a == b)
r1(a, b) = (a > b)
s1(a, b) = (a − b, a) s2(a, b) = (a, b − a)

g(a, b) = a
r2(a, b) = (a < b)

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

Si traducimos esta versión recursiva a una iterativa del algoritmo obtenemos:

int itmcd( int a, int b )
{

int auxa =a; int auxb=b;
while (auxa!=auxb)

{

if (auxa>auxb)

{auxa = auxa-auxb;}

else

Estructura de Datos y Algoritmos

1. Introducción

55

{auxb = auxb-auxa;}

};

return auxa;

}

1.3. Recursión múltiple

⋆

Este tipo de recursión se caracteriza por que, al menos en un caso recursivo, se rea-
lizan varias llamadas recursivas. El esquema correspondiente es el siguiente:

void nombreProc ( τ1x1 , ... , τnxn , δ1 & y1 , ... , δm & ym ) {
// P r e c o n d i c i ó n
// d e c l a r a c i ó n de c o n s t a n t e s

τ1x11 ; ... ; τnx1n ; ... ; τ1xk1 ; ... ; τnxkn ;
δ1y11 ; ... ; δmy1m ; ... ; δ1yk1 ; ... ; δmykm ;

if ( d(~x) )

~y = g(~x);

else if ( r(~x) ) {

~x1 = s1( ~x );
nombreProc(~x1, ~y1);
...
~xk = sk( ~x );
nombreProc(~xk, ~yk);
~y = c(~x, ~y1, ... , ~yk);

}

// P o s t c o n d i c i ó n
}

donde

k > 1, indica el número de llamadas recursivas

~x representa los parámetros de entrada x1,..., xn, ~xi a los parámetros de la i-
ésima llamada recursiva xi1,..., xin, ~yi a los resultados de la i-ésima llamada
recursiva yi1,..., yim, para i = 1, ..., k, e ~y a los parámetros de salida y1,..., ym
d(~x) es la condición que determina el caso directo

r(~x) 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
para realizar la i-ésima llamada recursiva, para i = 1, ... , k

c, la función de combinación, obtiene la combinación de los resultados ~yi de
las llamadas recursivas, para i = 1, ... , k, junto con los datos de entrada ~x,
proporcionando así el resultado ~y.

⋆

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

{n ≥ 0}
fun fib (int n) return int r
{r = f ib(n)}

Facultad de Informática - UCM

56

Capítulo 4. Diseño de algoritmos recursivos

int fib( int n )
{

int r;

( n == 0 ) r = 0;
if
else if ( n == 1 ) r = 1;
else

//