condições de saída. erro de estouro de pilha

Exemplo de código recursivo sem condição de saída

Vamos dar outra olhada em um problema recursivo. Como exemplo, considere o cálculo dos números de Fibonacci. Todos devem se lembrar que a sequência de Fibonacci é uma sequência numérica na qual os dois primeiros números são 0 e 1, e cada número subseqüente é igual à soma dos dois números anteriores.

Vamos escrever um código para calcular e exibir esses 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 da primeira chamada do método printFibonacci recursivo , imprima os dois primeiros números da sequência: zero e um. Precisamos fazer isso porque o método recursivo exibe apenas a soma dos parâmetros de entrada, não os próprios parâmetros.

O código parece bom: obtemos dois números, calculamos sua soma, imprimimos no console e chamamos o método printFibonacci recursivamente novamente. Passamos o número anterior (anterior) e o número atual (atual) como argumentos.

Na verdade, o código tem dois erros. Você pode vê-los se executar o código.

O primeiro erro está transbordando o tipo longo . O 104º número em nossa sequência é negativo, indicando que o tipo long estourou.

O segundo erro é diferente. Depois de calcular cerca de 12.000 números, obtemos:

Agora é um momento apropriado para relembrar o que é uma pilha de chamadas de método em Java. A máquina Java mantém um registro de todas as chamadas de função. Para fazer isso, ele usa um tipo especial de coleção chamado pilha. Quando uma função chama outra, a máquina Java coloca um novo StackTraceElement na pilha. Quando a função termina, esse elemento é removido da pilha. Da mesma forma, a pilha sempre armazena informações atualizadas sobre o estado atual da pilha de chamada de função. A documentação do StackTraceElement diz que ele é "lançado quando ocorre um estouro de pilha porque um aplicativo recursa muito profundamente". Uma JVM em execução possui uma área especial de memória para armazenar a pilha de chamadas de método. O tamanho dessa área de memória depende das configurações do sistema operacional e da JVM. Além da própria pilha de chamadas de método, as variáveis ​​primitivas (valores específicos dos parâmetros do método) e os endereços das variáveis ​​de referência (em uma área de memória chamada "heap") são armazenados nesta área de memória especial. O acesso à pilha de chamadas segue o princípio LIFO.

Exemplo corrigido com uma condição de saída

Vamos começar corrigindo o segundo problema no código.

Vamos tentar resolver o problema de frente: se a pilha for muito pequena, vamos aumentá-la. Para fazer isso, inicie a JVM com o sinalizador "-Xss" e especifique quanta memória alocar para a pilha. Vamos tentar alocar 5 megabytes. É assim que ficará no IDEA:

Conseguimos aumentar o comprimento da saída. Agora pode calcular mais de 49.000 números da sequência, em vez de se limitar a cerca de 12.000 números. Mas, em algum momento, ainda obtemos um StackOverflowError .

Você pode tentar aumentar o tamanho da pilha, mas isso não resolve o problema fundamental. Então, vamos procurar um problema de lógica. Deve haver um ponto em que a recursão para. Em outras palavras, deve haver alguma condição que determine quando o método recursivo não será mais chamado, permitindo que a pilha de chamadas se desenrole. Para definir tal condição, vamos deixar nosso objetivo explícito: exibir a série de Fibonacci desde que seus números sejam menores que Integer.MAX_VALUE .

Vamos escrever um novo método printFibonacciWithCondition que levará em consideração essa condição. E chamaremos o novo método corrigido no 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);
    }
}

Depois de executar o código, vemos que a saída termina com o número 1836311903. O número anterior a este é 1134903170. A soma desses números é 2_971_215_073, que é realmente maior que Integer.MAX_VALUE (2_147_483_647 ) .

Essa alteração corrigiu automaticamente o bug de estouro longo . Se você precisar calcular mais da série, precisará usar outros tipos de dados, como BigInteger .

Descida recursiva e desenrolamento

Vamos analisar passo a passo como nosso código é executado. Para fazer isso, vamos adicionar um método echo e chamá-lo antes e depois da chamada recursiva do 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);
        }
    }
}

O programa nos dá esta saída:

Aqui está uma visualização do que está acontecendo.

Vamos repetir: o método printFibonacciWithCondition é chamado. Ele calcula o número atual. Se for conveniente, exibimos e chamamos o método printFibonacciWithCondition novamente com novos argumentos.

Enquanto o método recursivo estiver sendo chamado, isso é chamado de "descida recursiva". Quando o recursivo termina e as chamadas de método retornam, dizemos que a pilha de chamadas está "desenrolando".

Recursão é um tópico interessante em programação. Para entender melhor o material, vamos mudar um pouco nossa tarefa. A nova tarefa é gerar, em ordem decrescente, todos os números da série Fibonacci que não excedam Integer.MAX_VALUE . Já escrevemos todo o código necessário para esta tarefa. Tudo o que resta é trocar a ordem de exibição do número atual e chamar o método recursivo. Ou seja, no primeiro exemplo, o número calculado foi exibido durante a "descida", mas agora precisamos "descer até o fundo" e depois exibir os números "no caminho de volta". E claro, no método main , trocamos os dois números iniciais da sequência (zero e um) após exibi-los após chamarmos o método recursivo. Para facilitar a leitura,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);
    }
}

A saída será: