Diferencia entre recursividad e iteración

Diferencia Clave - Recursión vs iteración
 

La recursión y la iteración pueden usarse para resolver problemas de programación. El enfoque para resolver el problema mediante la recursión o la iteración depende de la forma de resolver el problema. los diferencia clave Entre recursividad e iteración es que la recursión es un mecanismo para llamar a una función dentro de la misma función, mientras que la iteración es ejecutar un conjunto de instrucciones repetidamente hasta que la condición dada sea verdadera. La recursión y la iteración son técnicas importantes para desarrollar algoritmos y crear aplicaciones de software.

CONTENIDO

1. Resumen y diferencia clave
2. Que es la recursion
3. Que es la iteración
4. Similitudes entre recursión e iteración
5. Comparación lado a lado: recursión frente a iteración en forma tabular
6. Resumen

Que es la recursion?

Cuando una función se llama a sí misma dentro de la función, se conoce como Recursión. Hay dos tipos de recursión. Son recursión finita y recursión infinita.. Recursion finita tiene una condición de terminación. Recursion infinita no tiene una condición de terminación.

La recursión puede ser explicada usando el programa para calcular factoriales..

¡norte! = n * (n-1) !, si n> 0

¡norte! = 1, si n = 0;

Consulte el código de abajo para calcular el factorial de 3 (3! = 3 * 2 * 1).

intmain ()

valor int = factorial (3);

printf ("Factorial es% d \ n", valor);

devuelve 0;

intfactorial (intn)

si (n == 0)

devuelve 1;

else

devuelve n * factorial (n-1);

Cuando se llama factorial (3), esa función llamará factorial (2). Cuando se llama factorial (2), esa función llamará factorial (1). Entonces factorial (1) llamará factorial (0). factorial (0) devolverá 1. En el programa anterior, n == 0 condición en el "bloque if" es la condición base. Según el mismo modo, la función factorial se llama una y otra vez..

Las funciones recursivas están relacionadas con la pila. En C, el programa principal puede tener muchas funciones. Por lo tanto, main () es la función de llamada, y la función llamada por el programa principal es la función llamada. Cuando se llama a la función, el control se da a la función llamada. Una vez completada la ejecución de la función, el control vuelve a main. Entonces el programa principal continúa. Por lo tanto, crea un registro de activación o un marco de pila para continuar la ejecución.

Figura 01: Recursión

En el programa anterior, cuando se llama factorial (3) desde main, se crea un registro de activación en la pila de llamadas. Luego, el marco de pila factorial (2) se crea en la parte superior de la pila y así sucesivamente. El registro de activación mantiene información sobre variables locales, etc. Cada vez que se llama a la función, se crea un nuevo conjunto de variables locales en la parte superior de la pila. Estos marcos de pila pueden ralentizar la velocidad hacia arriba. Igualmente en la recursión, una función se llama a sí misma. La complejidad del tiempo para una función recursiva se encuentra por el número de veces que se llama a la función. La complejidad del tiempo para una llamada de función es O (1). Para n número de llamadas recursivas, la complejidad del tiempo es O (n).

Que es la iteración?

La iteración es un bloque de instrucciones que se repite una y otra vez hasta que la condición dada es verdadera. La iteración se puede lograr utilizando "bucle for", "bucle do-while" o "bucle while". La sintaxis de "bucle" es la siguiente.

para (inicialización; condición; modificar)

// declaraciones;

Figura 02: “para diagrama de flujo de bucle”

El paso de inicialización se ejecuta primero. Este paso es declarar e inicializar las variables de control de bucle. Si la condición es verdadera, las declaraciones dentro de las llaves se ejecutan. Esas declaraciones se ejecutan hasta que la condición es verdadera. Si la condición es falsa, el control pasa a la siguiente declaración después del "bucle for". Después de ejecutar las instrucciones dentro del bucle, el control pasa a la sección de modificación. Es para actualizar la variable de control de bucle. Entonces la condición se comprueba de nuevo. Si la condición es verdadera, se ejecutarán las instrucciones dentro de las llaves. De esta manera el “for loop” itera.

En "while loop", Las instrucciones dentro del bucle se ejecutan hasta que la condición es verdadera..

while (condición)

// declaraciones

En bucle "do-while", La condición se verifica al final del bucle. Así, el bucle se ejecuta al menos una vez..

hacer

// declaraciones

while (condición)

El programa para encontrar el factorial de 3 (3!) Usando la iteración ("for loop") es el siguiente.

int main ()

intn = 3, factorial = 1;

inti

para (i = 1; i<=n ; i++)

factorial = factorial * i;

printf ("Factorial es% d \ n", factorial);

devuelve 0;

Cuáles son las similitudes entre la recursión y la iteración?

• Ambas son técnicas para resolver un problema..
• La tarea se puede resolver ya sea en recursión o iteración.

Cuál es la diferencia entre recursión e iteración?

Recursion vs Iteracion
La recursión es un método para llamar a una función dentro de la misma función.	La iteración es un bloque de instrucciones que se repite hasta que la condición dada es verdadera.
Complejidad espacial
La complejidad del espacio de los programas recursivos es mayor que las iteraciones..	La complejidad del espacio es menor en las iteraciones..
Velocidad
La ejecución de la recursión es lenta.	Normalmente, la iteración es más rápida que la recursión.
Condición
Si no hay una condición de terminación, puede haber una recursión infinita.	Si la condición nunca se vuelve falsa, será una iteración infinita..
Apilar
En la recursión, la pila se utiliza para almacenar variables locales cuando se llama a la función.	En una iteración, la pila no se utiliza.
Código legible
Un programa recursivo es más legible.	El programa iterativo es más difícil de leer que un programa recursivo.

Resumen - Recursión vs iteración

Este artículo discutió la diferencia entre recursión e iteración. Ambos pueden ser utilizados para resolver problemas de programación. La diferencia entre recursión e iteración es que la recursión es un mecanismo para llamar a una función dentro de la misma función y iterarla para ejecutar un conjunto de instrucciones repetidamente hasta que la condición dada sea verdadera. Si un problema se puede resolver de forma recursiva, también se puede resolver utilizando iteraciones.

Descargue la versión en PDF de Recursion vs Iteration

Puede descargar la versión en PDF de este artículo y usarla para fines fuera de línea, como se indica en la nota de cita. Por favor descargue la versión en PDF aquí Diferencia entre recursión e iteración

Referencia:

1.Point, Tutoriales. "Estructuras de datos y algoritmos básicos de recursión"., Punto de tutoriales, 15 de agosto de 2017. Disponible aquí 
2.nareshtechnologies. “Recursión en funciones C | Tutorial de lenguaje C ”YouTube, YouTube, 12 de septiembre de 2016.  Disponible aquí  
3.yusuf shakeel. “Algoritmo de recursión | Factorial: guía paso a paso "YouTube, YouTube, 14 de octubre de 2013.  Disponible aquí  

Imagen de cortesía:

1.'CPT-Recursion-Factorial-Code'By Pluke - Trabajo propio, (Dominio público) a través de Commons Wikimedia 
2.'For-loop-diagram'By No se proporciona autor legible por máquina - Se supone trabajo propio. (CC BY-SA 2.5) vía Commons Wikimedia