Un ciclo while è intrinsecamente una ricorsione?

I loop sono molto ricorsivi non . In effetti, sono il primo esempio del meccanismo opposto : iterazione .

Il punto di ricorsione è che un elemento di elaborazione di chiama un'altra istanza di se stesso. Il macchinario di controllo del ciclo semplicemente salta nel punto in cui è stato avviato.

Saltare nel codice e chiamare un altro blocco di codice sono operazioni diverse. Ad esempio, quando si salta all'inizio del ciclo, la variabile di controllo del ciclo ha ancora lo stesso valore che aveva prima del salto. Ma se chiami un'altra istanza della routine in cui ti trovi, la nuova istanza ha nuove copie non correlate di tutte le sue variabili. In effetti, una variabile può avere un valore sul primo livello di elaborazione e un altro valore su un livello inferiore.

Questa funzionalità è cruciale per il funzionamento di molti algoritmi ricorsivi, ed è per questo che non è possibile emulare la ricorsione tramite iterazione senza gestire anche una pila di frame chiamati che tiene traccia di tutti quei valori.

Dire che X è intrinsecamente Y ha senso solo se hai in mente un sistema (formale) che stai esprimendo X in. Se definisci la semantica di while in termini di calcolo lambda, potresti menzionare ricorsione *; se lo definisci in termini di macchina di registro, probabilmente non lo farai.

In entrambi i casi, probabilmente le persone non ti capiranno se chiami una funzione ricorsiva solo perché contiene un ciclo while.

* Anche se forse solo indirettamente, ad esempio se lo definisci in termini di fold .

Dipende dal tuo punto di vista.

Se osservi la teoria della computabilità , l'iterazione e la ricorsione sono ugualmente espressive . Ciò significa che puoi scrivere una funzione che calcola qualcosa, e non importa se lo fai in modo ricorsivo o iterativo, sarai in grado di scegliere entrambi gli approcci. Non c'è nulla che tu possa calcolare in modo ricorsivo che non puoi calcolare in modo iterativo e viceversa (anche se il funzionamento interno del programma potrebbe essere diverso).

Molti linguaggi di programmazione non trattano la ricorsione e l'iterazione allo stesso modo, e per una buona ragione. Di solito , la ricorsione significa che la lingua / il compilatore gestisce lo stack delle chiamate, e l'iterazione significa che potresti dover gestire da solo lo stack.

Tuttavia, ci sono linguaggi - in particolare linguaggi funzionali - in cui cose come loop (per, while) sono infatti solo zucchero sintattico per la ricorsione e implementate dietro il scene così. Questo è spesso auspicabile nei linguaggi funzionali, perché di solito non hanno il concetto di looping altrimenti, e l'aggiunta di questo renderebbe il loro calcolo più complesso, per un piccolo motivo pratico.

Quindi no, non sono intrinsecamente uguali . Sono ugualmente espressivi , il che significa che non puoi calcolare qualcosa in modo iterativo che non puoi calcolare in modo ricorsivo e viceversa, ma questo è tutto, nel caso generale (secondo la tesi di Church-Turing).

Nota che stiamo parlando di programmi ricorsivi qui. Esistono altre forme di ricorsione, ad es. in strutture di dati (ad es. alberi).

Se lo guardi da un punto di vista dell'implementazione , la ricorsione e l'iterazione non sono praticamente la stessa cosa. La ricorsione crea un nuovo stack frame per ogni chiamata. Ogni fase della ricorsione è autonoma, ottenendo gli argomenti per il calcolo dal callee (stesso).

I loop d'altra parte non creano frame di chiamata. Per loro, il contesto non viene mantenuto ad ogni passaggio. Per il ciclo, il programma si limita a tornare all'inizio del ciclo fino a quando la condizione del ciclo non riesce.

Questo è abbastanza importante da sapere, dal momento che può fare differenze abbastanza radicali nel mondo reale. Per la ricorsione, l'intero contesto deve essere salvato ad ogni chiamata. Per l'iterazione, hai un controllo preciso su quali variabili sono in memoria e su cosa viene salvato dove.

