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:

•Los números naturales se pueden definir de la siguiente forma:
0 es un Número natural y el sucesor de un número natural
es también un número natural.
•El factorial de un número natural n, es 1 si dichonúmero es 0,
o n multiplicado por el factorial del número n-1, en caso
contrario.
•La n-ésima potencia de un número x, es 1 si n es igual a 0, o el
producto de x por la potencia (n-1)-ésima de x, cuando n es
mayor que 0.

En todos estos ejemplos se utiliza el concepto definido en la
propia definición.

Solución de problemas recursivos:
•División sucesiva del problema original en uno o variosmás
pequeños, del mismo tipo que el inicial.
•Se van resolviendo estos problemas más sencillos.
•Con las soluciones 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.
2.Igualmente, supongamos que pudiéramos resolver Qmediante la búsqueda de la solución de otro nuevo
problema, R, que sigue siendo del mismo tipo que Q y P,
pero de un tamaño menor que ambos.
3.Si el problema R fuera tan simple que su solución es obvia o
directa, entonces, dado que sabemos la solución de R,
procederíamos a resolver Q y, una vez resuelto, finalmente
se obtendría la solución definitiva al primer problema, P.

Ejemplos simplesde recursividad.
A) Cálculo del factorial de un número, por ejemplo, 5.
5! = 5 * 4!
4! = 4 * 3!
3!= 3 * 2!
DESCOMPOSICIÓN
DEL PROBLEMA

2! = 2 * 1!
1! = 1 * 0!
0! = 1

SOLUCIÓN CONOCIDA O DIRECTA

1! = 1 * 0! = 1
2! = 2 * 1! = 2
3! = 3 * 2! = 6
4! = 4 * 3! = 24

RESOLUCIÓN DE
PROBLEMAS MÁS
COMPLEJOS A PARTIR
DE OTROS MÁS
SIMPLES

5! = 5 * 4! = 120

B) Búsqueda de unapalabra en un diccionario.

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 subproblemas tienen solución directa o conocida,
no recursiva.

6.Aplicando la redefinición del problema enté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 problema de manera recursiva

El algoritmo se llamará a sí mismo varias veces

¡Ojo al diseñaralgoritmos 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 recursivoindirecto.

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 una solución no recursiva.
Esto es lo que se conoce como caso base: una instancia delproblema 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 al problema.
Ejemplo: Traza del factorial de 5.

Búsqueda de soluciones recursivas: cuatro...