Iteración vs Recursión

[pic 1]

Universidad Tecnológica Centroamericana

(UNITEC)

Alumno: 

Milton Joel Martínez.

No. Cuenta:

11511162.

Catedrático:

 Ing. Carlos Arias.

Clase:

 Estructura de Datos.

 Sección:

496

Tema:

Iteración y Recursión.

Fecha:

 10 de Febrero del 2017.

Introducción

La presente investigación  se refiere al tema de eficiencia entre un algoritmo iterativo y un algoritmo recursivo, un algoritmo iterativo se puede definir como el acto de repetir un proceso con el fin de llegar a un resultado, y un algoritmo recursivo se puede definir como un algoritmo que  expresa la solución del problema en términos de una llamada a sí mismo.

La característica principal de ambos algoritmos es su manera de implementar, ya que al final ambos llegan a la misma respuesta, pero la forma de llegar a esa respuesta es distinta.

La implementación de un algoritmo recursivo, es que el algoritmo hace una llamada así mismo, teniendo un caso base, y mientras el caso base no se cumpla, el algoritmo seguirá creando un Stack Frame, guardando en la pila las variables, hasta llegar a cumplir el caso base.

Marco Teórico

¿Que es la recursividad?

La recursividad es una técnica de programación que se utiliza para realizar una llamada a una función desde ella misma, de allí su nombre. El ejemplo más utilizado por su fácil comprensión es el cálculo de números factoriales.

La recursión se utiliza mejor para los problemas en los que una gran tarea puede desglosarse en una repetitiva "subtarea". Debido a que una rutina recursiva se llama a realizar esas subtareas, eventualmente la rutina se encontrará con una subtarea que puede manejar sin llamarse a sí misma. Esto se conoce como un caso base, y es necesario para evitar que la rutina se vuelva a llamar una y otra vez sin detenerse. Por lo tanto, se puede decir que el caso base detiene la recursión.

En el caso base, la rutina no se llama a sí misma. Pero, cuando una rutina tiene que llamarse a sí misma para completar su subtarea, entonces eso se conoce como el caso recursivo. Por lo tanto, hay 2 tipos de casos cuando se utiliza un algoritmo recursivo: casos base y casos recursivos. Esto es muy importante recordar cuando se usa la recursividad, y cuando se intenta resolver un problema debe preguntarse: "¿Cuál es mi caso base y cuál es mi caso recursivo?". (ProgrammerInterview.com)

int Factorial(int n){

if (n < 0){

cout << “No existe el factorial de un numero negativo.\n”;

}else if(n < 2){

return 1;

}else

return n * Factorial(n-1);

}

(Delphin)

Call Stack: Una pila de llamadas es una estructura de datos utilizada por el programa para almacenar información sobre las subrutinas activas (como funciones en C ++ o métodos en Java) en un programa. La principal razón para tener una pila de llamadas es para que el programa pueda realizar un seguimiento de donde una subrutina debe devolver el control una vez que termina de ejecutar. Por ejemplo, supongamos que tenemos un método "CreateBox" que llama a otro método "CreateLine" en 4 lugares diferentes. Si el programa ha terminado de ejecutar el método CreateLine, entonces necesita saber dónde en el método CreateBox necesita volver. Esta es la razón por la que el programa utiliza una pila de llamadas - para que pueda realizar un seguimiento de

Estos detalles.

Stack frames: Un marco de pila es una parte de la pila de llamadas y un nuevo marco de pila se crea cada vez que se llama a una subrutina. Por lo tanto, en nuestro método factorial recursivo anterior, se crea un nuevo marco de pila cada vez que se llama al método. El marco de pila se utiliza para almacenar todas las variables para una invocación de una rutina. Por lo tanto, recuerde que una pila de llamadas es básicamente una pila de marcos de pila.

[pic 2][pic 3]

(ProgrammerInterview.com)

¿Qué es iteración?

Iteración, significa el acto de repetir un proceso con la intención de alcanzar una meta deseada, objetivo o resultado. Cada repetición del proceso también se le denomina una "iteración", y los resultados de una iteración se utilizan como punto de partida para la siguiente iteración.

int Factorial(int n){

        int fact = 1;

        for(int i = 1; i

                fact = fact*i;

        }

        return fact;

}

(Wikipedia)

Metodología

Para la investigación se utilizaron los siguientes componentes:

...