Diferencia clave: recursividad frente a iteración
La recursividad y la iteración se pueden utilizar para resolver problemas de programación. El enfoque para resolver el problema usando recursividad o iteración depende de la forma de resolver el problema. La diferencia clave entre la recursión y la 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 recursividad y la iteración son técnicas importantes para desarrollar algoritmos y crear aplicaciones de software.
¿Qué es la recursividad?
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. La recursividad finita tiene una condición de terminación. La recursividad infinita no tiene una condición de terminación.
La recursión se puede explicar usando el programa para calcular factoriales.
n!=n(n-1)!, si n>0
n!=1, si n=0;
Consulte el siguiente código para calcular el factorial de 3(3!=321).
intmain () {
int valor=factorial (3);
printf(“El factorial es %d\n”, valor);
retornar 0;
}
intfactorial (intn) {
si(n==0) {
retorno 1;
}
más {
retorna n factorial(n-1);
}
}
Al llamar al factorial (3), esa función llamará al factorial (2). Al llamar al factorial (2), esa función llamará al factorial (1). Entonces factorial (1) llamará factorial (0). factorial (0) devolverá 1. En el programa anterior, la condición n==0 en el “bloque if” es la condición base. De acuerdo con Del 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. Entonces, main () es la función que llama, y la función que llama el programa principal es la función llamada. Cuando se llama a la función, el control se le da a la función llamada. Una vez completada la ejecución de la función, el control vuelve a main. Luego continúa el programa principal. Entonces, crea un registro de activación o un marco de pila para continuar con la ejecución.
Figura 01: Recursión
En el programa anterior, al llamar a factorial (3) desde main, se crea un registro de activación en la pila de llamadas. Luego, se crea un marco de pila factorial (2) en la parte superior de la pila y así sucesivamente. El registro de activación mantiene información sobre las 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. Del mismo modo, en la recursividad, 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 un número n de llamadas recursivas, la complejidad temporal es O(n).
¿Qué 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 usando "for loop", "do-while loop" o "while loop". La sintaxis del "bucle for" es la siguiente.
for (inicialización; condición; modificar) {
// sentencias;
}
Figura 02: “para diagrama de flujo de bucle”
El paso de inicialización se ejecuta primero. Este paso es para declarar e inicializar variables de control de bucle. Si la condición es verdadera, se ejecutan las declaraciones dentro de las llaves. 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 sentencias dentro del ciclo, el control va 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 declaraciones dentro de las llaves. De esta forma, el "bucle for" itera.
En el "bucle while", las sentencias dentro del bucle se ejecutan hasta que la condición es verdadera.
mientras (condición){
//declaraciones
}
En el bucle "do-while", la condición se comprueba al final del bucle. Entonces, 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 ("bucle for") es el siguiente.
int principal(){
intn=3, factorial=1;
inti;
para(i=1; i<=n; i++){
factorial=factoriali;
}
printf(“El factorial es %d\n”, factorial);
retornar 0;
}
¿Cuáles son las similitudes entre la recursividad y la iteración?
- Ambas son técnicas para resolver un problema.
- La tarea se puede resolver en recursividad o iteración.
¿Cuál es la diferencia entre recursividad e iteración?
Recursión frente a iteración |
|
| La recursividad 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 espacial de los programas recursivos es mayor que la de las iteraciones. | La complejidad del espacio es menor en las iteraciones. |
| Velocidad | |
| La ejecución de la recursividad es lenta. | Normalmente, la iteración es más rápida que la recursividad. |
| Condición | |
| Si no hay una condición de terminación, puede haber una recursividad infinita. | Si la condición nunca se vuelve falsa, será una iteración infinita. |
| Pila | |
| En recursividad, la pila se usa para almacenar variables locales cuando se llama a la función. | En una iteración, la pila no se usa. |
| Legibilidad del código | |
| Un programa recursivo es más legible. | El programa iterativo es más difícil de leer que un programa recursivo. |
Resumen: recursividad frente a iteración
Este artículo analiza la diferencia entre recursividad e iteración. Ambos se pueden utilizar 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 e iterarla para ejecutar un conjunto de instrucciones repetidamente hasta que la condición dada sea verdadera. Si un problema se puede resolver en forma recursiva, también se puede resolver mediante iteraciones.
Descargue la versión en PDF de Recursión vs Iteración
Puede descargar la versión en PDF de este artículo y utilizarlo sin conexión según la nota de la cita. Descargue la versión en PDF aquí Diferencia entre recursividad e iteración
