Recursividad

Introducción. En java un m´etodo recursivo lleva a cabo alguna tareautilizando llamados al mismo m´etodo se “utiliza a s´ı mismo” para completar una tarea. El uso de par´ametros es fundamental para implementar un metodo recursivo Permiten distinguir el caso base y el paso de recursividad. De esta forma repetiremos llamados a un mismo metodo con distintos parametros hasta encontrar alg´un casobase.Por esta razon, la recursividad se utiliza como una alternativa para la iteracion. Para implementar un m´etodo recursivo es necesario establecer uno o mas casos base, cuya solucion es expedita, sin mayor procesamiento. En estos casos es que la recursividad se detendr´a y no se har´an m´as llamados al metodo. Asimismo, es necesario definir la forma en que los problemas mas complejos puedenresolverse en terminos de un problema mas simple, es decir, el paso de recursividad. Por lo general, los m´etodos recursivos van a tener la siguiente forma: Ejemplo if (caso-base) resuelvalo else { redefina el problema utilizando recursividad y la solucion de un problema mas simple } Euclides La recursividad consiste en realizar una definición de un concepto en términos del propio concepto que se estádefiniendo. 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 elproblema original en términos de otro más pequeño

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 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.

A veces es más fácil definir funciones de manera inductiva • Lo mismo se puede aplicar a funciones no matemáticas • Recursiva: se llama a sí misma para resolver el problema Claves para utilizar la recursividad • La recursividad es una alternativa para el desarrollo de programasrepetitivos (otra alternativa son las sentencias iterativas). • En Java se pueden desarrollar programas recursivos • En un programa recursivo debe existir al menos un caso no recursivo Caso no recursivo (caso básico) • Aquellos que obtienen un resultado sin llamadas recursivas Un programa recursivo sin casos básicos nunca finalizaría Los casos recursivos debe aproximarse a los casos básicos, esdecir, el programa debe tender hacia las condiciones de finalización Pasos para el diseño de programas recursivos

1. Especificación / parametrización 2. Análisis delos casos básicos (no recursivos) 3. Análisis de los casos recursivos (generales) 4. Análisis de la finalización 5. Diseño del algoritmo 6. Implementación

Especificación / Parametrización 1. Determinar las carácterísticas del programaa implementas(precondiciones, postcondiciones) 2. Determinar los parámetros (entrada y salida) , incluídos los tipos teniendo en cuenta que la llamada recursiva se realizará en función de dichos parámetros. 3.Determinar las condiciones y restricciones que deben cumplir los parámetros 4.Definir la llamada inicial (Sobre todo si es importante el valor inicial de alguno de los parámetros para elcorrecto funcionamiento). Análisis de los casos básicos 1. Determina cuáles son los casos básicos (no recursivos). (¡Como mínimo un caso básico!) 2. Para cada caso básico, especifica las acciones a realizar y los resultados a Devolver Análisis de los casos generales 1. Determina cuáles son los casos generales: ¿Para qué valores de los parámetros hay que realizar llamadas recursivas? 2. Tratamiento...