Ricorsione Allocazione di memoria VS [duplicato]

Question

Ricorsione Allocazione di memoria VS [duplicato]

#1 da (0 voti)

-1

Quale approccio è più popolare negli esempi del mondo reale: ricorsione o iterazione?

Ad esempio, semplice attraversamento del preordine dell'albero con ricorsione:

void preorderTraversal( Node root ){
    if( root == null ) return;
    root.printValue();
    preorderTraversal( root.getLeft() );
    preorderTraversal( root.getRight() );
}

e con iterazione (usando lo stack):

Push the root node on the stack
While the stack is not empty
    Pop a node
    Print its value
    If right child exists, push the node's right child
    If left child exists, push the node's left child

Nel primo esempio abbiamo chiamate di metodo ricorsive, ma nella seconda - nuova struttura di dati ausiliari.

La complessità è simile in entrambi i casi: O (n). Quindi, la domanda principale è il requisito dell'impronta di memoria?

recursion memory-usage

posta Vladimir Kishlaly 05.06.2014 - 11:31

fonte

1 risposta

Leggi altre domande sui tag recursion memory-usage

c'è un modo per lasciare notificaManager e alarmManger attivi anche quando l'app è chiusa? Tree View Indicatore condizione bambini sul genitore non espanso più in alto

score 0 · Answer 1

Nel caso di discendere una struttura ricorsiva come un albero, i requisiti di memoria sono dello stesso ordine usando la ricorsione o l'iterazione (proporzionale alla profondità).

Probabilmente è un po 'più economico usare l'iterazione poiché non devi tenere traccia dei telai dello stack e ottieni anche la flessibilità aggiuntiva di poter scegliere la profondità massima della ricorsione (alcune lingue hanno dimensioni di stack di chiamata finite).

Detto questo, è abbastanza dipendente dalla lingua in quanto dipende dall'ottimizzazione della ricorsione in coda e dal fatto che i frame dello stack siano tracciati. In alcune lingue, l'esempio ricorsivo può essere ottimizzato nella forma iterativa equivalente.

In generale, per le lingue in cui è possibile l'iterazione, la ricorsione costa almeno la quantità di memoria di quella iterativa.