Un programa se llama recursivo cuando una entidad se llama a sí misma. Un programa se llama iterativo cuando hay un bucle (o repetición).
Ejemplo: Programa para hallar el factorial de un número
C++
// C++ program to find factorial of given number #include<bits/stdc++.h> using namespace std; // ----- Recursion ----- // method to find factorial of given number int factorialUsingRecursion(int n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number int factorialUsingIteration(int n) { int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver method int main() { int num = 5; cout << "Factorial of " << num << " using Recursion is: " << factorialUsingRecursion(5) << endl; cout << "Factorial of " << num << " using Iteration is: " << factorialUsingIteration(5); return 0; } // This code is contributed by mits
Java
// Java program to find factorial of given number class GFG { // ----- Recursion ----- // method to find factorial of given number static int factorialUsingRecursion(int n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number static int factorialUsingIteration(int n) { int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver method public static void main(String[] args) { int num = 5; System.out.println("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)); System.out.println("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); } }
Python3
# Python3 program to find factorial of given number # ----- Recursion ----- # method to find factorial of given number def factorialUsingRecursion(n): if (n == 0): return 1; # recursion call return n * factorialUsingRecursion(n - 1); # ----- Iteration ----- # Method to find the factorial of a given number def factorialUsingIteration(n): res = 1; # using iteration for i in range(2, n + 1): res *= i; return res; # Driver method num = 5; print("Factorial of",num,"using Recursion is:", factorialUsingRecursion(5)); print("Factorial of",num,"using Iteration is:", factorialUsingIteration(5)); # This code is contributed by mits
C#
// C# program to find factorial of // given number using System; class GFG { // ----- Recursion ----- // method to find factorial of // given number static int factorialUsingRecursion(int n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of // a given number static int factorialUsingIteration(int n) { int res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver Code public static void Main(String[] args) { int num = 5; Console.WriteLine("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)); Console.WriteLine("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); } } // This code has been contributed by Rajput-Ji
PHP
<?php // PHP program to find factorial of given number // ----- Recursion ----- // method to find factorial of given number function factorialUsingRecursion($n) { if ($n == 0) return 1; // recursion call return $n * factorialUsingRecursion($n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number function factorialUsingIteration($n) { $res = 1; // using iteration for ($i = 2; $i <= $n; $i++) $res *= $i; return $res; } // Driver method $num = 5; print("Factorial of ".$num." using Recursion is: ". factorialUsingRecursion(5)."\n"); print("Factorial of ".$num." using Iteration is: ". factorialUsingIteration(5)."\n"); // This code is contributed by mits ?>
Javascript
<script> // JavaScript program to find factorial of given number // ----- Recursion ----- // method to find factorial of given number function factorialUsingRecursion(n) { if (n == 0) return 1; // recursion call return n * factorialUsingRecursion(n - 1); } // ----- Iteration ----- // Method to find the factorial of a given number function factorialUsingIteration(n) { var res = 1, i; // using iteration for (i = 2; i <= n; i++) res *= i; return res; } // Driver method var num = 5; document.write("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)+"<br>"); document.write("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); // This code is contributed by shivanisinghss2110 </script>
Producción:
Factorial of 5 using Recursion is: 120 Factorial of 5 using Iteration is: 120
A continuación se muestra el ejemplo detallado para ilustrar la diferencia entre los dos:
- Complejidad del tiempo: encontrar la complejidad del tiempo de la recursividad es más difícil que la de la iteración.
- Recursividad : la complejidad temporal de la recursividad se puede encontrar encontrando el valor de la n-ésima llamada recursiva en términos de las llamadas anteriores. Por lo tanto, encontrar el caso de destino en términos del caso base y resolver en términos del caso base nos da una idea de la complejidad temporal de las ecuaciones recursivas. Consulte Resolver recurrencias para obtener más detalles.
- Iteración : la complejidad temporal de la iteración se puede encontrar encontrando el número de ciclos que se repiten dentro del bucle.
- Recursividad : la complejidad temporal de la recursividad se puede encontrar encontrando el valor de la n-ésima llamada recursiva en términos de las llamadas anteriores. Por lo tanto, encontrar el caso de destino en términos del caso base y resolver en términos del caso base nos da una idea de la complejidad temporal de las ecuaciones recursivas. Consulte Resolver recurrencias para obtener más detalles.
- Uso: el uso de cualquiera de estas técnicas es una compensación entre la complejidad del tiempo y el tamaño del código. Si la complejidad del tiempo es el punto de enfoque y la cantidad de llamadas recursivas sería grande, es mejor usar la iteración. Sin embargo, si la complejidad del tiempo no es un problema y la brevedad del código sí lo es, la recursividad sería el camino a seguir.
- Recursión : la recursión implica volver a llamar a la misma función y, por lo tanto, tiene una longitud de código muy pequeña. Sin embargo, como vimos en el análisis, la complejidad temporal de la recursividad puede llegar a ser exponencial cuando existe un número considerable de llamadas recursivas. Por lo tanto, el uso de la recursividad es ventajoso en código más corto, pero con mayor complejidad de tiempo.
- Iteración : La iteración es la repetición de un bloque de código. Esto implica un tamaño de código más grande, pero la complejidad del tiempo es generalmente menor que para la recursividad.
- Recursión : la recursión implica volver a llamar a la misma función y, por lo tanto, tiene una longitud de código muy pequeña. Sin embargo, como vimos en el análisis, la complejidad temporal de la recursividad puede llegar a ser exponencial cuando existe un número considerable de llamadas recursivas. Por lo tanto, el uso de la recursividad es ventajoso en código más corto, pero con mayor complejidad de tiempo.
- Overhead: La recursividad tiene una gran cantidad de gastos generales en comparación con la iteración.
- Recursión : la recursión tiene la sobrecarga de llamadas de función repetidas, que se debe a llamadas repetitivas de la misma función, la complejidad del tiempo del código aumenta muchas veces.
- Iteración : la iteración no implica ninguna sobrecarga de este tipo.
- Recursión : la recursión tiene la sobrecarga de llamadas de función repetidas, que se debe a llamadas repetitivas de la misma función, la complejidad del tiempo del código aumenta muchas veces.
- Repetición infinita: la repetición infinita en la recursividad puede provocar un bloqueo de la CPU, pero en la iteración, se detendrá cuando se agote la memoria.
- Recursion : En Recursion, las llamadas recursivas infinitas pueden ocurrir debido a algún error en la especificación de la condición base, que al nunca volverse falsa, sigue llamando a la función, lo que puede provocar un bloqueo de la CPU del sistema.
- Iteración : la iteración infinita debido a un error en la asignación o el incremento del iterador, o en la condición de terminación, dará lugar a bucles infinitos, que pueden o no dar lugar a errores del sistema, pero seguramente detendrán más la ejecución del programa.
- Recursion : En Recursion, las llamadas recursivas infinitas pueden ocurrir debido a algún error en la especificación de la condición base, que al nunca volverse falsa, sigue llamando a la función, lo que puede provocar un bloqueo de la CPU del sistema.
Propiedad | recursividad | Iteración |
---|---|---|
Definición | La función se llama a sí misma. | Un conjunto de instrucciones ejecutadas repetidamente. |
Solicitud | Para funciones. | Para bucles. |
Terminación | A través del caso base, donde no habrá llamada de función. | Cuando deja de cumplirse la condición de terminación del iterador. |
Uso | Se usa cuando el tamaño del código debe ser pequeño y la complejidad del tiempo no es un problema. | Se utiliza cuando la complejidad del tiempo debe equilibrarse con un tamaño de código ampliado. |
Tamaño del código | Tamaño de código más pequeño | Tamaño de código más grande. |
Complejidad del tiempo | Complejidad temporal muy alta (generalmente exponencial). | Complejidad temporal relativamente menor (generalmente polinomial-logarítmica). |