Uma função recursiva pode ter iterações / loops?

Eu estudei sobre funções recursivas e, aparentemente, são funções que se autodenominam e não usam iterações / loops (caso contrário, não seria uma função recursiva).

No entanto, enquanto navegava na Web por exemplos (o problema recursivo de 8 rainhas), encontrei esta função:

private boolean placeQueen(int rows, int queens, int n) {
    boolean result = false;
    if (row < n) {
        while ((queens[row] < n - 1) && !result) {
            queens[row]++;
            if (verify(row,queens,n)) {
                ok = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Há um whileloop envolvido.

... então estou um pouco perdido agora. Posso usar loops ou não?

Você entendeu errado a recursão: embora possa ser usada para substituir a iteração, não há absolutamente nenhum requisito para a função recursiva não ter iterações internas a si mesma.

O único requisito para uma função ser considerada recursiva é a existência de um caminho de código pelo qual ela se chama, direta ou indiretamente. Todas as funções recursivas corretas também têm algum tipo de condição, impedindo-as de "recursarem para baixo" para sempre.

Sua função recursiva é ideal para ilustrar a estrutura da pesquisa recursiva com retorno. Começa com a verificação da condição de saída row < ne passa a tomar decisões de busca em seu nível de recursão (ou seja, escolher uma posição possível para o número da rainha row). Após cada iteração, é feita uma chamada recursiva para criar a configuração que a função encontrou até agora; eventualmente, " rowatinge no nfundo do poço " quando alcança a chamada recursiva com níveis profundos.

A estrutura geral de uma função recursiva é algo como isto:

myRecursiveFunction(inputValue)
begin
   if evaluateBaseCaseCondition(inputValue)=true then
       return baseCaseValue;
   else
       /*
       Recursive processing
       */
       recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
       return recursiveResult;
   end if
end

O texto que marquei como /*recursive processing*/poderia ser qualquer coisa. Ele poderia incluir um loop, se o problema a ser resolvido o exige, e também poderia incluir chamadas recursivas para myRecursiveFunction.

Você certamente pode usar loops em uma função recursiva. O que torna uma função recursiva é apenas o fato de a função se chamar em algum momento de seu caminho de execução. No entanto, você deve ter alguma condição para impedir chamadas de recursão infinitas das quais sua função não pode retornar.

Chamadas e loops recursivos são apenas duas maneiras / construções para implementar uma computação iterativa.

Um whileloop corresponde a uma chamada recursiva de cauda (veja, por exemplo, aqui ), ou seja, uma iteração na qual você não precisa salvar resultados intermediários entre duas iterações (todos os resultados de um ciclo estão prontos quando você entra no próximo ciclo). Se você precisar armazenar resultados intermediários que possam ser usados ​​novamente mais tarde, poderá usar um whileloop junto com uma pilha (veja aqui ) ou uma chamada recursiva não recursiva (ou seja, arbitrária).

Muitos idiomas permitem usar os dois mecanismos e você pode escolher o que melhor combina com você e até misturá-los no seu código. Em linguagens imperativas como C, C ++, Java etc., você normalmente usa a whileou forloop quando não precisa de uma pilha e usa chamadas recursivas quando precisa de uma pilha (você usa implicitamente a pilha de tempo de execução). O Haskell (uma linguagem funcional) não oferece uma estrutura de controle de iteração, portanto, você pode usar apenas chamadas recursivas para executar a iteração.

No seu exemplo (veja meus comentários):

// queens should have type int [] , not int.
private boolean placeQueen(int row, int [] queens, int n)
{
    boolean result = false;
    if (row < n)
    {
        // Iterate with queens[row] = 1 to n - 1.
        // After each iteration, you either have a result
        // in queens, or you have to try the next column for
        // the current row: no intermediate result.
        while ((queens[row] < n - 1) && !result)
        {
            queens[row]++;
            if (verify(row,queens,n))
            {
                // I think you have 'result' here, not 'ok'.
                // This is another loop (iterate on row).
                // The loop is implemented as a recursive call
                // and the previous values of row are stored on
                // the stack so that we can resume with the previous
                // value if the current attempt finds no solution.
                result = placeQueen(row + 1,queens,n);
            }
        }
        if (!result) {
            queens[row] = -1;
        }
    }else{
        result = true;
    }
    return result;
}

Você está certo ao pensar que existe uma relação entre recursão e iteração ou loop. Os algoritmos recursivos geralmente são convertidos manualmente ou mesmo automaticamente em soluções iterativas usando a otimização de chamada de cauda.

Em oito rainhas, a parte recursiva está relacionada ao armazenamento de dados necessários para o rastreamento posterior. Quando você pensa em recursão, é valioso pensar sobre o que é colocado na pilha. A pilha pode conter parâmetros de passagem por valor e variáveis ​​locais que desempenham um papel fundamental no algoritmo, ou às vezes coisas que não são aparentemente tão relevantes como o endereço de retorno ou, nesse caso, um valor passado com o número de rainhas usadas, mas não alterado pelo algoritmo.

A ação que ocorre em oito rainhas é que, essencialmente, nos é dada uma solução parcial para um número de rainhas nas primeiras colunas, a partir das quais determinamos iterativamente as escolhas válidas até o momento na coluna atual que passamos recursivamente para ser avaliada para o colunas restantes. Localmente, oito rainhas rastreiam qual linha está tentando e, se o rastreamento posterior ocorrer, ele está pronto para percorrer as linhas restantes ou para rastrear ainda mais, simplesmente retornando se não encontrar outra linha que possa funcionar.

A parte "criar uma versão menor do problema" pode ter loops. Enquanto o método se chamar passando como parâmetro a versão menor do problema, o método será recursivo. Obviamente, uma condição de saída, quando a menor versão possível do problema for resolvida e o método retornar um valor, deverá ser fornecida para evitar uma condição de estouro de pilha.

O método na sua pergunta é recursivo.

A recursão basicamente chama sua função novamente e a principal vantagem da recursão é economizar memória. A recursão pode ter loops, pois eles são usados ​​para executar alguma outra operação.