algoritmos recursivos

Capítulo 4

Diseño de algoritmos recursivos1

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 estacomplejidad 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 yrecursió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, ⃗ , para
x
distinguir los casos desolución directa y los casos de solución recursiva:
caso(s) directo(s): ⃗ es tal que el resultado ⃗ puede calcularse directamente de
x
y
forma sencilla.
caso(s) recursivo(s): sabemos cómo calcular a partir de ⃗ otros datos más pex
queños ⃗ ′ , y sabemos además cómo calcular el resultado ⃗ para ⃗ suponiendo
x
y
x
conocido el resultado ⃗ ′ para ⃗ ′ .
y
x
Para implementar solucionesrecursivas 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.

⋆

1

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

41

42

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 tansimples 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 lallamada precedente son utilizados para obtener 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 mismo código, operando sobre datos diferentes (en realidad sólo se copian las variables
locales y los parámetros por valor). Elejemplo clásico del factorial:
{n ≥ 0}
fun factorial (int n) return int r
{r = n!}
int factorial ( int n )
{
int r;
if
( n == 0 ) r = 1;
else if
( 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

43

Figura 2: Llamadasrecursivas 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 (olineal) si cada caso recursivo realiza
exactamente una llamada recursiva. Puede describirse mediante el esquema general:
Facultad de Informática - UCM

44

Capítulo 4. Diseño de algoritmos recursivos

void nombreProc ( τ1 x1 , ... , τn xn , δ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
τ1 x′ ; ... ; τn x′ ; // ⃗ ′ , p a r á m e...