Iteración frente a recursividad en Java

1. Recurrencia

Considere la función factorial: n!=n*(n-1)*(n-2)*...*1

Hay muchas formas de calcular factoriales. ¡Una forma es que n! es igual an * (n-1) !. Por lo tanto, el programa se puede escribir directamente como:

Programa 1:

int factorial (int n) {
    if (n == 1) {
        return 1;
    } else {
        return n*factorial(n-1);
    }
}

Para ejecutar este programa, la computadora necesita construir una cadena de multiplicaciones: factorial (n) → factorial (n-1) → factorial (n-2) → … → factorial (1). Por lo tanto, la computadora debe realizar un seguimiento de las multiplicaciones que se realizarán más adelante. Este tipo de programa, caracterizado por una cadena de operaciones, se llama recursividad. La recursividad se puede categorizar además en lineal y árbol recursividad. Cuando la cantidad de información necesaria para realizar un seguimiento de la cadena de operaciones crece linealmente con la entrada, la recursividad se denomina recursividad lineal. El cálculo de n! es tal caso, porque el tiempo requerido crece linealmente con n. Otro tipo de recursividad, la recursividad de árbol, ocurre cuando la cantidad de información crece exponencialmente con la entrada. Pero lo dejaremos sin discutir aquí y volveremos poco después.

2. Iteración

Una perspectiva diferente sobre el cálculo de factoriales es multiplicar primero 1 por 2, luego multiplicar el resultado por 3, luego por 4, y así sucesivamente hasta n. Más formalmente, el programa puede usar un contador que cuenta desde 1 hasta ny calcular el producto simultáneamente hasta que el contador exceda n. Por lo tanto, el programa se puede escribir como:

Programa 2:

int factorial (int n) {
    int product = 1;
    for(int i=2; i<n; i++) {
        product *= i;
    }
    return product;
}

Este programa, a diferencia del programa 2, no construye una cadena de multiplicación. En cada paso, la computadora solo necesita realizar un seguimiento de los valores actuales del producto e i. Este tipo de programa se denomina iteración, cuyo estado se puede resumir en un número fijo de variables, una regla fija que describe cómo deben actualizarse las variables y una prueba final que especifica las condiciones bajo las cuales debe terminar el proceso. Al igual que la recursividad, cuando el tiempo requerido crece linealmente con la entrada, llamamos a la iteración recursión lineal.

3. Recurrencia frente a iteración

Comparados los dos procesos, podemos encontrar que parecen casi iguales, especialmente en términos de función matemática. Ambos requieren un número de pasos proporcionales an para calcular n !. Por otro lado, cuando consideramos los procesos en ejecución de los dos programas, evolucionan de manera bastante diferente.

En el caso iterativo, las variables del programa proporcionan una descripción completa del estado. Si paramos el cómputo a la mitad, para reanudarlo solo es necesario suministrar al ordenador todas las variables. Sin embargo, en el proceso recursivo, la información es mantenida por la computadora, por lo tanto «oculta» al programa. Esto hace que sea casi imposible reanudar el programa después de detenerlo.

4. Recursión de árboles

Como se describió anteriormente, la recursividad del árbol ocurre cuando la cantidad de información crece exponencialmente con la entrada. Por ejemplo, considere la secuencia de números de Fibonacci definida de la siguiente manera:

Por definición, los números de Fibonacci tienen la siguiente secuencia, donde cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Un programa recursivo se puede escribir inmediatamente como:

Programa 3:

int fib (int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fib(n-1) + fib(n-2);
    }
}

Por lo tanto, para calcular fib (5), el programa calcula fib (4) y fib (3). Para la computadora fib (4), calcula fib (3) y fib (2). Observe que el procedimiento de fib se llama a sí mismo dos veces en la última línea. Se pueden obtener dos observaciones de la definición y el programa:

1. El i-ésimo número de Fibonacci Fib (i) es igual a phi (i) / rootsquare (5) redondeado al entero más cercano, lo que indica que los números de Fibonacci crecen exponencialmente.
2. Esta es una mala forma de calcular números de Fibonacci porque hace cálculos redundantes. Calcular el tiempo de ejecución de este procedimiento está más allá del alcance de este artículo, pero se puede encontrar fácilmente en los libros de algoritmos, que es O (phi (n)). Por lo tanto, el programa toma una cantidad de tiempo que crece exponencialmente con la entrada.

Por otro lado, también podemos escribir el programa de forma iterativa para calcular los números de Fibonacci. El programa 4 es una iteración lineal. La diferencia de tiempo requerida por los programas 3 y 4 es enorme, incluso para entradas pequeñas.

Programa 4:

int fib (int n) {
    int fib = 0;
    int a = 1;
    for(int i=0; i<n; i++) {
       fib = fib + a;
       a = fib;
    }
    return fib;
}

Sin embargo, uno no debería pensar que los programas recursivos de árboles son inútiles. Cuando consideramos programas que operan en estructuras de datos jerárquicamente en lugar de números, la recursividad de árboles es una herramienta natural y poderosa. Puede ayudarnos a comprender y diseñar programas. En comparación con los programas 3 y 4, podemos decir fácilmente que el programa 3 es más sencillo, incluso si es menos eficiente. Después de eso, lo más probable es que podamos reformular el programa de forma iterativa.

Referencia:
1. Conferencia de Cornell CS211