Recursividad JAVA

TEMA 1
Recursividad

Recursividad
T
E
M
A
1

CONTENIDO DEL TEMA
1.- Introducción.
2.- Verificación de funciones y procedimientos recursivos
3.- Escritura de programas recursivos
4.-Ejemplos.
5.- ¿Recursión o iteración?
6.- Depuración
7.- Ejemplos
8.- Asignación estática y dinámica de memoria.

Introducción
• Definición de Recursividad: Técnica de programación muy
potenteque puede ser usada en lugar de la iteración.
• Ambito de Aplicación:
– General
– Problemas cuya solución se puede hallar solucionando el mismo problema
pero con un caso de menor tamaño.

•Razones de uso:
– Problemas “casi” irresolubles con las estructuras iterativas.
– Soluciones elegantes.
– Soluciones más simples.

• Condición necesaria : ASIGNACIÓN DINÁMICA DE MEMORIAIntroducción
• ¿En qué consiste la recursividad?
– En el cuerpo de sentencias del subalgoritmo se invoca al propio
subalgoritmo para resolver “una versión más pequeña” del problema
original.
– Habrá un caso(o varios) tan simple que pueda resolverse directamente
sin necesidad de hacer otra llamada recursiva.

•

Aspecto de un subalgoritmo recursivo.
ALGORITMO Recursivo(...)
INICIO
...Recursivo(...);
...
FIN

Introducción
• Ejemplo: Factorial de un natural.

1

si n == 0

Factorial(n)=
n*Factorial(n-1) si n > 0

Introducción
• Ejemplo: Factorial de un natural.
ALGORITMO NFactorial(E n:N)
VAR
N fact
INICIO
SI n == 0 ENTONCES fact = 1
SINO fact = n*Factorial(n-1)
FINSI
DEVOLVER fact
FIN

Introducción
• ¿Cómo funciona la recursividad?
4!=4*3!

Introducción• 3!=3*2!

Introducción
•2!=2*1!

Introducción
• 1!=1*0!=1*1

Introducción

Verificación de funciones y
procedimientos recursivos
Método de las tres preguntas
• La pregunta Caso-Base:¿Existe una salida no recursiva o
caso base del subalgoritmo? Además, ¿el subalgoritmo
funciona correctamente para ella?
• La pregunta Más-pequeño : ¿Cada llamada recursiva se
refiere a un caso...