Algoritmos

Para las actividades de control de la semana, responderemos las siguientes preguntas:

1.- Definir con sus propias palabras que es un Algoritmo recursivo y que tipos de recursión que existen.

Podemos decir, un algoritmo recursivo es un algoritmo que se explica en términos de sí mismo, estos son implementados en forma de subrutinas (procedimientos, subprogramas, etc) de talforma que dentro de una subrutina recursiva hay una o más llamadas a sí misma lo que lo hace ser diferente a los demás en su clase.

Por lo general, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecuciónrecurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N. De esta forma, al ir reduciendo progresivamente la complejidad del problema queresolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos anteun caso base de la recursividad.

Las claves para construir un subprograma recurrente son:

Cada llamada recurrente se debería definir sobre un problema de menor complejidad

ha de existir al menos uncaso base para evitar que la recurrencia sea infinita.

Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.Partes

1.- Condición a evaluar según la aproximación al límite establecido.

2.- Llamada al método recursivo si la condición no se cumple.

Así, la definición de la función consta de la recursiva que se llama a sí misma, y la condición para detenerse.

Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse al programa.

En un computador, esta serie de pasos recursivos debe ser finita, terminando con un paso base. Es decir, a cada paso recursivo se reduce el número de pasos que hay que dar para terminar, llegando un momento en el que no se verifica la condición de paso a la recursividad. Ni el paso base ni el paso recursivo son necesariamente únicos.

Por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P. También en estos casos debe haber una condición de parada.

Existen ciertas estructuras cuya definición es recursiva, tales como los árboles, y los algoritmos que utilizan árboles suelen ser en general recursivos

Dentro de la teoría de la recursión, se tiene que existen diferentes tipos de recursión:

* Recursión directa. Cuando el código F tiene una sentencia que involucra a F.

* Recursión indirecta o cruzada.- Cuando la función F involucra una función G que invoca a la ves una función H, y así sucesivamente, hasta que se involucra la función F. Por ejemplo el algoritmo de Par o impar.

* Recursión simple.- Aquella en cuya función solo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iteractivos.

* Recursión múltiple.- Se da cuando hay más de una llamada a sí misma dentro del cuerpo de la función, resultando más difícil de transformar a iteractiva. Por ejemplo el algoritmo de Fibonacci.

* Recursión anidada.- En algunos de los argumentos de la llamada hay una nueva llamada a sí misma.

* Recursión infinita

La iteración y la recursión pueden producirse infinitamente. Un bucle infinito ocurre si la prueba o test de continuación del bucle nunca se vuelve falsa.

En

...