Eliminazione della ricorsione

Question

Eliminazione della ricorsione

Naviga le tue risposte

#1 da (4 voti)

0

È facile eliminare la ricorsione della coda.

Ci sono alcuni casi curiosi in cui la ricorsione non-coda può anche essere eliminata.

Esposizione 1: numeri di Fibonacci.

Una soluzione ricorsiva ingenua
```
fib(n)
    if (n < 2)
        return n
    return fib(n-1) + fib(n-2)
```
porta a complessità esponenziale. Una soluzione iterativa
```
fib(n)
   f_0 = 0
   f_1 = 1
   for i = 2; i < n; ++i
       f = f_0 + f1
       f_0 = f1
       f_1 = f
   return f
```
è lineare. So che posso avere uno logaritmico, ma è oltre il punto.

Allegato 2: unisci l'ordinamento

Una soluzione ricorsiva

merge_sort(begin, end)
    mid = begin + (end - begin)
    merge_sort(begin, mid)
    merge_sort(mid, end)
    merge(begin, mid, end)

(che non è così male come mostra 1, ma ancora) consente anche una versione iterativa:

merge_sort(begin, end)
    for stride = 2; stride < end - begin; stride *= 2
        for start = begin; start < end; start += stride
            merge(start, start + stride/2, start + stride)

Queste mostre apparentemente non correlate condividono un tratto comune: non c'è lavoro svolto sulla via ¹.

Le vere domande sono,

questa caratteristica garantisce che l'eliminazione è possibile,
è possibile identificarlo e
una volta identificato, c'è un modo meccanico per eliminare effettivamente la ricorsione.

Dichiarazione di non responsabilità: mi interessa solo l'eliminazione senza usare uno stack. So che è sempre possibile eliminare la ricorsione introducendo una pila come mostrato in Modo generale per convertire un ciclo (while / for) in ricorsione o da una ricorsione a un ciclo?

[1] Nessuno ci derubare andando giù per la montagna. Non abbiamo soldi andando giù per la montagna. Quando abbiamo i soldi, sulla via del ritorno, allora puoi sudare.

recursion

posta user58697 22.04.2017 - 08:40

fonte

1 risposta

Leggi altre domande sui tag recursion

Avvolgere un processo shell per manipolare un file system, come migliorare la progettazione? Microservizi livello di dettaglio

score 4 · Accepted Answer

does this trait [no job done on the way down] warrant that elimination is possible,

No. Un semplice esempio: visitando un albero binario in ordine di post: nessun lavoro viene eseguito mentre si scende, ma è necessario uno stack (ci sono modi per codificare lo stack nell'albero modificando temporaneamente l'albero, ma lo stack è fondamentalmente lì ).

Tuttavia, ci sono modi per rimuovere le ricorsioni non terminali senza usare uno stack. Ma quelli che conosco stanno usando proprietà aggiuntive, e in particolare quella che alcune operazioni possono essere eseguite in un altro ordine rispetto a quello utilizzato per la versione ricorsiva. Questo è vero per il tuo esempio di Fibonacci (dove stai anche usando il fatto che alcune operazioni sono ridondanti) e la tua fusione ne ordina una. Rilevare che questa proprietà sia valida può essere difficile (potrebbe cambiare la stabilità e le caratteristiche di errore di un algoritmo in virgola mobile, ad esempio).

Almeno due di questi sono abbastanza sistematici da consentire ai compilatori di implementarli (so che il primo è stato implementato nei compilatori).

l'introduzione dei parametri dell'accumulatore. Alcuni casi di ricorsione non terminale possono essere trasformati in una ricorsione terminale introducendo parametri aggiuntivi e utilizzando l'associatività dell'operazione ancora da eseguire. È il caso di una funzione ricorsiva fattoriale o di lunghezza lista:
```
int len(list l) {
    if (l == NIL)
        return 0;
    else
        return 1 + len(tail(l));
}
```
può essere sostituito con
```
int len_aux(list l, int acc) {
    if (l == NIL)
        return acc;
    else
        return len_aux(tail(l), acc+1);
}

int len(list l) {
    return len_aux(l, 0);
}
```
Ci sono algoritmi che mostrano come fare automaticamente.
la tecnica successiva che ho usato (ma non ricordo di aver visto descritto nel contesto di un passaggio di ottimizzazione per un compilatore) sta usando la memoizzazione come passaggio intermedio (e quindi è valido solo per la pura funzione) . Si consideri che si sta memorizzando nella cache il risultato della funzione in una tabella indicizzata con i suoi parametri e poi si vede che la tabella può essere calcolata in un altro ordine, a volte riducendo il numero di valori che devono essere mantenuti. Questo metodo sarebbe applicabile al tuo programma Fibonacci.

Essere in grado di rimuovere la ricorsione per l'esempio di fusione è ancora più complesso: non è una funzione pura ma una che modifica lo stato. Puoi pensare e dedurre che è possibile cambiare l'ordine delle operazioni per renderle adatte a un'implementazione non ricorsiva senza bisogno di uno stack, ma una descrizione così piccola può essere utile per un umano, espandendola a un algoritmo da implementare in un compilatore sarebbe necessario un lavoro aggiuntivo.