Como o retrocesso recursivo funciona?

5

Eu estou tentando descobrir back recacking recursivo, eu tenho uma boa compreensão da recursão e até certo ponto o conceito de retrocesso também, mas eu estou tendo dificuldade em entender a ordem cronológica de como as coisas estão funcionando quando o loop está sendo usado no código a seguir .

public static void diceRolls(int dice) { 
    List<Integer> chosen = new ArrayList<Integer>(); 
    diceRolls(dice, chosen); 
} 

// private recursive helper to implement diceRolls logic 
private static void diceRolls(int dice,List<Integer> chosen) { 
     if (dice == 0) { 
          System.out.println(chosen); // base case 
       } else { 
          for (int i = 1; i <= 6; i++) { 
               chosen.add(i); // choose 
               diceRolls(dice - 1, chosen); // explore 
               chosen.remove(chosen.size() - 1); // un-choose 
      } 
  } 
}

Agora eu estou tendo problema entender que por exemplo passamos 3 na função diceRolls, ele chama o método auxiliar, dentro do loop for adicionamos todo o valor de i (ie 1) depois que ele chama o método novamente para loop completo antes de recursing ou o método diceRolls (2, escolhido) é passado agora? Porque se 2 for passado, então o loop só será executado uma vez antes de se recorrer.

    
por Karan Singla 02.09.2015 / 20:30
fonte

4 respostas

7

Você pode retroceder como se estivesse andando por uma masmorra e deve explorar todos os caminhos da masmorra (a masmorra é acíclica - você nunca voltará ao mesmo lugar, independentemente do caminho que escolher). Quando você chega a um lugar que se bifurca em vários caminhos, escolhe apenas um e segue-o. Só depois de chegar ao fim, você volta para o último garfo e escolhe o próximo caminho. Quando você explorou todos os caminhos, você volta para a bifurcação anterior e repete até voltar ao início da masmorra.

No código, o for cycle é como a bifurcação na masmorra (neste caso com 6 caminhos diferentes onde você pode continuar), a chamada recursiva para diceRolls representa a escolha de um dos caminhos possíveis, o fim de uma masmorra é quando você para a recursão (você não para a execução, você apenas volta um passo atrás). Toda vez que você pula para fora da função diceRolls, você continua com o loop for e chama diceRolls novamente.

Você acaba com a interrupção do loop for por uma chamada recursiva na primeira iteração no começo, imprimindo 111, depois dando um passo para trás e continuando o loop você terá 112, depois 113, ... 116, e você volta um passo para trás e pega 121, 122, 123, ... até chegar a 661, 662, 666. Nesse ponto todos os seus loops e chamadas recursivas terminam e o cálculo termina.

    
por 02.09.2015 / 21:44
fonte
1

Tente executar o seguinte:

public static void diceRolls(int dice) { 
    List<Integer> chosen = new ArrayList<Integer>(); 
    diceRolls(dice, chosen); 
} 

// private recursive helper to implement diceRolls logic 
private static void diceRolls(int dice,List<Integer> chosen) {
System.out.println("Entering diceRolls with dice="+dice); 
     if (dice == 0) { 
          System.out.println(chosen); // base case 
       } else { 
          for (int i = 1; i <= 6; i++) {
               System.out.println("Starting for loop. i="+i+", dice="+dice); 
               chosen.add(i); // choose 
               diceRolls(dice - 1, chosen); // explore 
               chosen.remove(chosen.size() - 1); // un-choose 
               System.out.println("Ending for loop. i="+i+", dice="+dice);
           }
           System.out.println("Exiting diceRolls with dice="+dice); 
       }
}

Para cada iteração do loop for, uma nova chamada será feita para diceRolls (int dados, Lista escolhida) com dados sendo um a menos do que era antes. Se os dados não forem iguais a 0, essa nova chamada resultará em mais seis chamadas sendo feitas.

A idéia de retrocesso é que você deseja executar uma pesquisa aprofundada em todas as soluções possíveis para um problema. Digamos que você esteja tentando lançar um dado N vezes e esteja tentando aumentar os números para cada jogada. Deixe [1,2,3] denotar um rolo de 1, em seguida, 2, em seguida, 3. Seu estado inicial do problema será [], sem que nenhum teste seja executado ainda. Você pode lançar um dado padrão de seis maneiras diferentes, e assim, após o seu primeiro lançamento, você terá [1], [2], [3], [4], [5], [6]. Para cada um desses estados, você pode lançar um dado e uma adição de seis maneiras para um total de 36 estados possíveis: [1,1], [1,2], [1,3], [1,4], [1 , 5], [1,6], [2,1], [2,2] ... [6,5], [6,6]. No entanto, podemos "remover" estados que já são inválidos, como [2,1] e [6,5], pois eles não estão aumentando as jogadas. Desta forma, podemos realizar uma mudança de adição para cada solução parcial do problema até obtermos todas as soluções possíveis para um problema, podando a cada passo para reduzir o tamanho do problema.

    
por 02.09.2015 / 21:51
fonte
1

A resposta de OndreJM está no ponto. Apenas para adicionar um pouco de magia diagramatic, considere um programa fatorial recursivo simples e siga o fluxograma.

    
por 06.09.2015 / 11:55
fonte
-1

Basta seguir linha por linha, e quando você apertar uma chamada de função, imagine copiar e colar a totalidade desse código de função em seu lugar.

Portanto, o chosen.remove () será chamado depois que as chamadas da função anterior tiverem terminado e, portanto, as outras escolhidas.remove serão chamadas antes dele.

Google como usar um depurador colocar intervalos em seu trabalho e, em seguida, encontrar o que as variáveis são em diferentes pontos do seu código vai ajudar sua compreensão muito mais do que tentar conseguir alguém para explicá-lo.

    
por 02.09.2015 / 20:46
fonte