condiciones de salida. error de desbordamiento de pila

Ejemplo de código recursivo sin condición de salida

Echemos otro vistazo a un problema recursivo. Como ejemplo, considere calcular los números de Fibonacci. Todo el mundo recordará que la secuencia de Fibonacci es una secuencia numérica en la que los dos primeros números son 0 y 1, y cada número posterior es igual a la suma de los dos números anteriores.

Escribamos código para calcular y mostrar estos números:

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}

Antes de la primera llamada del método recursivo printFibonacci , imprima los dos primeros números de la secuencia: cero y uno. Necesitamos hacer esto porque el método recursivo muestra solo la suma de los parámetros de entrada, no los parámetros en sí.

El código se ve bien: obtenemos dos números, calculamos su suma, la imprimimos en la consola y volvemos a llamar recursivamente al método printFibonacci . Pasamos el número anterior (anterior) y el número actual (actual) como argumentos.

En realidad, el código tiene dos errores. Puedes verlos si ejecutas el código.

El primer error es desbordar el tipo largo . El número 104 de nuestra secuencia es negativo, lo que indica que el tipo largo se desbordó.

El segundo error es diferente. Después de calcular aproximadamente 12.000 números, obtenemos:

Ahora es el momento apropiado para recordar qué es una pila de llamadas a métodos en Java. La máquina Java mantiene un registro de todas las llamadas a funciones. Para hacer esto, utiliza un tipo especial de colección llamada pila. Cuando una función llama a otra, la máquina Java inserta un nuevo StackTraceElement en la pila. Cuando finaliza la función, este elemento se elimina de la pila. En consecuencia, la pila siempre almacena información actualizada sobre el estado actual de la pila de llamadas a funciones. La documentación de StackTraceElement dice que "se lanza cuando se produce un desbordamiento de pila porque una aplicación se repite demasiado". Una JVM en ejecución tiene un área especial de memoria para almacenar la pila de llamadas al método. El tamaño de esta área de memoria depende de la configuración del sistema operativo y la JVM. Además de la propia pila de llamadas al método, Las variables primitivas (valores específicos de los parámetros del método) y las direcciones de las variables de referencia (en un área de memoria llamada "montón") se almacenan en esta área de memoria especial. El acceso a la pila de llamadas sigue el principio LIFO.

Ejemplo corregido con una condición de salida.

Comencemos solucionando el segundo problema en el código.

Intentemos resolver el problema de frente: si la pila es demasiado pequeña, entonces hagámosla más grande. Para hacer esto, inicie la JVM con el indicador "-Xss" y especifique cuánta memoria asignar para la pila. Intentemos asignar 5 megabytes. Así es como se verá en IDEA:

Conseguimos aumentar la longitud de la salida. Ahora puede calcular más de 49 000 números de la secuencia en lugar de estar limitado a unos 12 000 números. Pero en algún momento, todavía obtenemos un StackOverflowError .

Puede intentar aumentar el tamaño de la pila, pero eso no soluciona el problema fundamental. Entonces, busquemos un problema en la lógica. Debe haber un punto en el que la recursividad se detiene. En otras palabras, debe haber alguna condición que determine cuándo ya no se llamará al método recursivo, lo que permitirá que la pila de llamadas se relaje. Para definir tal condición, hagamos explícito nuestro objetivo: mostrar la serie de Fibonacci siempre que sus números sean menores que Integer.MAX_VALUE .

Escribamos un nuevo método printFibonacciWithCondition que tendrá en cuenta esta condición. Y llamaremos al nuevo método corregido en el método principal.

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}

Después de ejecutar el código, vemos que la salida termina con el número 1836311903. El número anterior a este es 1134903170. La suma de estos números es 2_971_215_073, que es mayor que Integer.MAX_VALUE (2_147_483_647 ) .

Este cambio solucionó automáticamente el error de desbordamiento largo . Si necesita calcular más de la serie, deberá usar otros tipos de datos, como BigInteger .

Descenso recursivo y desenrollado

Analicemos paso a paso cómo se ejecuta nuestro código. Para hacer esto, agregaremos un método echo y lo llamaremos antes y después de la llamada recursiva del método printFibonacciWithCondition .

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}

El programa nos da esta salida:

Aquí hay una visualización de lo que está sucediendo.

Digámoslo de nuevo: se llama al método printFibonacciWithCondition . Calcula el número actual. Si nos conviene, lo mostramos y llamamos al método printFibonacciWithCondition nuevamente con nuevos argumentos.

Siempre que se llame al método recursivo, esto se denomina "descenso recursivo". Cuando finaliza recursivamente y regresan las llamadas a métodos, decimos que la pila de llamadas se está "desenrollando".

La recursividad es un tema interesante en la programación. Para manejar mejor el material, cambiemos ligeramente nuestra tarea. La nueva tarea es generar, en orden descendente, todos los números de la serie de Fibonacci que no excedan Integer.MAX_VALUE . Ya hemos escrito todo el código necesario para esta tarea. Todo lo que queda es intercambiar el orden de mostrar el número actual y llamar al método recursivo. Es decir, en el primer ejemplo, el número calculado se mostró durante el "descenso", pero ahora necesitamos "descender hasta el fondo" y luego mostrar los números "en el camino de regreso". Y, por supuesto, en el método principal , intercambiamos los dos números iniciales de la secuencia (cero y uno) después de mostrarlos después de llamar al método recursivo. Para la legibilidad,método.

public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}

La salida será: