c++ - ventaja - ¿Cuál es la diferencia entre iteración y recursión?

recursividad vs

Question

¿Cuál es la diferencia entre iteration y recursion y por qué / cuándo es mejor:

while (true) {
    // Iterating
}

Y

private void recursion() {
    if (true)
        recursion(); // Recursing

    return;
}

Veo mucha implementación recursive , mientras que se podría hacer fácilmente en un bucle simple.

Answer 1

Diferencias entre recursividad e iteración.

Recursion

1. Función recursiva: es una función que está parcialmente definida por sí misma.
2. La recursión utiliza la estructura de selección.
3. La recursión infinita ocurre si el paso de recursión no reduce el problema de una manera que converge en alguna condición (caso base)
4. La recursión termina cuando se reconoce un caso base
5. La recursión suele ser más lenta que la iteración debido a la sobrecarga de mantener la pila
6. La recursión usa más memoria que iteración.
7. La recursión infinita puede estrellar el sistema
8. La recursión hace que el código sea más pequeño.

Iteración

1. Instrucciones iterativas - son repeticiones basadas en bucles de un proceso.
2. Iteración usa estructura de repetición.
3. Se produce un bucle infinito con iteración si la prueba de condición de bucle nunca se vuelve falsa
4. La iteración termina cuando falla la condición de bucle
5. La iteración no usa la pila, por lo que es más rápida que la recursión
6. La iteración consume menos memoria
7. Bucle infinito utiliza ciclos de CPU repetidamente
8. La iteración hace que el código sea más largo

Datos tomados de here .

Answer 2

En teoría, siempre se puede cambiar entre iteración y recursión. Sin embargo, al menos en el caso de C / C ++ / C # / Java, el compilador le ofrece algo de soporte que podría hacer que la solución sea más elegante, especialmente cuando no conoce el número de bucles anteriormente.

El mejor ejemplo es enumerar todos los archivos dentro de una carpeta y sus descendientes. Si hay varias subcarpetas que contienen subcarpetas, normalmente en modo iteración, necesita una pila para guardar todas las carpetas que necesita analizar. En el caso de un enfoque recursivo, el compilador ya proporciona la pila y la solución es más elegante.

Answer 3

Hay dos diferencias principales entre la recursión y una versión iterativa del mismo algoritmo.

En primer lugar, algunas veces es casi mejor entender un algoritmo recursivo que uno iterativo (al menos si usted es un programador experimentado). Por lo tanto, aumenta la expresividad y en algunos casos la legibilidad (en otros casos, también puede llevar a lo contrario). )

La expresividad es un gran negocio en lenguajes de programación y poder escribir el mismo código en 5 líneas en lugar de 20 es un gran negocio.

En el lado negativo, disminuye el rendimiento de su código. Las funciones recursivas tienen que mantener los registros de función en la memoria y saltar de una dirección de memoria a otra para ser invocados para pasar parámetros y valores de retorno. Eso los hace muy malos en cuanto a rendimiento.

Resumir:

Algoritmos iterativos = Rendimiento rápido pero difícil de escribir (a veces también es difícil de leer)

Algoritmos recursivos = Rápido de escribir pero con un rendimiento deficiente (a veces también es más fácil de entender)

Tomemos este ejemplo:

public static long fib(long n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

vs

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }

Fuente:

http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java

Answer 4

La principal diferencia entre la recursión y la iteración es el uso de la memoria.

Para cada llamada recursiva se necesita espacio en el marco de la pila, lo que genera una sobrecarga de memoria.

Dejame darte un ejemplo. Imagínese en un caso que olvidó escribir el caso base para su función recursiva que resulta en llamadas recursivas sin fin y en el otro caso que escribió un bucle infinito.

Dado que cada función recursiva asigna un nuevo espacio de memoria, en el primer caso, su código dará una excepción de desbordamiento de pila, pero en el segundo caso seguirá funcionando para siempre.

Por lo tanto, es mejor hacer que tu código iterativo sea más comprensible que usar Recursion.

Answer 5

La recursión y la iteración son diferentes maneras de pensar acerca de una solución. Sería difícil explicar en profundidad la diferencia en el alcance total. En su código de ejemplo, ya mostró la diferencia. La función recursiva es la que se llama a sí misma, mientras que la iterativa es la que recorre un bloque de código. Aquí hay algunos artículos para ayudarte a entenderlos mejor: Recursión wiki

Wiki iteración

CodeProject SO # 1

SO # 2

Answer 6

Las funciones recursivas funcionan a través del proceso de llamarse a sí mismas hasta que se cumple una condición, mientras que la iteración utiliza una estructura de control de bucle (por ejemplo, mientras hace do, para) para repetir una sección de código hasta que se cumpla una determinada condición.

Ejemplo recursivo:

int rec_func(int u, int k) {
  if (k == 0)
    return u;
  return rec_func(u * k, k - 1);
}

Ejemplo de iteración:

int ite_func(int u, int k) {
  while (k != 0) {
    u = u * k;
    k = k - 1;
  }
  return u;
} 

La única diferencia real de la OMI entre ellos es la compilación de diferencias.

Answer 7

Se pueden utilizar intercambiables para resolver diferentes problemas. En esencia, puede escribir funciones recursivas de forma iterativa y viceversa.

La iteración puede aumentar el rendimiento de su programa. Mientras que la recursión puede dar un resultado más intuitivo y elegante. Usted puede elegir cualquiera de los cuales a su preferencia!

Answer 8

Son formas diferentes de hacer lo mismo. Todas las implementaciones recursivas se pueden realizar con un (o varios) bucle (s) y viceversa. Es más sobre la lógica detrás de esto, una manera de pensar en ello. Factorial, aunque no es el mejor ejemplo, es n * (n-1)! Así que tiene sentido usarlo recursivamente.