Riscrivere una funzione ricorsiva senza ricorrere alla ricorsione

Sto riscrivendo un codice esistente in un'impostazione in cui le chiamate ricorsive non sono facilmente implementabili né desiderate. (E in Fortran 77, se devi saperlo.) Ho pensato di creare uno stack da zero per tenere traccia delle chiamate necessarie, ma questo mi sembra un po 'fasullo, e preferirei non allocare memoria a un array nei casi in cui il la ricorsione non è profonda. (Non sono sicuro che Fortran 77 supporti l'allineamento di array dinamici.)Riscrivere una funzione ricorsiva senza ricorrere alla ricorsione

Qualche altro suggerimento per una soluzione generale su come prendere una funzione ovviamente ricorsiva e riscriverla senza ricorsività senza sprecare spazio su una pila?

Molte grazie, Vecchio MCST

fonte

2010-12-12 Old McStopher

Se non si dirama, di solito è possibile riscriverlo in un ciclo semplice. Se si dirama di solito è necessario uno stack – CodesInChaos

@CodeInChaos: una funzione ricorsiva che non si dirama, per definizione, non restituirà mai ... –

Indovina che ho usato male la parola ramo. Intendo le chiamate più volte, quindi il grafico delle chiamate diventa un albero con rami. Ed è solo la mia esperienza e non sempre è vera. – CodesInChaos

Se il codice utilizza ricorsione di coda (vale a dire, la funzione restituisce il risultato di ogni chiamata ricorsiva direttamente senza qualsiasi altra elaborazione) allora è possibile riscrivere la funzione imperativamente senza una pila:

function dosomething(a,b,c,d) 
{ 
    // manipulate a,b,c,d 
    if (condition) 
    return dosomething(a,b,c,d) 
    else 
    return something; 
}

Into:

Senza ricorsione della coda, l'utilizzo di una pila (o di un deposito intermedio simile) è l'unica soluzione.

fonte

2010-12-12 14:17:42

Questo è simile a quello che stavo pensando, ma non potevo esprimere a parole. Quindi nel mio caso particolare, ho un insieme di elementi di dati che dovranno essere testati per una relazione con altri elementi dell'insieme. Potrei passare nella struttura dei dati di tutti gli articoli, ma dal momento che ognuno ha bisogno di ulteriore elaborazione, suppongo che lo stack sia inevitabile, sì? –

Depends.Se il codice è per lo più "per tutte le coppie (a, b) se P (a, b) è vero, allora esegui F (a, b)" puoi farla passare iterativamente attraverso tutte le coppie ... –

maggior parte delle funzioni ricorsive possono essere facilmente riscritto come loop, per sprecare spazio - che dipende dalla funzione, dal momento che molti (ma non tutti) ricorsiva algoritmi in realtà dipendono da questo tipo di archiviazione (sebbene, in questi casi, la versione del loop sia solitamente più efficiente).

fonte

2010-12-12 14:15:59 Ofir

Attenzione a mostrare una funzione ricorsiva che non richiede spazio sullo stack? Anche per i suoi argomenti? –

@Nikita Rybak: una funzione ricorsiva codificata in linea;) –

@Victor Sì, ma è in forma riscritta. E Ofir afferma che esiste una funzione ricorsiva che non richiede memoria di stack. Quindi, sono curioso. –

La funzione ricorsiva classico che può essere scritto come un ciclo è la funzione Fibonacci:

function fib(n) 
{ 
    // valid for n >= 0 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
}

Ma senza memoization questo richiede O (exp^N) operazioni con O (N) spazio dello stack.

Si può essere riscritta:

function fib(n) 
{ 
    if (n < 2) 
     return n; 
    var a = 0, b = 1; 
    while (n > 1) 
    { 
     var tmp = a; 
     a = b; 
     b = b + tmp; 
     n = n - 1; 
    } 
    return b; 
}

ma ciò comporta la conoscenza di come funziona la funzione, non è sicuro se può essere generalizzato a un processo automatico.

fonte

2010-12-12 16:51:54

Riscrivere una funzione ricorsiva senza ricorrere alla ricorsione

risposta

Problemi correlati