Maquina de turing

DISEÑO Y ADMINISTRACIÓN

DE

DATOS

RECURSIVIDAD:

ALGORITMOS RECURSIVOS

Índice……………......…………………………………………. 2
Introducción…………………………………………………….3
Recursividad…………………………………………………… 3
Cuándo no utilizar recursividad ………………………………...4
Eliminación de la recursividad..………………………………...5
Algoritmos “divide y vencerás”………………………………...6
Torres de Hanoi….…………………………………………….. 7
Implementación deprocedimientos recursivos mediante pilas…8
El problema de las Torres de Hanoi resuelto sin recursividad….9
Codificación no recursiva de las Torres de Hanoi………………11
Algoritmo de vuelta atrás (backtracking)……………………….12
Algoritmo caballo..……………………………………………..13
Solución del problema “salto del caballo” con esquema iterativo…………………………………………………………15
Problema de las ocho reinas…………………………………….22El problema de la selección óptima…………………………… 23
El viajante de comercio…………………………………………24
Problema de los matrimonios estables …..…..…………………24
Conclusión……………………………………………………...25
Bibliografía …………………………………………………….26

Introducción

Un procedimiento o función recursiva es aquella que se llama a sí misma. Esta característica permite a un procedimiento recursivo repetirse con valoresdiferentes de parámetros. La recursión es una alternativa a la iteración muy elegante en la resolución de problemas, especialmente si éstos tienen naturaleza recursiva.
Normalmente, una solución recursiva es menos eficiente en términos de tiempo de computadora que una solución iterativa debido al tiempo adicional de llamada a procedimientos.
En muchos casos, la recursión permite especificar unasolución más simple y natural para resolver un problema que en otro caso sería difícil. Por esta razón la recursión (recursividad) es una herramienta muy potente para la resolución de problemas y la programación.

RECURSIVIDAD

Un objeto recursivo es aquel que forma parte de sí mismo. Esta idea puede servir de ayuda para la definición de conceptos matemáticos. Así, la definición del conjunto de losnúmeros naturales es aquel conjunto en el que se cumplen las siguientes características:

• 0 es un número natural.
• El siguiente número de un número natural es otro número natural.

Mediante una definición finita hemos representado un conjunto infinito.
El concepto de recursividad es muy importante en programación. La recursividad es una herramienta muy eficaz para resolver diversostipos de problemas; existen muchos algoritmos que se describirán mejor en términos recursivos.
Supongamos que disponemos de una rutina Q que contiene sentencia de llamada a sí misma, o bien una sentencia de llamada a una segunda rutina que a su vez tiene una sentencia de llamada a la rutina original Q. Entonces se dice que Q es una rutina recursiva.
Un procedimiento o función recursivos han decumplir dos propiedades generales para no dar lugar a un bucle infinito con las sucesivas llamadas:

• Cumplir una cierta condición o criterio base del que dependa la llamada recursiva.
• Cada vez que el procedimiento o función se llaman a sí mismos, directa o indirectamente, debe estar más cerca del incumplimiento de la condición de que depende de la llamada.

Ejemplo: Secuenciade números de Fibonacci

Esta serie numérica es un ejemplo típico de cumplimiento de las dos propiedades generales de todo procedimiento recursivo. La serie de Fibonacci es:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

El término inicial es a0=0, y los siguientes son: a1=1, a2=2, a3=3, a5=8… observándose que cada término es la suma de los dos términos precedentes excepto a0 y a1.
La serie puede serdefinida recursivamente del modo siguiente:
Fibonacci(n) = n si n = 0 o n = 1
Fibonacci(n) = Fibonacci(n-2) + Fibonacci(n-1) para n>1

Esta definición recursiva hace referencia a ella misma dos veces Y la condición para que dejen de hacerse llamadas recursivas es que n sea 0 o 1. La llamada recursiva se hace en términos de menores de n, n-2, n-1, por lo que se va acercando a los valores...