MATERIA:
ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
2. RECURSIVIDAD
2.1 DEFINICIÓN
RECURSIVIDAD
La recursividad (recursión) es aquella
propiedad que posee un método por lo
cual puede llamarse a sí mismo.
La recursividad es una alternativa a la
iteración, aunque menos eficiente en
términos de tiempo de computadoras que una
solución iterativa (invocaciones
suplementarias a los métodos); sin embargo,
en muchas circunstancias, el uso de la
recursividad permite a los programadores
especificar soluciones naturales,
sencillas, que serían, en caso contrario,
difíciles de resolver. La recursión es una
herramienta poderosa e importante en la resolución de problemas y en la
programación.
La recursividad es un tópico importante en la resolución de algoritmos y
estructuras de datos.
En matemáticas existen numerosas funciones que tienen carácter recursivo;
de igual modo, numerosas circunstancias y situaciones de la vida ordinaria tienen
carácter recursivo. Por ejemplo, en la búsqueda en páginas web, puede ocurrir
que aparezcan direcciones (enlaces) que lleven a otras páginas y estas, a su vez,
a otras nuevas y así hasta completar todo lo relativo a la búsqueda inicial.
1
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
2
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
2.2 PROCEDIMIENTOS O MÉTODOS RECURSIVOS
Un método recursivo es un método que se invoca a sí mismo de forma directa o
indirecta. En recursión directa, el código del método A( ) contiene una sentencia
que invoca a A( ),
mientras que en recursión indirecta, el método A() invoca a un método B( ) que a
su vez invoca al método C( ), y así sucesivamente hasta que se invoca de nuevo
al método A( ).
Un requisito para que un algoritmo
recursivo sea correcto es que no genere una
secuencia infinita de llamadas sobre sí mismo.
Cualquier algoritmo que genere una secuencia de
este tipo no puede terminar nunca. En consecuencia
la definición recursiva debe incluir una condición
de salida, que se denomina componente base, en el
3
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
que f(n) se defina directamente (es decir, no recursivamente) para uno o más
valores de n.
Debe existir una “forma de salir” de la secuencia de llamadas recursivas.
Para mostrar el funcionamiento de la recursividad vemos unos ejemplos sencillos.
Suponga se desea realizar la suma de los primeros 5 numeros enteros positivos;
para ello diseñaremos un método denominado sumar para realizar esta función.
EJEMPLO 1. Cálculo de la Suma del número 5.
Sumar (n) , donde n=5;
1+ 2 + 3 + 4 + 5
5+ 4 + 3 + 2 + 1
Suma (5) = 5 + Suma(4)
4 + Suma(3)
3 + Suma(2)
2 + Suma(1)
Caso base Suma( 1) = 1
2 + 1 =Suma(2)
3 + 3 = Suma(3)
4 + 6 = Suma(4)
15= 5 + 10 = Suma(5)
4
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
La condición de salida o componente base es Suma (n) = 1 para n = 1.
Así, en el algoritmo que calcula la suma de los n primeros enteros:
1 n=1
Suma(n) =
n + S(n-1) n>1
Así el código es el siguiente:
public long Suma (long n) {
if (n == 1) return 1;
else
{
return n +Suma(n-1);
}}
Un método recursivo correcto debe incluir un componente base o condición
de salida ya que, en caso contrario, se produce una recursión infinita.
Un método es recursivo si se llama a sí mismo, directamente o bien
indirectamente a través de otro método g( ). Es necesario contemplar un caso
base que determina la salida de las llamadas recursivas.
Recursividad indirecta: métodos mutuamente recursivos
La recursividad indirecta se produce cuando un método llama a otro, que
eventualmente terminara llamando de nuevo al primer método.
Condición de terminación de la recursión
Cuando se implementa un método recursivo, es preciso considerar una condición
de terminación ya que, en caso contrario, continuaría indefinidamente llamándose
a sí mismo y llegaría un momento en que la pila que registra las llamadas se
desbordaría. En consecuencia, en cualquier método recursivo se necesita
establecer la condición de parada de las llamadas y evitar indefinidas repeticiones.
Por ejemplo, en el caso del método factorial, la condición de parada ocurre cuando
n es 1 o 0, ya que en ambos casos el factorial es 1. Es importante que cada
5
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
llamada suponga un acercamiento a la condición de parada, porque en el método
factorial cada llamada supone un decremento del entero n lo que supone estar
más cerca de la condición de salida, donde n = 1.
EJEMPLO 2. Calculo del factorial del número 5.
5! = 5 * 4!
4! = 4 * 3!
3!= 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
Caso base 0! = 1
1! = 1 * 0! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24
5! = 5 * 4! = 120
Código del método correspondiente al factorial de un número.
public long factorial (long n)
{
if (n == 0) return 1;
else
{
return n * factorial(n-1);
}
En un algoritmo recursivo, se define como caso base aquel resuelto directamente
con sentencias elementales. El caso base se ejecuta cuando se alcanza la
condición de parada de llamadas recursivas. Para que funcione la recursión el
progreso de las llamadas debe tender a la condición de parada.
2.3 EJEMPLOS DE CASOS RECURSIVOS
Una de las técnicas más importantes para la resolución de muchos problemas de
computadora es la denominada divide y vencerás. El diseño de algoritmos
basados en esta técnica consiste en transformar (dividir) un problema de tamaño n
en problemas más pequeños, de tamaño menor que n, pero similares al problema
original, de modo que resolviendo los subproblemas y combinando las soluciones
se pueda construir fácilmente una solución del problema completo (vencerás).
Normalmente, el proceso de división de un problema en otros de tamaño menor va
a dar lugar a que se llegue el caso base, cuya solución es inmediata. A partir de la
6
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
obtención de la solución del problema para el caso base, se combinan soluciones
que amplían el tamaño del problema resuelto, hasta que el problema original
queda también resuelto.
Por ejemplo, se plantea el problema de dibujar un segmento que está conectado
por los puntos en el plano (x1, y1) y (x2, y2). El problema puede descomponerse
así: determinar el punto medio del segmento, dibujar dicho punto y dibujar los dos
segmentos mitad obtenidos al dividir el segmento original por el punto mitad. El
tamaño del problema se ha reducido a la mitad, el hecho de dibujar un segmento
se ha transformado en dibujar dos segmentos con un tamaño de justamente la
mitad. Sobre cada segmento mitad se vuelve aplicar el mismo procedimiento, de
tal forma que llega un momento en que, a base de dividir el segmento, se alcanza
uno de longitud cercana a cero (caso base) y se dibuja un punto. Cada tarea
realiza las mismas acciones, por lo que se puede plantear con llamadas recursivas
al proceso de dibujar el segmento cada vez con un tamaño menor, exactamente a
la mitad.
Un Algoritmo divide y vencerás consta de dos partes.
• La primera, divide recursivamente el problema original en subproblemas cada
vez más pequeños.
• La segunda, soluciona (vencerás) el problema dando respuesta a los
subproblemas. Desde el caso base se empieza a combinar soluciones de
subproblemas hasta que queda resuelto el problema completo.
Problemas clásicos resueltos mediante recursividad son las torres de Hanoi, el
método de búsqueda binaria, la ordenación rápida, la ordenación por mezclas, etc.
Torres de Hanói
Este juego (un algoritmo clásico) tiene sus orígenes en la cultura oriental y en una
leyenda sobre el Templo de Brahma, cuya estructura simulaba una plataforma
metálica con tres varillas y discos en su interior. El problema en cuestión suponía
la existencia de 3 varillas (A, B y C) o postes en los que se alojaban discos (n
discos) que se podían trasladar de una varilla a otra libremente, pero con una
condición: cada disco era ligeramente inferior en diámetro al que estaba justo
debajo de él.
7
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
Varilla A Varilla B Varilla C
Se ilustra el problema con tres varilla con seis discos en la varilla A, y se desea
trasladar a la varilla C conservando la condición de que cada disco sea
ligeramente inferior en diámetro al que tiene situado debajo de él. Por ejemplo, se
pueden cambiar cinco discos de golpe de la varilla A a la varilla B, y el disco más
grande a la varilla C. ya ha habido una transformación del problema en otro de
menor tamaño, se ha divido el problema original.
Varilla A Varilla B Varilla C
Ahora el problema se centra en pasar los cinco discos de la varilla B a la varilla C.
se utiliza un método similar al anterior, parar los cuatro discos superiores de la
varilla B a la varilla A y, a continuación, se para el disco de mayor tamaño de la
varilla B a la varilla C, y así sucesivamente. El proceso continua del mismo modo,
siempre dividiendo el problema en dos de menor tamaño hasta que finalmente se
queda un disco en la varilla B, que es el caso base y, a su vez, la condición de
parada.
8
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
La solución del problema es claramente recursiva. Además, con las dos partes
mencionadas anteriormente: división recursiva y solución a partir del caso base.
Varilla A Varilla B Varilla C
Búsqueda binaria
La búsqueda binaria es un método de localización de una clave especificada
dentro de una lista o array ordenado de n elementos que realiza una exploración
de la lista hasta que se encuentra o se decide que no se está en la lista. El
algoritmo de búsqueda binaria se puede describir recursivamente aplicando la
técnica divide y vencerás.
Se tiene una lista ordenada a[ ] con un límite inferior y un límite superior. Dada una
clave, comienza la búsqueda en la posición central de la lista (índice central).
inferior central superior
central = (inferior + superior) /2
Comparar a [central] y clave.
Si hay coincidencia, se tiene la condición de terminación que permite detener la
búsqueda y devolver el índice central. En caso contrario dado que la lista esta
ordenada, se centra la búsqueda en la “sublista inferior” o en la “sublista superior”
(a la derecha de la posición central). El problema de la búsqueda se ha dividido en
la mitad, el tamaño de la lista donde buscar es la mitad de tamaño anterior. El
tamaño de la lista se reduce cada vez a la mitad, así hasta que se encuentre el
elemento, o bien la lista resultante este vacía.
9
INGENIERÍA EN INFORMÁTICA 2020
MATERIA: ESTRUCTURA DE DATOS
UNIDAD 2: RECURSIVIDAD
AUTORA: MSC. [Link] CARREÓN ROMERO
1. Si clave < a [central], el valor buscado solo puede estar en la mitad
izquierda de la lista con elementos en el rango, [inferior,central–1].
clave
inferior central superior
Búsqueda en sublista izquierda [inferior, central–1].
2. Si clave > a[central], el valor buscado solo puede estar en la mitad superior
de la lista con elementos en el rango de índices, [central+1, superior].
clave
inferior central superior
3. La búsqueda continúa en sublistas más y más pequeñas, exactamente a la
mitad, con dos llamadas recursivas: una se corresponde con la sublista
inferior y la otra, con la sublista superior. El algoritmo termina con éxito
(aparece la clave buscada) o sin éxito (no aparece la clave buscada)
situación que ocurrirá cuando el límite superior de la lista sea más pequeño
que el límite inferior. La condición inferior > superior es la condición de
salida o terminación sin éxito, y el algoritmo devuelve el índice – 1.
busquedaBR(doublé a[ ], doublé clave, int inferior, int superior)
{
int central;
if (inferior -- superior) // no encontrado
return -1;
else
{
central = (inferior + superior) /2;
if (a[central] == clave)
return central;
else if (a[central] - clave)
return busquedaBR(a, clave, central+1, superior);
else
return busquedaBR(a, clave, inferior, central-1);
}}
10
INGENIERÍA EN INFORMÁTICA 2020
