Recursividad

RECURSIVIDAD
ESTRUCTURAS DE DATOS
2006

Prof. Ing. M.Sc. Fulbia Torres

UNIDAD II
ESTRUCTURAS DE DATOS
RECURSIVIDAD
Definición.
Estado base.
Estado general.
Ejemplos.
Ejercicios.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
DEFINICIÓN

Es una técnica de programación muy potente que permite definir un objeto
(problemas,(problemas, estructuras de datos) en términos de si mismo.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
DEFINICIÓN
Ejemplo:
Un subprograma que se llame a si mismo se dice que es recursivo.
En estos se dan de dos maneras:
DIRECTO: El subprograma se llama directamente a si mismo.
Subprograma P
Instrucción 1
Instrucción 2
Instrucción 3Llamada a P

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
DEFINICIÓN
INDIRECTA: El subprograma llama a otro subprograma y éste a su
vez llama al primero.

Subprograma P
Llamada a Q

Subprograma Q
Llamada a V

Subprograma V
Se ejecuta termina

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

En todadefinición recursiva de un problema se
debe establecer lo siguiente:

Estado Base: un estado en el cual la solución no se presenta de
manera recursiva sino directamente. Además la entrada (datos) del
problema debe ir acercándose al estado básico. Este estado se
denomina salida de la recursión, y es necesario que exista por lo
menos una dentro de cada rutina recursiva, para garantizar que elproceso termina.
Estado General: llamada recursiva, y también es necesaria la
presencia de al menos uno de éstos en toda rutina recursiva.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
Metodología de desarrollo
Buscar las salidas de la recursión: en que casos o bajo qué
circustancias se puede dar una respuesta inmediata al problema
planteado.Determinar los avances de la recursión: en que casos se debe
plantear la respuesta en términos de una llamada recursiva. Para esto
es conveniente:
Identificar los casos posibles,
Definir que significa un problema con la misma estructura pero menor
tamaño y plantear la llamada recursiva, y
Explicar en cada caso la manera de construir la respuesta a partir del
retorno de dicha llamada.Escribir el algoritmo que implementa el planteamiento antes logrado.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
EJEMPLO

El factorial de un número entero positivo n se define como el producto
de los números comprendidos entre 1 y n, la expresión n! simboliza el
factorial de n. Escribir una función recursiva para encontrar el factorial
de unnúmero n. Hacer el análisis y el planteamiento del problema.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
EJEMPLO

0! = 1
1! = 1
2! = 2 * 1
31 = 3 * 2 * 1
4! = 4 * 3 * 2 * 1
.
.
n! = n(n – 1)!

4! = 4(4 – 1) = 4 * 3!
3! = 3(3 – 1) = 3 * 2!
2! = 2(2 – 1) = 2 * 1!
1! = 1
llamadas recursivas
2! = 2 * 1! = 2 * 1 = 2
3! = 3 * 2! =3 * 2 = 6
4! = 4 * 3! = 4 * 6 = 24

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
EJEMPLO

Análisis:
Entradas: entero n.
Salidas: factorial de n.
Planteamiento:
1

si n=0 o n=1

Estado Base

Fact (n)
n * Fact(n – 1)

si n > 1

Estado General

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006RECURSIVIDAD
EJEMPLO

int Fact ( int n )
{
If (n == 0 || n == 1) return 1;
else return (n * Fact(n – 1));
}

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

RECURSIVIDAD
EJEMPLO

Gráficamente:
Fact (4) = 24
4 * Fact(3) = 24
6
3 * Fact(2) = 6
2
2 * Fact(1) = 2
1
1 * Fact (0) = 1
11

4*6
3*2
2*1
1*1
Ing. M.Sc. Fulbia Torres
Asignatura:...