Diferencia entre recursividad e iteración

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:
 

  1. 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. 
       
  2. 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. 
       
  3. 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. 
       
  4. 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. 
       

  
 

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).

Publicación traducida automáticamente

Artículo escrito por dkp1903 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *