Problema sulla ricorsione

Question

Problema sulla ricorsione

#1 da (3 voti)

-2

void function(int x){
    if(x<=0)
        return;
    function(x--);
}

Questa è una funzione di ricorsione chiamata con il valore di x = 20.

La chiamata ricorsiva avverrà in questo modo

function(20)...function(19).......function(0)

Ogni chiamata di funzione userà un po 'di memoria e se i dati sono grandi genererà StackOverflowException.

Quindi quello che voglio sapere è:
C'è un modo in cui possiamo chiamare una funzione e rimuoverla dallo stack di chiamata in modo che la sua memoria possa essere utilizzata (ad esempio dopo la funzione (20) chiama function (19) la memoria per la funzione (20) dovrebbe essere deselezionata ), e la fine della chiamata ricorsiva (qui function (0)) dovrebbe essere restituita dal primo posto da dove è stata chiamata (es. function (20)).

Questo può essere fatto in Java e C?

recursion java c control-flow

posta Amit Aswal 15.01.2016 - 10:51

fonte

1 risposta

Leggi altre domande sui tag recursion java c control-flow

Programmatori fullstack e web design [chiuso] Domanda sull'istruzione switch-case [chiusa]

score 3 · Accepted Answer

Quello che hai qui è un Tail Call, e ancora di più, è Tail Recursion ( Direct Tail Recursion ) per essere precisi.

Molte lingue hanno chiamate di coda corrette (ad esempio Schema, ECMAScript) e anche più lingue hanno una corretta ricorsione di coda (ad esempio Scala, almeno per la ricorsione a coda diretta). Sfortunatamente, né C né Java supportano le Tail Tail Calls o anche la molto più corretta corretta ricorsione della coda, quindi, per valori sufficientemente grandi di x , farà saltare lo stack, non c'è modo di aggirarlo.

Ovviamente, hai un bug nel tuo codice che porta alla ricorsione infinita, il che significa che anche se hai una corretta ricorsione della coda, il tuo programma funzionerà per un tempo infinito.

Le giuste chiamate di coda hanno la semantica di una chiamata di subroutine ma le prestazioni di tempo e spazio di un GOTO (perché sono in effetti equivalenti a un GOTO e spesso vengono implementate in quel modo). La corretta ricorsione della coda, quindi, è ovviamente equivalente a un GOTO indietro all'inizio della subroutine. O, in altre parole, un ciclo.

Quindi, se la tua lingua ha loop, ma non Direct Tail Recursion, puoi sempre sostituire Direct Tail Recursion con un loop con le stesse prestazioni di spazio e tempo, ma perdendo le proprietà di sicurezza e leggibilità di una chiamata di subroutine.