Modo generale per convertire un loop (while / for) in ricorsione o da una ricorsione ad un loop?

In realtà dovresti prima interrompere la funzione:

Un ciclo ha alcune parti:

1. l'intestazione e l'elaborazione di prima del ciclo. Può dichiarare alcune nuove variabili

2. la condizione, quando interrompere il ciclo.

3. il corpo del loop effettivo. Cambia alcune delle variabili dell'intestazione e / o i parametri passati.

4. la coda; cosa succede dopo il ciclo e restituisce il risultato.

O per scriverlo:

foo_iterative(params){
    header
    while(condition){
        loop_body
    }
    return tail
}

Utilizzare questi blocchi per effettuare una chiamata ricorsiva è piuttosto semplice:

foo_recursive(params){
    header
    return foo_recursion(params, header_vars)
}

foo_recursion(params, header_vars){
    if(!condition){
        return tail
    }

    loop_body
    return foo_recursion(params, modified_header_vars)
}

Et voilà; una versione ricorsiva della coda di qualsiasi loop. break s e continue s nel corpo del ciclo dovranno essere sostituiti con return tail e restituiti foo_recursion(params, modified_header_vars) in base alle esigenze, ma è abbastanza semplice.

Andare dall'altra parte è più complicato; in parte perché possono esserci più chiamate ricorsive. Ciò significa che ogni volta che popiamo uno stack frame ci possono essere più posti dove dobbiamo continuare. Inoltre ci possono essere variabili che dobbiamo salvare attraverso la chiamata ricorsiva e i parametri originali della chiamata.

Possiamo usare un interruttore per ovviare a questo:

bar_recurse(params){
    if(baseCase){
        finalize
        return
    }
    body1
    bar_recurse(mod_params)
    body2
    bar_recurse(mod_params)
    body3
}


bar_iterative(params){
    stack.push({init, params})

    while(!stack.empty){
        stackFrame = stack.pop()

        switch(stackFrame.resumPoint){
        case init:
            if(baseCase){
                finalize
                break;
            }
            body1
            stack.push({resum1, params, variables})
            stack.push({init, modified_params})
            break;
        case resum1:
            body2
            stack.push({resum2, params, variables})
            stack.push({init, modified_params})
            break;
        case resum2:
            body3
            break;
        }
    }
}

Seguendo la risposta di @ratchet freak, ho creato questo esempio di come la funzione Fibonacci può essere riscritta in un ciclo while in Java. Nota che c'è un modo molto più semplice (ed efficiente) per riscrivere il Fibonacci con un ciclo while.

class CallContext { //this class is similar to the stack frame

    Object[] args;

    List<Object> vars = new LinkedList<>();

    int resumePoint = 0;

    public CallContext(Object[] args) {
        this.args = args;
    }

}


static int fibonacci(int fibNumber) {
    Deque<CallContext> callStack = new LinkedList<>();
    callStack.add(new CallContext(new Object[]{fibNumber}));
    Object lastReturn = null; //value of last object returned (when stack frame was dropped)
    while (!callStack.isEmpty()) {
        CallContext callContext = callStack.peekLast();
        Object[] args = callContext.args;
        //actual logic starts here
        int arg = (int) args[0];
        if (arg == 0 || arg == 1) {
            lastReturn = arg;
            callStack.removeLast();
        } else {
            switch (callContext.resumePoint) {
                case 0: //calculate fib(n-1)
                    callStack.add(new CallContext(new Object[]{arg - 1}));
                    callContext.resumePoint++;
                    break;
                case 1: //calculate fib(n-2)
                    callContext.vars.add(lastReturn); //fib1
                    callStack.add(new CallContext(new Object[]{arg - 2}));
                    callContext.resumePoint++;
                    break;
                case 2: // fib(n-1) + fib(n-2)
                    callContext.vars.add(lastReturn); //fib2
                    lastReturn = (int) callContext.vars.get(0) + (int) callContext.vars.get(1);
                    callStack.removeLast();
                    break;
            }
        }
    }
    return (int) lastReturn;
}