Che cosa è la ricorsività?

Question

Mentre a partire da imparare lisp, ho incontrato il termine tail-ricorsiva.Che cosa significa esattamente?

Answer 1

Si consideri una semplice funzione che aggiunge i primi N numeri interi.(ad es. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Ecco una semplice implementazione di JavaScript che usa la ricorsione:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Se hai chiamato recsum(5), questo è ciò che l'interprete JavaScript di valutare:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Si noti come ogni chiamata ricorsiva deve completare prima l'interprete JavaScript inizia effettivamente fare il lavoro di calcolare la somma.

Ecco una coda-versione ricorsiva della funzione stessa:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Ecco la sequenza di eventi che si verificano se si chiama tailrecsum(5), (che sarebbe effettivamente tailrecsum(5, 0), a causa del default secondo argomento).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Nel tail-ricorsiva caso, con ogni valutazione della chiamata ricorsiva, il running_total viene aggiornato.

Nota:L'originale di risposta utilizzato esempi da Python.Questi sono stati modificati per JavaScript, dato che le moderne JavaScript interpreti di supporto coda di chiamata ottimizzazione ma Python interpreti non.

Answer 2

In tradizionale ricorsione, il modello tipico è che si esegue il vostro chiamate ricorsive prima, e poi si prende il valore di ritorno della chiamata ricorsiva e calcolare il risultato.In questo modo, non si ottiene il risultato del calcolo fino a quando sei tornato da ogni chiamata ricorsiva.

In ricorsività, eseguire i calcoli prima, e quindi si esegue la chiamata ricorsiva, passando per i risultati del passaggio di corrente per il prossimo passo ricorsivo.Questo si traduce nell'ultima dichiarazione in forma di (return (recursive-function params)). In sostanza, il valore di ritorno di un dato ricorsiva passo è lo stesso come il valore di ritorno della prossima chiamata ricorsiva.

La conseguenza di questo è che una volta che si è pronti per eseguire il vostro prossimo passo ricorsivo, non hai bisogno di stack frame corrente più.Questo permette un certo livello di ottimizzazione.Infatti, con un'scritto appositamente compilatore, non si dovrebbe mai avere un overflow dello stack sogghigno con una coda di chiamata ricorsiva.Semplicemente riutilizzare lo stack frame corrente per il prossimo passo ricorsivo.Sono abbastanza sicuro che il Lisp non questo.

Answer 3

Un punto importante è che la coda di ricorsione è sostanzialmente equivalente a ciclo continuo.Non è solo una questione di ottimizzazione del compilatore, ma un dato fondamentale per l'espressività.Questo vale in entrambi i modi:si può prendere qualsiasi ciclo di forma

while(E) { S }; return Q

dove E e Q sono espressioni e S è una sequenza di istruzioni, e di trasformarlo in una coda di funzione ricorsiva

f() = if E then { S; return f() } else { return Q }

Naturalmente, E, S, e Q devono essere definiti per calcolare alcune interessanti valore di alcune variabili.Per esempio, il ciclo di funzione

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

è equivalente al tail-recursive function(s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Questo "involucro" della coda-funzione ricorsiva di una funzione con un numero inferiore di parametri è un funzionale comune idioma.)

Answer 4

Questo estratto dal libro Programmare in Lua mostra come fare una coda corretta ricorsione (in Lua, ma si dovrebbe applicare per Lisp) e perché è meglio.

Un coda di chiamata [ricorsività] è una sorta di goto vestito come una chiamata.Una coda di chiamata accade quando un chiamate di funzione e la sua ultima l'azione, quindi, non ha niente altro da fare.Per esempio, nel codice seguente, la chiamata a g è una coda di chiamata:

function f (x)
  return g(x)
end

Dopo f chiamate g, non ha niente altro fare.In tali situazioni, il programma non è necessario tornare alla chiamata funzione quando la funzione chiamata le estremità.Pertanto, dopo la coda di chiamata, il programma non ha bisogno di tenere qualsiasi informazioni sulla funzione di chiamata nella pila....

Perché una corretta coda di chiamata non utilizza spazio di stack, non c'è limite alla numero di "nested" coda di chiamate che un il programma può fare.Per esempio, siamo in grado di chiamare la funzione seguente, con qualsiasi numero come argomento;non sarà mai overflow dello stack:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

...Come ho detto in precedenza, una coda di chiamata è un tipo di goto.Come tale, molto utile applicazione di un corretto coda chiamate in Lua è per la programmazione di macchine a stati.Applicazioni di questo tipo possono rappresentare ogni stato da parte di una funzione;per cambiare stato è quello di andare a (o a chiamata) una specifica funzione.Come esempio, cerchiamo di si consideri un semplice gioco del labirinto.Il labirinto dispone di diverse sale, ognuna con un massimo di quattro porte:nord, sud, est, e a ovest.Ad ogni passo, l'utente entra in un direzione di movimento.Se c'è una porta in tale direzione, l'utente va a il corrispondente in camera;in caso contrario, il programma stampa un messaggio di avviso.L'obiettivo è per andare da una stanza iniziale e finale camera.

Questo gioco è una tipica macchina di stato, dove la corrente in camera è stato.Siamo in grado di realizzare tale labirinto, con una funzione per ogni camera.Noi di coda chiamate a muoversi da una stanza all' un altro.Un piccolo labirinto con quattro camere potrebbe assomigliare a questo:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Quindi, come vedi, quando si effettua una chiamata ricorsiva come:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Questo non è ricorsiva di coda, perché hai ancora cose da fare (add 1) in funzione dopo la chiamata ricorsiva è fatto.Se si immette un numero molto elevato sarà probabilmente causare un overflow dello stack.

Answer 5

L'uso regolare di ricorsione, ogni chiamata ricorsiva spinge un altro ingresso sul stack di chiamate.Quando la ricorsione è completato, l'app ha anche la pop ogni voce fuori tutto il percorso di discesa.

Con ricorsività, a seconda della lingua che il compilatore può essere in grado di far crollare la pila giù a una voce, in modo da risparmiare spazio di stack...Un grande query ricorsiva può effettivamente causare un overflow dello stack.

Fondamentalmente Coda ricorsioni sono in grado di essere ottimizzato nell'iterazione.

Answer 6

Invece di spiegare con le parole, ecco un esempio.Questo è un Regime versione della funzione fattoriale:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Qui è una versione di fattoriale che è il tail-ricorsiva:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Si noterà che nella prima versione che la chiamata ricorsiva di fatto è immessa nella moltiplicazione di espressione, e quindi lo stato deve essere salvato sullo stack quando si effettua la chiamata ricorsiva.In coda-versione ricorsiva non c'è nessun altro S-espressione di attesa per il valore della chiamata ricorsiva, e dal momento che non c'è più lavoro da fare, lo stato non deve essere salvato sullo stack.Come regola generale, Schema di coda-funzioni ricorsive uso costante di spazio di stack.

Answer 7

Jargon file ha questo da dire circa la definizione di ricorsività:

ricorsività /n./

Se non si è malati di già, vedere ricorsività.

Answer 8

Ricorsività si riferisce la chiamata ricorsiva essere l'ultima logica di istruzione algoritmo ricorsivo.

In genere in ricorsione, si dispone di una di base, in caso che è quello che impedisce che le chiamate ricorsive e comincia a saltar lo stack di chiamate.Per usare un esempio classico, anche se più C-ish di Lisp, la funzione fattoriale illustra ricorsività.La chiamata ricorsiva si verifica dopo il controllo della base caso la condizione.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

La chiamata iniziale per il fattoriale sarebbe factorial(n) dove fac=1 (valore di default) e n è il numero per il quale il fattoriale di calcolo.

Answer 9

Ciò significa che, piuttosto che dover spingere il puntatore all'istruzione in pila, si può semplicemente saltare verso l'alto di una funzione ricorsiva e continuare l'esecuzione.Questo consente per le funzioni di recurse a tempo indeterminato senza inondare la pila.

Ho scritto un blog post sull'argomento, che ha esempi grafici di ciò che il frame dello stack simile.

Answer 10

Qui di seguito un breve frammento di codice a confronto due funzioni.Il primo è il tradizionale ricorsione per trovare il fattoriale di un numero dato.Il secondo utilizza la ricorsione di coda.

Molto intuitiva e semplice da capire.

Un modo semplice per dire se una funzione ricorsiva è un tail ricorsiva è se restituisce un valore concreto nel caso base.Il che significa che non restituisce 1 o vera o qualcosa di simile.Sarà più che probabile ritorno qualche variante di uno dei parametri del metodo.

Un altro modo è quello di dire è che se la chiamata ricorsiva è privo di qualsiasi aggiunta, l'aritmetica, la modifica, ecc...Significato del suo nulla, ma un puro chiamata ricorsiva.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Answer 11

Il modo migliore per me per capire tail call recursion è un caso speciale di ricorsione in cui il ultima chiamata(o la coda di chiamata) è la funzione stessa.

Confrontando gli esempi forniti in Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^La RICORSIONE

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^RICORSIVITÀ

Come si può vedere in generale versione ricorsiva, la chiamata finale del blocco di codice è x + recsum(x - 1).Così, dopo aver chiamato il recsum metodo, c'è un'altra operazione che è x + ...

Tuttavia, nella versione ricorsiva di coda, l'ultima chiamata(o la coda di chiamata) nel blocco di codice è tailrecsum(x - 1, running_total + x) il che significa che l'ultima chiamata al metodo e nessuna operazione dopo che.

Questo punto è importante perché ricorsività come si vede qui non è fare memoria crescere perché quando il sottostante VM vede una funzione che richiama se stessa in una coda di posizione (l'ultima espressione essere valutata in funzione), elimina lo stack frame corrente, che è conosciuta come la Coda di Chiamata di Ottimizzazione(TCO).

MODIFICA

NB.Tenete a mente che l'esempio sopra è scritto in Python cui runtime non supporta il TCO.Questo è solo un esempio per illustrare il punto.Il TCO è supportata in lingue come lo Schema, Haskell, ecc

Answer 12

In Java, ecco un possibile tail ricorsiva attuazione della funzione di Fibonacci:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Questo contrasta con la norma implementazione ricorsiva:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Answer 13

Qui è un Common Lisp esempio del fattoriale che utilizza tail-recursion.A causa dello stack meno la natura, si può eseguire follemente grande fattoriale calcoli ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

E poi per divertimento si potrebbe provare (format nil "~R" (! 25))

Answer 14

Io non sono un Lisp programmatore, ma penso che questo sarà di aiuto.

Fondamentalmente si tratta di uno stile di programmazione tale che la chiamata ricorsiva è l'ultima cosa da fare.

Answer 15

In breve, una ricorsività è la chiamata ricorsiva, come il ultimo istruzione in funzione così da non dover aspettare per la chiamata ricorsiva.

Quindi questa è una ricorsività cioèN(x - 1, p * x) è l'ultima istruzione della funzione in cui il compilatore è intelligente per capire che può essere ottimizzato per un ciclo for (fattoriale).Il secondo parametro p porta il prodotto intermedio valore.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Questo è il non-tail-ricorsiva modo di scrivere sopra funzione fattoriale (anche se alcuni compilatori C++ può essere in grado di ottimizzare in ogni caso).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

ma questo non è:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Ho scritto un lungo post intitolato "Comprensione Ricorsività – Visual Studio C++ – Assemblea Vista"

Answer 16

qui è un Perl 5 versione del tailrecsum funzione accennato in precedenza.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 17

Questo è un estratto da La struttura e l'Interpretazione dei Programmi per Computer sulla ricorsività.

In contrasto iterazione e ricorsione, dobbiamo essere attenti a non confondere la nozione di un processo ricorsiva con la nozione di procedura ricorsiva.Quando descriviamo una procedura ricorsiva, ci sono riferendosi al sintattica fatto che la procedura di definizione si riferisce (direttamente o indirettamente) alla procedura stessa.Ma quando ci descrivere il processo segue un modello che è, diciamo, in modo lineare ricorsiva, stiamo parlando di come il processo si evolve, non la sintassi di come una procedura scritta.Può sembrare inquietante che ci riferiamo ad una procedura ricorsiva come fact-iter come la generazione di un processo iterativo.Tuttavia, il processo è iterativo:Il suo stato viene catturato completamente le tre variabili di stato, e un interprete bisogno di tenere traccia di solo tre variabili, in modo da eseguire il processo.

Uno dei motivi per cui la distinzione tra processo e procedimento, può essere confuso è che la maggior parte delle implementazioni di linguaggi comuni (tra cui Ada, Pascal, e C) sono progettati in modo che l'interpretazione di qualsiasi ricorsiva procedura consuma una quantità di memoria che cresce con il numero di chiamate di procedura, anche quando il processo descritto è, in linea di principio, iterativo.Di conseguenza, queste lingue può descrivere iterativo processi solo ricorrendo a speciali “costrutti di ciclo” come fare, ripetere, fino a quando, per, e mentre. L'attuazione di Regime di non condividere questo difetto.Si verrà eseguito un processo iterativo in spazio costante, anche se il processo iterativo descritto da una procedura ricorsiva.Un attuazione con questa proprietà viene chiamata tail-ricorsiva. Con un tail-ricorsiva di attuazione, l'iterazione può essere espressa utilizzando il procedura ordinaria meccanismo di chiamata, in modo che particolari iterazione i costrutti sono utili solo come " zucchero sintattico.

Answer 18

Ricorsività è la vita che si sta vivendo in questo momento.Costantemente riciclare lo stesso stack frame, più e più volte, perché non c'è nessuna ragione o mezzi per tornare a un "precedente" del telaio.Il passato è passato e fatto con così può essere scartato.Si ottiene un fotogramma, sempre in movimento verso il futuro, fino a quando il processo inevitabilmente muore.

_{L'analogia si rompe quando si considera alcuni processi potrebbero utilizzare altri fotogrammi, ma sono ancora considerati tail-ricorsiva, se la pila non cresce all'infinito.}

Answer 19

Una coda di ricorsione è una funzione ricorsiva in cui le chiamate di funzione stesso alla fine ("coda") della funzione in cui nessun calcolo è fatto dopo il ritorno di chiamata ricorsiva.Molti compilatori per ottimizzare cambiare una chiamata ricorsiva di coda ricorsivo o iterativo chiamata.

Prendere in considerazione il problema del calcolo fattoriale di un numero.

Un approccio diretto sarebbe:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Supponiamo che si chiama fattoriale(4).L'albero di ricorsione sarebbe:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

La massima profondità di ricorsione nel caso di cui sopra è O(n).

Tuttavia, si consideri il seguente esempio:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Albero di ricorsione per factTail(4) sarebbe:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Anche qui, massima profondità di ricorsione è O(n), ma nessuna delle chiamate aggiunge qualche variabile in più per lo stack.Quindi il compilatore è in grado di fare con una pila.

Answer 20

Per capire alcuni dei fondamentali differenze tra la coda di chiamata di ricorsione e non-coda-di chiamare la ricorsione siamo in grado di esplorare l' .NET implementazioni di queste tecniche.

Ecco un articolo con alcuni esempi in C#, F# e C++\CLI: Avventure in Coda Ricorsione in C#, F# e C++\CLI.

C# non ottimizza la coda di chiamata ricorsione mentre F# non.

Le differenze di principio coinvolgere passanti vsLambda calcolo.C# è stato progettato con passanti in mente mentre F# è costruito dai principi del Lambda calcolo.Per un ottimo (e gratuito) libro sui principi del Lambda calcolo, vedere La struttura e l'Interpretazione dei Programmi per Computer, da Abelson, Sussman, e Sussman.

Per quanto riguarda la coda chiamate in F#, per un ottimo articolo introduttivo, vedere Introduzione dettagliata di Coda Chiamate in F#.Infine, ecco un articolo che copre la differenza tra non-ricorsione di coda e la coda di chiamata di ricorsione (F#): Coda-di ricorsione vsnon ricorsività in F sharp.

Se volete saperne di più su alcune delle differenze di design di coda di chiamata ricorsione tra C# e F#, vedere La generazione di Coda-Call Opcode in C# e F#.

Se si cura abbastanza per voler sapere che cosa le condizioni di evitare che il compilatore C#, dall'esecuzione di coda di chiamata ottimizzazioni, vedere questo articolo: JIT CLR coda-call condizioni.

Answer 21

Ci sono due tipi fondamentali di ricorsioni: testa di ricorsione e ricorsività.

In testa di ricorsione, una funzione rende la sua chiamata ricorsiva e quindi esegue più calcoli, magari usando il risultato del chiamata ricorsiva, per esempio.

In un tail ricorsiva funzione, tutti i calcoli accadere prima e la chiamata ricorsiva è l'ultima cosa che accade.

Tratto da questo super fantastico post.Si prega di prendere in considerazione la lettura.

Answer 22

Ricorsione indica una funzione che richiama se stessa.Per esempio:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion significa che la ricorsione concludere che la funzione:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Vedi, l'ultima cosa onu-ended funzione (procedura, in Regime di gergo) non è quello di chiamare se stesso.Un altro (più utile) esempio:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

Nel helper procedura, l'ULTIMA cosa che fa se la sinistra non è zero, è di chiamare se stesso (DOPO contro qualcosa e cdr qualcosa).Questo è fondamentalmente come una mappa di un elenco.

La coda-la ricorsione è un grande vantaggio che l'interprete o compilatore, dipende dalla lingua e fornitore) in grado di ottimizzare e trasformare in qualcosa di equivalente ad un ciclo while.Infatti, in Regime di tradizione, più che "per" e ", mentre" il ciclo è finito in un tail-recursion modo (non c'è per un po', per quanto ne so).

Answer 23

Questa domanda ha un sacco di grandi risposte...ma io non posso aiutare ma carillon con un'alternativa prendere su come definire "ricorsività", o almeno "corretto ricorsività." Vale a dire:si dovrebbe guardare come una proprietà di una particolare espressione in un programma?O ci si deve guardare come una proprietà di un implementazione di un linguaggio di programmazione?

Per saperne di più su quest'ultimo aspetto, c'è un classico carta da Clinger, "Corretto Ricorsività e l'Efficienza di Spazio" (PLDI 1998), che ha definito "corretto ricorsività" come una proprietà di un linguaggio di programmazione che di attuazione.La definizione è costruito per permettere di ignorare i dettagli di implementazione (ad esempio se lo stack di chiamate è in realtà rappresentato tramite il runtime stack o tramite un'allocazione heap elenco collegato di frame).

Per fare questo, utilizza asintotica analisi:non di tempo di esecuzione del programma, come di solito si vede, ma piuttosto di programma l'utilizzo dello spazio.In questo modo, l'utilizzo di spazio di allocazione heap lista collegata vs un runtime stack di chiamate finisce per essere asintoticamente equivalente;così si arriva a ignorare il linguaggio di programmazione di dettaglio di implementazione (un dettaglio che certamente conta un bel po', in pratica, ma può inquinare le acque un po ' quando si cerca di determinare se un dato attuazione è quello di soddisfare il requisito di essere "la struttura ricorsiva di coda")

La carta vale un attento studio per una serie di motivi:

• Esso fornisce una definizione induttiva di coda espressioni e coda chiamate di un programma.(Tale definizione, e perché tali chiamate sono importanti, sembra essere il soggetto della maggior parte delle altre risposte date qui.)

  Qui sono quelle definizioni, solo per fornire un sapore di testo:

  Definizione 1 Il coda espressioni di un programma scritto in Core Schema sono definiti induttivamente come segue.

  1. Il corpo di una lambda expression è una coda di espressione
  2. Se (if E0 E1 E2) è una coda di espressione, quindi sia E1 e E2 sono in coda espressioni.
  3. Nient'altro è una coda di espressione.

  Definizione 2 Un coda di chiamata è una coda di espressione che è una chiamata di procedura.

(una coda di chiamata ricorsiva, o come la carta dice, "self-coda di chiamata" è un caso speciale di una coda di chiamata in cui la procedura viene richiamata stesso.)

• Esso fornisce le definizioni formali per sei diverse "macchine" per la valutazione Nucleo di Regime, in cui ogni macchina ha lo stesso comportamento osservabile salvo per il asintotica spazio complessità di classe che ciascuno è in.

  Per esempio, dopo aver dato le definizioni per le macchine con, rispettivamente, 1.stack-based di gestione della memoria, 2.garbage collection, ma senza coda chiamate, 3.raccolta rifiuti e la coda di chiamate, la carta continua poi con ancora più avanzate di memorizzazione strategie di gestione, come il 4."evlis ricorsività", in cui l'ambiente non ha bisogno di essere conservato attraverso la valutazione dell'ultimo sub-argomento di espressione in una coda di chiamata, 5.riducendo l'ambiente di una chiusura a solo le variabili libere di chiusura, e 6.cosiddetto "safe-per-spazio" semantica", come definito dalla Appel e Shao.

• Al fine di dimostrare che le macchine appartengono a sei distinti spazio complessità classi, la carta, per ogni coppia di macchine a confronto, fornisce esempi concreti di programmi in grado di esporre asintotica spazio di ingrandimento su una macchina, ma non gli altri.

---

(Che, leggendo la mia risposta ora, non so se sono riuscita a catturare i punti cruciali del Clinger carta.Ma, ahimè, non posso dedicare più tempo allo sviluppo di questa risposta per il momento).

Answer 24

La funzione ricorsiva è una funzione che chiamate da sola

Esso consente ai programmatori di scrivere i programmi efficienti utilizzando un quantità minima di codice.

Il lato negativo è che può causare un loop infinito e altri risultati imprevisti se non è scritto correttamente.

Vi spiegherò sia Semplice funzione Ricorsiva e la Coda di funzione Ricorsiva

Per scrivere un Semplice funzione ricorsiva

1. Il primo punto da considerare è quando si decide di uscire del ciclo, che è il loop
2. La seconda è che il processo di fare se ci sono le nostre funzione

Da l'esempio:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Dall'esempio sopra

if(n <=1)
     return 1;

È il fattore decisivo al momento di uscire dal loop

else 
     return n * fact(n-1);

È l'effettiva elaborazione

Let me rompere il compito a uno a uno, per una facile comprensione.

Vediamo cosa accade internamente se corro fact(4)

1. Sostituendo n=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If ciclo non riesce così va a else loop così si restituisce 4 * fact(3)

2. In memoria dello stack, abbiamo 4 * fact(3)

   Sostituendo n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If ciclo non riesce così va a else loop

così si restituisce 3 * fact(2)

Ricordati che abbiamo chiamato ``4 * fact(3)`

L'uscita per fact(3) = 3 * fact(2)

Finora lo stack 4 * fact(3) = 4 * 3 * fact(2)

3. In memoria dello stack, abbiamo 4 * 3 * fact(2)

   Sostituendo n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If ciclo non riesce così va a else loop

così si restituisce 2 * fact(1)

Ricordati che abbiamo chiamato 4 * 3 * fact(2)

L'uscita per fact(2) = 2 * fact(1)

Finora lo stack 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. In memoria dello stack, abbiamo 4 * 3 * 2 * fact(1)

   Sostituendo n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If loop è vero

così si restituisce 1

Ricordati che abbiamo chiamato 4 * 3 * 2 * fact(1)

L'uscita per fact(1) = 1

Finora lo stack 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Infine, il risultato di fatto(4) = 4 * 3 * 2 * 1 = 24

Il Ricorsività sarebbe

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. Sostituendo n=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If ciclo non riesce così va a else loop così si restituisce fact(3, 4)

2. In memoria dello stack, abbiamo fact(3, 4)

   Sostituendo n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If ciclo non riesce così va a else loop

così si restituisce fact(2, 12)

2. In memoria dello stack, abbiamo fact(2, 12)

   Sostituendo n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If ciclo non riesce così va a else loop

così si restituisce fact(1, 24)

3. In memoria dello stack, abbiamo fact(1, 24)

   Sostituendo n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If loop è vero

così si restituisce running_total

L'uscita per running_total = 24

Infine, il risultato di fatto(4,1) = 24

Answer 25

Molte persone hanno già spiegato la ricorsione qui.Vorrei citare un paio di pensieri su alcuni vantaggi che la ricorsione dà dal libro “la Concorrenza in .NET, Moderni modelli di concorrenti e di programmazione parallela” di Riccardo Terrell:

“Funzionali ricorsione è il modo naturale per scorrere in FP, perché evita di mutazione di stato.Durante ogni iterazione, un nuovo valore viene passato nel ciclo costruttore, invece, essere aggiornato (mutato).In inoltre, una funzione ricorsiva può essere composto, rendendo il vostro programma più modulare, così come l'introduzione di nuove opportunità per sfruttare parallelizzazione."

Anche qui ci sono alcune interessanti note dallo stesso libro sulla ricorsività:

Coda-di chiamare la ricorsione è una tecnica che consente di convertire un normale ricorsiva funzione in una versione ottimizzata in grado di gestire grandi ingressi senza rischi ed effetti collaterali.

NOTA La ragione principale per una coda di chiamata come ottimizzazione è quello di migliorare località di dati, utilizzo della memoria, e l'utilizzo della cache.Facendo una coda chiamata, il chiamato utilizza lo stesso spazio nello stack del chiamante.Questo riduce memoria di pressione.Non marginalmente migliora la cache, poiché lo stesso la memoria è riutilizzati per successive chiamanti e può rimanere nella cache, piuttosto che la rimozione di una vecchia linea di cache per fare spazio per una nuova cache linea.

Answer 26

Un tail ricorsiva la funzione è una funzione ricorsiva in cui l'ultima operazione prima di ritorno è di fare la chiamata di funzione ricorsiva.Che è, il valore di ritorno della chiamata di funzione ricorsiva è immediatamente restituito.Per esempio, il codice sarebbe simile a questa:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Compilatori e interpreti che implementano coda di chiamata ottimizzazione o coda di chiamata eliminazione possibile ottimizzare il codice ricorsivo per evitare overflow dello stack.Se il compilatore o un interprete non implementare la coda di chiamata di ottimizzazione (come il CPython interprete) non vi è alcun ulteriore beneficio per scrivere il tuo codice in questo modo.

Per esempio, questo è uno standard ricorsiva del fattoriale funzione in Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

E questa è una coda di chiamata versione ricorsiva della funzione fattoriale:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Si noti che, anche se questo codice Python, il CPython interprete non fare coda di chiamata di ottimizzazione, in modo da organizzare il tuo codice come questo non conferisce alcun runtime beneficio.)

Si può avere a rendere il codice un po ' più illeggibile di fare uso di coda di chiamata di ottimizzazione, come illustrato nell'esempio di fattoriale.(Per esempio, il caso base è un po ' poco intuitivo, e l' accumulator il parametro è effettivamente utilizzato come una sorta di variabile globale.)

Ma il beneficio di coda di chiamata di ottimizzazione è quello di evitare errori di overflow dello stack.(Faccio notare che è possibile ottenere questo stesso beneficio utilizzando un algoritmo iterativo, invece di un ricorsiva uno.)

Stack overflow sono causati quando lo stack di chiamate ha avuto troppi frame oggetti inseriti.Un telaio in oggetto viene inserito nello stack di chiamate quando viene chiamata una funzione, e spuntato fuori lo stack di chiamate quando la funzione restituisce.Telaio oggetti contengono informazioni quali le variabili locali e quale riga di codice per tornare a quando la funzione restituisce.

Se la funzione ricorsiva fa troppe chiamate ricorsive senza ritorno, lo stack di chiamate grado di superare la sua cornice limite dell'oggetto.(Il numero varia a seconda della piattaforma;in Python è 1000 frame oggetti per impostazione predefinita.) Questo provoca un stack overflow errore.(Ehi, che è dove il nome di questo sito!)

Tuttavia, se l'ultima cosa che la funzione ricorsiva non è fare la chiamata ricorsiva e ritorna il suo valore di ritorno, quindi non c'è nessun motivo si deve mantenere l'attuale telaio in oggetto ha bisogno di rimanere stack di chiamate.Dopo tutto, se non c'è il codice dopo la chiamata di funzione ricorsiva, non c'è alcun motivo per tenersi al corrente oggetto frame variabili locali.Così si può sbarazzarsi di il fotogramma corrente oggetto immediatamente, piuttosto che tenerlo nello stack di chiamate.Il risultato finale di questo è che il vostro stack di chiamate non crescere in dimensioni, e pertanto non sono in grado di overflow dello stack.

Un compilatore o un interprete deve avere la coda di chiamata ottimizzazione di una funzione per essere in grado di riconoscere quando la coda di chiamata ottimizzazione può essere applicata.Anche allora, si può avere riorganizzare il codice nella funzione ricorsiva per usufruire di coda di chiamata di ottimizzazione, e spetta a voi se questo potenziale diminuzione leggibilità è valsa la pena di ottimizzazione.

Answer 27

Ricorsività è abbastanza veloce rispetto al normale ricorsione.È veloce perché l'uscita degli antenati chiamata non verrà scritto in stack per tenere traccia.Ma in normale ricorsione tutte le antenato chiamate in uscita scritto in stack per tenere traccia.