Recursividad

_ _
Capítulo 2: Recursividad.
2.1.- Introducción.
La recursividad consiste en realizar una definición de un
concepto en términos del propio concepto que se está definiendo.

Ejemplos:
Solución de problemas recursivos:
•División sucesiva del problema original en uno o varios más
pequeños, del mismo tipo que el inicial.
•Se van resolviendo estos problemas más sencillos.
•Con lassoluciones de éstos se construyen las soluciones de los
problemas más complejos.
O lo que es lo mismo:
1.Un problema P se puede resolver conociendo la solución de
otro problema Q que es del mismo tipo que P, pero más
pequeño.

Ejemplos simples de recursividad.
A) Cálculo del factorial de un número, por ejemplo, 5.
5! = 5 * 4!
4! = 4 * 3!
3!= 3 * 2!
2! = 2 * 1!
DESCOMPOSICIÓN
DEL PROBLEMA
1!= 1 * 0!
SOLUCIÓN CONOCIDA O DIRECTA 0! = 1
1! = 1 * 0! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6 RESOLUCIÓN DE





Características de los problemas que pueden ser
resueltos de manera recursiva:
4.Los problemas pueden ser redefinidos en términos de uno o
más subproblemas, idénticos en naturaleza al problema
original, pero de alguna forma menores en tamaño.
5.Uno o más subproblemastienen solución directa o conocida,
no recursiva.
6.Aplicando la redefinición del problema en términos de
problemas más pequeños, dicho problema se reduce
sucesivamente a los subproblemas cuyas soluciones se
conocen directamente.
7.La solución a los problemas más simples se utiliza para
construir la solución al problema inicial.
_ _
Algoritmos recursivos:
diseño de la solución de un problemade manera recursiva
_
El algoritmo se llamará a sí mismo varias veces
¡Ojo al diseñar algoritmos recursivos!
pueden ser menos eficientes que que su solución iterativa
Algoritmo recursivo _ Implementación en un lenguaje de alto
nivel que permita recursividad (en nuestro caso, en Java).
_ _
2.2.- Diseño de módulos recursivos.
•Módulo M con una llamada a sí mismo: módulo recursivo
directo.•Módulo M con una llamada a otro F, que hace una llamada a
M: Módulo recursivo indirecto.
Ejemplo: Implementación del factorial de un número.
public long factorial (long n)
{
if (n == 0) return 1;
else return n * factorial(n-1);
}


Dos partes principales:
8.La llamada recursiva, que expresa el problema original en
términos de otro más pequeño, y
9.el valor para el cual se conoce unasolución no recursiva.
Esto es lo que se conoce como caso base: una instancia del
problema cuya solución no requiere de llamadas recursivas.
_ _
El caso base
10.Actúa como condición de finalización de la función
recursiva. Sin el caso base la rutina recursiva se llamaría
indefinidamente y no finalizaría nunca.
11.Es el cimiento sobre el cual se construirá la solución
completa alproblema.
Ejemplo: Traza del factorial de 5.
_
Búsqueda de soluciones recursivas: cuatro preguntas
básicas.
•[P1] ¿Cómo se puede definir el problema en términos de uno o
más problemas más pequeños del mismo tipo que el original?
•[P2] ¿Qué instancias del problema harán de caso base?
•[P3] Conforme el problema se reduce de tamaño ¿se alcanzará
el caso base?
•[P4] ¿Cómo se usa la solución delcaso base para construir una
solución correcta al problema original?
_
Ejemplo: la sucesión de Fibonacci.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
•El tercer término de la sucesión se obtiene sumando el segundo
y el primero. El cuarto, a partir de la suma del tercero y el
segundo.
•El problema: calcular el valor del n-ésimo término de la
solución, que se obtendrá sumando los términosn-1 y n-2.
Las respuestas a la preguntas anteriores serían:
•[P1] fibonacci(n) = fibonacci(n-1) + fibonacci(n-2).
•[P2] Casos bases: fibonacci(1) = 1 y fibonacci(2)=1.
•[P3] En cada llamada a la rutina fibonacci se reduce el tamaño
del problema en uno o en dos, por lo que siempre se alcanzará
uno de los dos casos bases.
•[P4] fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1.
Se...