Lienciado

Módulo 4
Unidad 4
Lectura 4

Materia: Taller de Algoritmos y Estructura de Datos I
Profesor: Marcelo Bianchi

4.1 Concepto de Recursión
Frases introductorias
“Un método parcialmente definido en términos de sí mismo recibe el
nombre de recursivo”. (M.A. Weiss, Estructuras de Datos en Java-, 2000,
pag. 167)
La recursión es un concepto que trata de explicar el funcionamiento interno
dememoria de las computadoras que se da cuando se usa un método
recursivo, es por ello que Weiss dice simplemente que “la recursión consiste
en el uso de métodos recursivos. Es una herramienta potente para producir
algoritmos cortos y eficientes”.

Recursión
Un método es recursivo
cuando directa o
indirectamente hace una
llamada a sí mismo

Recuerde que para que un método sea recursivodebe cumplir cuatro
condiciones básicas y que se da la recursión cuando de forma directa o
indirecta hace una llamada a sí mismo, es por ello que requiere de un corte
de control para que no quede en un bucle infinito.
Por cada llamada a sí mismo crea un nuevo hilo de ejecución utilizando un
nuevo lugar en memoria.
La recursión es una herramienta muy potente de resolución de problemas,
perohay que saber cuándo utilizarlos. Muchos algoritmos se pueden
expresar de forma sencilla usando una formulación recursiva, esto sucede
por ejemplo con las estructuras de datos avanzadas dinámicas árbol y grafo,
donde es necesario aplicar algoritmos recursivos en las operaciones.

Recursión Básica
Una de las características importantes de las
estructuras de datos es la reutilización.Recursión
No se debe crear una
lógica circular que lleve a
bucles infinitos.

Abstracción
VENTAJA
Independizar el diseño del programa de la
implementación especifica de los datos

Taller de Algoritmos y Estructuras de Datos I – Marcelo Bianchi | 2

Fundamentos de la Recursión
INDUCCIÓN
Técnica usada para demostrar teoremas que
cumplen los enteros positivos
Repasemos las cuatro reglasbásicas de la recursividad


Caso Base: se puede demostrar directamente. Es necesario que se
establezca cuál es el caso base que se utilizará como corte de control de
la recursión.



Caso General: se demuestra que si el teorema es cierto para
determinados casos, se puede extender para incluir el siguiente caso. El
caso general es siempre una fórmula que representa cualquier término
deuna serie o sucesión numérica, la que utilizaremos en la condición de
llamada a sí mismo.
Ejemplo: Si es cierto para N = k, debe ser cierto para N = k + 1.

 Puede Creerlo: Siempre tiene que asumir que la recursividad
funciona correctamente en memoria y resolverá todos los algoritmos
que quedaron pendientes para salir por el caso base.

 Regla de interés compuesto: nunca duplique trabajoresolviendo la misma instancia de un problema en llamadas recursivas
separadas. El algoritmo siempre debe ser sencilla.
Debe recordar estas cuatro reglas básicas cuando diseñe algoritmos
recursivos.

Algunas funciones matemáticas se definen recursivamente.


S(N) //denota la suma de los primeros N enteros.



S(1) = 1 //caso base



S(N) = S (N-1) + N //caso general
El códigoque lo resuelve es el siguiente:
public class recursionBasica {
public static long s( int n ) {
if( n==1 ) // caso base
return 1;
else // caso general
return s( n-1 ) + n;
}
}
Taller de Algoritmos y Estructuras de Datos I – Marcelo Bianchi | 3

La recursión siempre se puede implementar usando una pila, recuerde
que cada instancia de programa se ubica en un lugar distinto. El valor
deN inicial es siempre mayor o igual al del caso base y el nuevo valor
de cada llamada se acerca al del caso base.

La ejecución del programa comienza con el primer valor de
N = 4, con cada llamada N disminuye en 1, hasta llegar a
N = 1 completando todos los cálculos pendientes.

Problemas de la Recursión


Cada llamada recursiva genera una nueva instancia en la pila
del sistema....