CONTROL DE LA SEMANA N° 3 RECURSIVIDAD Y ARREGLOS

INSTRUCCIONES

1) Defina con sus propias palabras qué es un algoritmo recursivo y qué tipos de recursión existen.

2) Explique el algoritmo utilizado para resolver el juego – problema llamado “Las Torres de Hanoi”.

Respuesta 1:

Un algoritmo recursivo es un algoritmo que se define en términos de sí mismo. Son implementados en forma de subrutinas (funciones, procedimientos, subprogramas, etc.) de tal forma que dentro de una subrutina recursiva hay una o más llamadas a sí misma. Algunos ejemplos de recurrencia:

 En un texto: Para saber qué es la recurrencia, primero hay que saber qué es la recurrencia.

 En un acrónimo: ¿Qué es GNU? -> GNU No es Unix

¿Qué es PHP? -> PHP: Hipertext Preprocessor

 En matemáticas: f(x) = x * f(x-1)

 En un algoritmo:

FUNCIÓN Factorial(n)

INICIO

SI (n Subrutina_B --> Subrutina_A

Subrutina_A --> Subrutina_B --> Subrutina_C --> Subrutina_D --> Subrutina_A

En la ciencia de la computación, la recursividad es un elemento muy importante en la solución de algunos problemas. Por definición, un algoritmo recursivo es aquel que utiliza una parte de él mismo como solución al problema. La otra parte generalmente es la solución trivial, es decir, aquella cuya solución será siempre conocida, es muy fácil de calcular, o es parte de la definición del problema a resolver. Dicha solución sirve como referencia y además permite que el algoritmo tenga una cantidad finita de pasos.

La implementación de estos algoritmos se realiza generalmente en conjunto con una estructura de datos, la pila, en la cual se van almacenando los resultados parciales de cada recursión.

A manera de ejemplo (típico en la enseñanza de este tema) es el cálculo de factorial de manera recursiva.

Se puede definir el factorial de un número entero positivo x como sigue:

x!=x*(x-1)*(x-2)...*3*2*1

donde ! Indica la operación unaria de factorial.

Definimos, además:

1!=1 0!=1

Sin embargo, podemos observar que la definición de la factorial de un número x, puede expresarse, a su vez, a través de la factorial de otro número:

x!=x*(x-1)!

Es decir, para conocer el factorial de x basta con conocer el factorial de x-1 y multiplicarlo por x. Para conocer el factorial de x-1 basta con conocer el factorial de x-2, y multiplicarlo por x-1. Este proceso se realiza recursivamente, hasta llegar a la solución trivial, donde necesitamos el factorial de 1, el cual es 1.

Lo importante a notar en la igualdad anterior es que expresa un proceso recursivo, donde definimos una operación en términos de sí misma.

El seudocódigo queda así:

inicio de la rutina Factorial

Factorial(parámetro: entero x)

si x vale 1 o x vale 0

devolver 1

si no

devolver x*Factorial(x-1)

fin de la rutina Factorial

Ventajas:

Algunos problemas son esencialmente recursivos, por lo cual su implementación se facilita mediante un algoritmo de naturaleza recursiva, sin tener que cambiarlo a un método iterativo, por ejemplo. En algunas ocasiones el código de un algoritmo recursivo es muy pequeño

Desventajas:

Puede llegar a utilizar grandes cantidades de memoria en un instante, pues implementa una pila cuyo tamaño crece linealmente con el número de recursiones necesarias en el algoritmo. Si los datos en cada paso son muy grandes, podemos requerir grandes cantidades de memoria.

Tipos de Recursión:

Recursividad simple: Aquella en cuya definición sólo aparece una llamada recursiva. Se puede transformar con facilidad en algoritmos iterativos.

Recursividad 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 hacer de forma iterativa.

Recursividad anidada: En algunos de los arreglos de la llamada recursiva hay una nueva llamada a sí misma.

Recursividad

...