Se lo guardi in questo modo, vedi rapidamente che per la maggior parte delle lingue, l'iterazione e la ricorsione sono fondamentalmente differenti e hanno proprietà diverse. A seconda della situazione, alcune proprietà sono più desiderabili di altre.

La ricorsione può rendere i programmi più semplici e facili da testare e prova . La conversione di una ricorsione in iterazione di solito rende il codice più complesso, aumentando la probabilità di errore. D'altra parte, la conversione in iterazione e la riduzione della quantità di frame di stack di chiamata possono far risparmiare memoria molto necessaria.

La differenza è lo stack implicito e semantico.

Un ciclo while che "chiama se stesso alla fine" non ha stack da eseguire il backup quando è finito. L'ultima iterazione imposta quale stato sarà come finisce.

La ricorsione tuttavia non può essere eseguita senza questo stack implicito che ricorda lo stato di lavoro svolto prima.

È vero che puoi risolvere qualsiasi problema di ricorsione con l'iterazione se gli dai un accesso esplicito a uno stack. Ma farlo in questo modo non è lo stesso.

La differenza semantica ha a che fare con il fatto che guardare il codice ricorsivo trasmette un'idea in un modo completamente diverso dal codice iterativo. Il codice iterativo fa le cose un passo alla volta. Accetta qualunque stato provenga da prima e lavora solo per creare lo stato successivo.

Il codice ricorsivo rompe un problema in frattali. Questa piccola parte sembra una grande parte, quindi possiamo fare solo un po 'di questo e un po' di esso allo stesso modo. È un modo diverso di pensare ai problemi. È molto potente e ci si abitua. Molto può essere detto in poche righe. Non puoi farlo uscire da un ciclo while anche se ha accesso a uno stack.

Tutto dipende dall'uso del termine intrinsecamente . A livello di linguaggio di programmazione, sono sintatticamente e semanticamente diversi e hanno prestazioni e utilizzo della memoria piuttosto diversi. Ma se si scava abbastanza in profondità nella teoria possono essere definiti in termini l'uno dell'altro, ed è quindi "lo stesso" in qualche senso teorico.

La vera domanda è: quando ha senso distinguere tra iterazione (loop) e ricorsione, e quando è utile pensarla come le stesse cose? La risposta è che quando si programma in realtà (al contrario di scrivere prove matematiche) è importante distinguere tra iterazione e ricorsione.

La ricorsione crea un nuovo stack frame, ovvero un nuovo set di variabili locali per ogni chiamata. Questo ha un sovraccarico e occupa spazio in pila, il che significa che una ricorsione abbastanza profonda può traboccare dallo stack che causa il crash del programma. L'iterazione invece modifica solo le variabili esistenti, quindi è generalmente più veloce e occupa solo una quantità costante di memoria. Quindi questa è una distinzione molto importante per uno sviluppatore!

Nelle lingue con ricorsione a coda di coda (in genere linguaggi funzionali), il compilatore può essere in grado di ottimizzare le chiamate ricorsive in modo tale da occupare solo una quantità costante di memoria. In quelle lingue l'importante distinzione non è l'iterazione o la ricorsione, ma la ricorsione chiamata coda-ricorsione e l'iterazione.

In conclusione: devi essere in grado di distinguere, altrimenti il tuo programma andrà in crash.

while sono una forma di ricorsione, vedi per es. la risposta accettata a questa domanda . Corrispondono all'operatore μ nella teoria della computabilità (vedi ad esempio qui ).

Tutte le variazioni di for cicli che iterano su un intervallo di numeri, una raccolta finita, una matrice e così via, corrispondono alla ricorsione primitiva, vedi ad es. qui e qui . Si noti che i cicli for di C, C ++, Java e così via, sono in realtà zucchero sintattico per un ciclo while , e quindi non corrisponde alla ricorsione primitiva. Il ciclo Pascal for è un esempio di ricorsione primitiva.

Una differenza importante è che la ricorsione primitiva termina sempre, mentre la ricorsione generalizzata ( while loops) non può terminare.

Modifica

Alcuni chiarimenti in merito a commenti e altre risposte. "La ricorsione si verifica quando una cosa è definita in termini di se stessa o del suo tipo." (vedi wikipedia ). Quindi,

Is a while loop intrinsically a recursion?

Poiché puoi definire un ciclo while in termini di se stesso

while p do c := if p then (c; while p do c))

then, yes , un ciclo while è una forma di ricorsione. Le funzioni ricorsive sono un'altra forma di ricorsione (un altro esempio di definizione ricorsiva). Le liste e gli alberi sono altre forme di ricorsione.

Un'altra domanda che è implicitamente presupposta da molte risposte e commenti è

Are while loops and recursive functions equivalent?

La risposta a questa domanda è no : un ciclo while corrisponde a una funzione ricorsiva di coda, dove le variabili a cui accede il ciclo corrispondono agli argomenti della funzione ricorsiva implicita, ma come altri hanno sottolineato, le funzioni non ricorsive alla coda non possono essere modellate da un ciclo while senza utilizzare uno stack extra.

Quindi, il fatto che "un while loop è una forma di ricorsione" non contraddice il fatto che "alcune funzioni ricorsive non possono essere espresse da un while loop".

Una chiamata a coda (o coda ricorsiva chiamata) è esattamente implementata come un "goto con argomenti" (senza spingere alcuno ulteriore frame di chiamata nello stack di chiamate ) e in alcune lingue funzionali (in particolare Ocaml) è il il solito modo di fare il ciclo.

Quindi un ciclo while (in lingue che li hanno) può essere visto come terminante con una coda chiamata al suo corpo (o al test della sua testa).

Allo stesso modo, le chiamate ricorsive ordinarie (non tail-call) possono essere simulate da loop (usando alcuni stack).

Leggi anche su continuazioni e stile di passaggio continuo .

Quindi "ricorsione" e "iterazione" sono profondamente equivalenti.

È vero che sia la ricorsione che i while-loop illimitati sono equivalenti in termini di espressività computazionale. Cioè, qualsiasi programma scritto in modo ricorsivo può essere riscritto in un programma equivalente usando invece i loop e viceversa. Entrambi gli approcci sono turing-complete , che può essere utilizzato per calcolare qualsiasi funzione computabile.

La differenza fondamentale in termini di programmazione è che la ricorsione consente di utilizzare i dati che vengono memorizzati nello stack delle chiamate. Per illustrare questo, supponi di voler stampare un elemento di una lista collegata singolarmente usando un ciclo o una ricorsione. Userò C per il codice di esempio:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Semplice, giusto? Ora facciamo una piccola modifica: stampa la lista nell'ordine inverso.

Per la variante ricorsiva, questa è una modifica quasi banale alla funzione originale:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Però, per la funzione del ciclo, abbiamo un problema. La nostra lista è collegata singolarmente e quindi può essere solo spostata in avanti. Ma dal momento che stiamo stampando al contrario, dobbiamo iniziare a stampare l'ultimo elemento. Una volta raggiunto l'ultimo elemento, non possiamo più tornare al penultimo elemento.

Quindi dobbiamo fare un sacco di re-traversing, o dobbiamo costruire una struttura dati ausiliaria che tenga traccia degli elementi visitati e da cui poi possiamo stampare in modo efficiente.

Perché non abbiamo questo problema con la ricorsione? Perché in ricorsione abbiamo già una struttura dati ausiliaria in atto: la funzione chiamata stack.

Poiché la ricorsione consente di tornare alla chiamata precedente della chiamata ricorsiva, con tutte le variabili locali e lo stato per quella chiamata ancora intatta, otteniamo una certa flessibilità che sarebbe noioso modellizzare nel caso iterativo.

I loop sono una forma speciale di ricorsione per raggiungere un compito specifico (per lo più iterazione). Si può implementare un ciclo in uno stile ricorsivo con la stessa prestazione [1] in diverse lingue. e nel SICP [2], puoi vedere che i loop sono descritti come "zucchero sintetico". Nella maggior parte dei linguaggi di programmazione imperativi, per e mentre i blocchi utilizzano lo stesso ambito della loro funzione genitore. Nondimeno, nella maggior parte dei linguaggi di programmazione funzionale non esiste né il ciclo né il ciclo while perché non ce n'è bisogno.

La ragione per cui le lingue imperative hanno per cicli / while è che stanno gestendo gli stati mutandoli. Ma in realtà, se guardi da una prospettiva diversa, se pensi a un blocco while come a una funzione stessa, prendi i parametri, elaborali e restituisci un nuovo stato - che potrebbe anche essere la chiamata della stessa funzione con parametri diversi - tu puoi pensare al loop come a una ricorsione.

Il mondo potrebbe anche essere definito mutevole o immutabile. se definiamo il mondo come un insieme di regole e chiamiamo una funzione definitiva che prende tutte le regole e lo stato corrente come parametri e restituisce il nuovo stato in base a questi parametri che ha la stessa funzionalità (genera lo stato successivo nello stesso modo), potremmo anche dire che è una ricorsione e un ciclo.

nel seguente esempio, life è la funzione accetta due parametri "rules" e "state", e il nuovo stato sarà costruito nella spunta temporale successiva.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: l'ottimizzazione delle chiamate tail è un'ottimizzazione comune nei linguaggi di programmazione funzionale per utilizzare lo stack di funzioni esistente nelle chiamate ricorsive anziché crearne uno nuovo.

[2]: Struttura e interpretazione dei programmi per computer, MIT. link

Un ciclo while è diverso dalla ricorsione.

Quando viene chiamata una funzione, si verifica quanto segue:

1. Uno stack frame viene aggiunto allo stack.

2. Il puntatore del codice si sposta all'inizio della funzione.

Quando un ciclo while è alla fine si verifica quanto segue:

1. Una condizione chiede se qualcosa è vero.

2. Se è così, il codice salta a un punto.

In generale, il ciclo while è simile al seguente pseudocodice:

 if (x)

 {

      Jump_to(y);

 }

Soprattutto, ricorsione e loop hanno diverse rappresentazioni del codice assembly e rappresentazioni del codice macchina. Ciò significa che non sono la stessa cosa. Possono avere gli stessi risultati, ma il diverso codice macchina dimostra che non sono al 100% la stessa cosa.

Solo l'iterazione è insufficiente per essere generalmente equivalente alla ricorsione, ma l'iterazione con uno stack è generalmente equivalente. Qualsiasi funzione ricorsiva può essere riprogrammata come un loop iterativo con uno stack e viceversa. Ciò non significa che sia pratico, tuttavia, e in qualsiasi situazione particolare l'uno o l'altro modulo potrebbe avere chiari vantaggi rispetto all'altra versione.

Non sono sicuro del motivo per cui questo è controverso. La ricorsione e l'iterazione con una pila sono la stessa procedura computazionale. Sono lo stesso "fenomeno", per così dire.

L'unica cosa che posso pensare è che quando si considerano questi come "strumenti di programmazione", sono d'accordo sul fatto che non si dovrebbe pensare a loro come alla stessa cosa. Sono equivalenti "matematicamente" o "computazionalmente" (ancora una volta iterazione con uno stack , non l'iterazione in generale), ma ciò non significa che dovresti affrontare i problemi con il pensiero che uno o l'altro farà. Da un punto di vista di implementazione / problem solving, alcuni problemi potrebbero funzionare meglio in un modo o nell'altro, e il tuo compito come programmatore è quello di decidere correttamente quale sia il più adatto.

Per chiarire, la risposta alla domanda È un ciclo while intrinsecamente una ricorsione? è definita no , o almeno "non meno che tu non abbia stack" .