Estructura



Un objeto es recursivo si su definición requiere la
definición previa del objeto en un caso más
sencillo.



Una función es recursiva si su resolución requiere
la solución previa de lafunción para casos más
sencillos.

ESTRUCTURA DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

1



Recursividad: técnica con la que un problema se
resuelve sustituyéndolo por otro problemade la
misma forma pero más simple.

Ejemplo: Definición del factorial para n >=0
0! = 1
n! = n * (n-1)! Si n>0

ESTRUCTURA DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

2



Es unaherramienta muy potente, útil y sencilla.



Ciertos problemas se adaptan de forma natural a
soluciones recursivas.



La implementación de estos algoritmos se realiza
generalmente enconjunto con una estructura de datos,
la pila, en la cual se van almacenando los resultados
parciales de cada recursión.

ESTRUCTURA DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

3

Segúndesde dónde se haga la llamada recursiva:




Recursividad directa.la función se llama a sí misma.
Recursividad indirecta.la función A llama la función B, y ésta
llama a A.

ESTRUCTURA DE DATOSM.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

4

Según el número de llamadas
generadas en tiempo de ejecución:




recursivas

Función recursiva lineal o simple.se genera una única llamadainterna.
Función recursiva no lineal o múltiple.se generan dos o más llamadas internas.

ESTRUCTURA DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

5

Según el punto dónde se realice lallamada recursiva,
las funciones recursivas pueden ser:




Final (Trail recursion).La
llamada
recursiva
es
la
instrucción que se produce dentro
función.

última
de la

No Final (Nontrailrecursive function).se hace alguna operación al volver de la
llamada
recursiva.

ESTRUCTURA DE DATOS

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

6



Las funciones recursivas suelen ser más...