sismos

Análisis de algoritmos

Recursividad
1

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í. Ésta muñeca,también contiene otra muñeca dentro. Y así, una
dentro de otra.

2

Recursividad: el concepto
• La recursividad es un concepto fundamental en
matemáticas y en computación.
• Es una alternativadiferente 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 unasecuencia 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ónsimple para un caso
particular (puede haber más de un caso base).

4

Función recursiva
•

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

1. El procedimiento se llama a sí mismo
2. El problema se resuelve, tratando el mismo
problema pero detamaño menor
3. La manera en la cual el tamaño del problema
disminuye asegura que el caso base
eventualmente se alcanzará
5

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

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

Ejemplo:factorial (iterativo - repetetitivo)
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 recursivotiene 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.

10

Solución Recursiva
Dado un...