Una funzione ricorsiva ha iterazioni / cicli?

Hai frainteso la ricorsione: sebbene possa essere usata per sostituire l'iterazione, non è assolutamente necessario che la funzione ricorsiva non abbia iterazioni interne a se stessa.

L'unico requisito per una funzione da considerare ricorsiva è l'esistenza di un percorso di codice attraverso il quale si chiama, direttamente o indirettamente. Tutte le funzioni ricorsive corrette hanno anche un condizionale di qualche tipo, impedendo loro di "ricorrere verso il basso" per sempre.

La tua funzione ricorsiva è l'ideale per illustrare la struttura della ricerca ricorsiva con il backtracking. Inizia con il controllo della condizione di uscita row < n , e procede a prendere decisioni di ricerca sul suo livello di ricorsione (cioè selezionando una possibile posizione per il numero regina row ). Dopo ogni iterazione, viene fatta una chiamata ricorsiva per costruire sulla configurazione che la funzione ha trovato finora; alla fine, "scende" quando row raggiunge n nella chiamata ricorsiva che è n livelli profondi.

La struttura generale di una funzione ricorsiva è qualcosa del tipo:

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

Il testo che ho contrassegnato come /*recursive processing*/ potrebbe essere qualsiasi cosa. potrebbe includere un ciclo, se il problema da risolvere lo richiede, e potrebbe anche includere chiamate ricorsive a myRecursiveFunction .

Sicuramente puoi usare i loop in una funzione ricorsiva. Ciò che rende una funzione ricorsiva è solo il fatto che la funzione si chiama ad un certo punto nel suo percorso di esecuzione. Tuttavia, dovresti avere alcune condizioni per impedire chiamate di ricorsione infinite dalle quali la tua funzione non può tornare.

Le chiamate e i loop ricorsivi sono solo due modi / costrutti per implementare un calcolo iterativo.

Un ciclo while corrisponde a una chiamata ricorsiva in coda (vedi ad esempio qui ), cioè un'iterazione in cui non è necessario salvare i risultati intermedi tra due iterazioni (tutti i risultati di un ciclo sono pronti quando si accede al ciclo successivo). Se devi memorizzare risultati intermedi che puoi riutilizzare in un secondo momento, puoi utilizzare un ciclo while insieme a uno stack (vedi qui ), o una chiamata ricorsiva non ricorsiva (cioè arbitraria).

Molte lingue ti consentono di utilizzare entrambi i meccanismi e puoi scegliere quello che ti si addice meglio e persino mescolarli nel tuo codice. In linguaggi imperativi come C, C ++, Java, ecc. Normalmente usi un ciclo while o for quando non hai bisogno di uno stack, e usi le chiamate ricorsive quando hai bisogno di uno stack (usi implicitamente il tempo di esecuzione pila). Haskell (un linguaggio funzionale) non offre una struttura di controllo di iterazione, quindi puoi utilizzare solo le chiamate ricorsive per eseguire l'iterazione.

Nel tuo esempio (vedi i miei commenti):

// 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;
}

Hai ragione di pensare che esista una relazione tra ricorsione e iterazione o looping. Gli algoritmi ricorsivi sono spesso manualmente o addirittura convertiti automaticamente in soluzioni iterative mediante l'ottimizzazione della coda di chiamata.

In otto regine, la parte ricorsiva è relativa alla memorizzazione dei dati necessari per il tracciamento posteriore. Quando pensi alla ricorsione, è utile pensare a ciò che viene messo in pila. Lo stack può contenere parametri pass-value e variabili locali che svolgono un ruolo chiave nell'algoritmo, o talvolta roba che non è così apparentemente rilevante come l'indirizzo di ritorno o, in questo caso, un valore passato con il numero di regine che viene utilizzato ma non modificato dall'algoritmo.

L'azione che avviene in otto regine è che essenzialmente ci viene data una soluzione parziale per un certo numero di regine nelle prime colonne da cui, in modo iterativo, si determinano scelte valide fino ad ora nella colonna corrente che passiamo ricorsivamente per essere valutato per le colonne rimanenti. A livello locale, otto regine tengono traccia di quale riga sta tentando e se il tracciamento posteriore si verifica, è pronto per passare attraverso le righe rimanenti o per tornare indietro, semplicemente restituendo se non trova altre righe che potrebbero funzionare.

La parte "crea una versione ridotta del problema" può avere loop. Finché il metodo chiama se stesso passando come parametro la versione più piccola del problema, il metodo è ricorsivo. Ovviamente una condizione di uscita, quando viene risolta la versione più piccola possibile del problema e il metodo restituisce un valore, deve essere fornito per evitare una condizione di overflow dello stack.

Il metodo nella tua domanda è ricorsivo.

La ricorsività chiama di nuovo la funzione e il vantaggio principale della ricorsione è quello di risparmiare memoria. La ricorsione può avere loop in essa utilizzati per eseguire altre operazioni.