Recursividad

Estructuras de Dato

Recursividad

1

Ejemplo Matrushka


La Matrushka es una artesanía tradicional rusa.
Es una muñeca de madera que contiene otra
muñeca más pequeña dentro de sí. Esta
muñeca, también contiene otra muñeca dentro.
Y así, una dentro de otra.

2

¿Qué es la recursividad?





La recursividad es un concepto fundamental en
matemáticas y en computación.Es una alternativa diferente para implementar
estructuras de repetición (ciclos). Los módulos
se hacen llamadas recursivas.
Se puede usar en toda situación en la cual la
solución pueda ser expresada como una
secuencia
de
movimientos,
pasos
o
transformaciones gobernadas por un conjunto de
reglas no ambiguas.
3

Función recursiva
Las funciones recursivas se componen de:
 Caso base:una solución simple para un caso
particular (puede haber más de un caso
base). La secuenciación, iteración
condicional y selección son estructuras
válidas de control que pueden ser
consideradas como enunciados.
NOTA: Regla recursiva Las estructuras de control que se pueden
formar combinando de manera válida la secuenciación,
iteración condicional y selección también son válidos.
4Función recursiva


Caso recursivo: una solución que involucra
volver a utilizar la función original, con
parámetros que se acercan más al caso
base. Los pasos que sigue el caso
recursivo son los siguientes:
1.
2.

3.

El procedimiento se llama a sí mismo
El problema se resuelve, resolviendo el
mismo problema pero de tamaño menor
La manera en la cual el tamaño del
problemadisminuye asegura que el caso
base eventualmente se alcanzará
5

Función recursiva

=

+

6

Ejemplo: factorial
Escribe un programa que calcule el factorial (!)
de un entero no negativo. He aquí algunos
ejemplos de factoriales:







0! = 1
1! = 1
2! = 2
 2! = 2 * 1!
3! = 6  3! = 3 * 2!
4! = 24
 4! = 4 * 3!
5! = 120
 5! = 5 * 4!
7

Ejemplo: factorial(iterativo)
int factorial (int n)
comienza

public int factorial (int n) {
int fact = 1;

fact  1

for (int i = 1; i 0 (recursión)

N! =

Un razonamiento recursivo tiene dos partes: la base y la
regla recursiva de construcción. La base no es recursiva y
es el punto tanto de partida como de terminación de la
definición.
12

Solución Recursiva
Dado un entero no negativo x, regresarel factorial de x fact:
Entrada n entero no nogativo,
Salida:entero.
int fact (int n)
{
if (n == 0)
return 1;
else
return fact(n – 1) * n ;
}

Es importante
determinar un caso
base, es decir un punto
en el cual existe una
condición por la cual no
se requiera volver a
llamar a la misma
función.

13

¿Cómo funciona la recursividad?
Llamadas recursivas

Resultados de lasllamadas recursivas

14

¿Por qué escribir programas recursivos?
Son mas cercanos a la descripción
matemática.
 Generalmente mas fáciles de analizar
 Se adaptan mejor a las estructuras de
datos recursivas.
 Los algoritmos recursivos ofrecen
soluciones estructuradas, modulares y
elegantemente simples.


15

¿Cómo escribir una función en forma
recursiva?
(){
[declaración devariables]
[condición de salida]
[instrucciones]
[llamada a ()]
return
}
16

Ejercicio
Considere la siguiente ecuación recurrente:
 
an = an-1 + 2n
a0 = 1
Escribe el algoritmo de la solución.
17

¿Cuándo usar recursividad?



Para simplificar el código.
Cuando la estructura de datos es recursiva
ejemplo : árboles.

¿Cuándo no usar recursividad?





Cuando losmétodos usen arreglos largos.
Cuando el método cambia de manera
impredecible de campos.
Cuando las iteraciones sean la mejor opción.
18

Algunas Definiciones.


Cuando un procedimiento incluye una
llamada a sí mismo se conoce como
recursión directa.

19

Algunas Definiciones.


Cuando un procedimiento llama a otro
procedimiento y éste causa que el procedimiento
original...