Teoria 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 dicho número es0, 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 varios máspequeñ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 Q mediante la búsquedade 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 simples de 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 1! = 1 * 0! = 1 2! = 2 * 1! = 2 3! = 3 * 2! = 6 4! = 4 * 3! = 24 5! = 5 * 4! = 120 RESOLUCIÓN DE PROBLEMAS MÁS COMPLEJOS A PARTIR DE OTROS MÁS SIMPLES

SOLUCIÓN CONOCIDA O DIRECTA

B) Búsqueda de una palabra en un diccionario.

Características de losproblemas 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 en términos de problemas más pequeños, dicho problema sereduce 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ñar algoritmos recursivos!

pueden ser menos eficientes que quesu 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. publiclong 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 del problema cuya solución no requiere de llamadas recursivas.

El caso base10.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 preguntas básicas.

•[P1] ¿Cómo se puede definir el problema en términos de uno o más...