Domanda

Un reddit thread portato apparentemente domanda interessante:

Coda per le funzioni ricorsive possono, ovviamente, essere convertito in iterativo funzioni.Altri, può essere trasformato mediante un esplicito stack.Può ogni ricorsione essere trasformato in iterazione?

Il contatore?)esempio nel post è la coppia:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))
È stato utile?

Soluzione

Si può girare sempre una funzione ricorsiva in un iterativo? Sì, assolutamente, e la tesi di Church-Turing lo dimostra, se la memoria non serve. In termini laici, si afferma che ciò che è calcolabile da funzioni ricorsive è calcolabile da un modello iterativo (ad esempio la macchina di Turing) e viceversa. La tesi non dirà esattamente come fare la conversione, ma non dire che è sicuramente possibile.

In molti casi, la conversione di una funzione ricorsiva è facile. Knuth offre diverse tecniche di "The Art of Computer Programming". E spesso, una cosa calcolata in modo ricorsivo può essere calcolato con un approccio completamente diverso in meno tempo e nello spazio. Il classico esempio di questo è numeri di Fibonacci o sequenze loro. Avrai sicuramente incontrato questo problema nel vostro piano di laurea.

Sul rovescio della medaglia, possiamo certamente immaginare un sistema di programmazione in modo avanzato per il trattamento di una definizione ricorsiva di una formula come un invito a Memoize risultati precedenti, offrendo così il vantaggio di velocità, senza il fastidio di dire al computer esattamente che passi da seguire nel calcolo di una formula con una definizione ricorsiva. Dijkstra quasi certamente immaginava un tale sistema. Ha trascorso un lungo periodo di tempo cercando di separare l'implementazione dalla semantica di un linguaggio di programmazione. Poi di nuovo, i suoi linguaggi di programmazione non-deterministici e multiprocessing sono in un campionato al di sopra del programmatore professionista pratica.

In ultima analisi, molte funzioni sono semplicemente più facili da capire, leggere e scrivere in forma ricorsiva. A meno che non ci sia un motivo valido, probabilmente non dovrebbe (manualmente) di convertire queste funzioni ad un algoritmo iterativo in modo esplicito. Il computer gestirà quel lavoro in modo corretto.

Posso vedere un motivo valido. Supponiamo che hai un prototipo di sistema in un linguaggio di livello super-alta come [ di indossare biancheria intima di amianto ] Scheme, Lisp, Haskell, OCaml, Perl, o Pascal. Supponiamo condizioni sono tali che è necessario un'implementazione in C o Java. (Forse è la politica). Poi si potrebbe certamente avere alcune funzioni scritte in modo ricorsivo, ma che, tradotto letteralmente, sarebbe esploso il sistema di runtime. Ad esempio, infinito ricorsione coda è possibile nello Schema, ma lo stesso linguaggio provoca un problema per ambienti C esistenti. Un altro esempio è l'uso di funzioni lessicali nidificati e portata statica, che sostiene Pascal ma C no.

In queste circostanze, si potrebbe cercare di superare la resistenza politica alla lingua originale. Potreste trovarvi reimplementare Lisp male, come nel decimo legge di (tongue-in-cheek) Greenspun. Oppure si potrebbe trovare solo un approccio completamente diverso alla soluzione. Ma in ogni caso, v'è sicuramente un modo.

Altri suggerimenti

È sempre possibile scrivere un non ricorsiva modulo per ogni funzione ricorsiva?

Sì.Una semplice prova formale è quello di mostrare che sia µ ricorsione e non ricorsiva di calcolo come GOTO sono entrambi Turing completo.Dal momento che tutti Turing completo calcoli sono strettamente equivalenti nella loro forza espressiva, tutte le funzioni ricorsive possono essere attuate da non ricorsiva Turing-completo di calcolo.

Purtroppo, non riesco a trovare una buona, definizione formale di GOTO online eccone una:

Un GOTO programma è una sequenza di comandi P eseguito su un registrare macchina tale che P è uno dei seguenti:

  • HALT, che interrompe l'esecuzione
  • r = r + 1 dove r è alcun albo
  • r = r – 1 dove r è alcun albo
  • GOTO x dove x è un'etichetta
  • IF r ≠ 0 GOTO x dove r è alcun registro e x è un'etichetta
  • Un'etichetta, seguito da tutti i comandi di cui sopra.

Tuttavia, le conversioni tra ricorsiva e non funzioni ricorsive non è sempre banale (tranne che da una folle manuale di re-implementazione dello stack di chiamate).

Per ulteriori informazioni, vedere questa risposta.

ricorsione è implementato come pile o costrutti simili a interpreti reali o compilatori. Così si può certamente convertire una funzione ricorsiva per una controparte iterativa perché è così che ha sempre fatto (se automatico) . Sarete solo duplicare il lavoro del compilatore in un ad-hoc e, probabilmente, in un modo molto brutto e inefficiente.

In sostanza sì, in sostanza ciò che si finisce per dover fare è sostituire le chiamate di metodo (che spingono implicitamente stato sulla pila) in pila esplicita spinge a ricordare dove il 'precedente chiamata' aveva ottenuto fino a, e quindi eseguire il ' cd metodo', invece.

Mi immagino che la combinazione di un ciclo, uno stack e uno stato-macchina potrebbe essere utilizzata per tutti gli scenari da fondamentalmente simulando le chiamate di metodo. Se questo sta per essere 'migliore' (o più veloce, più efficiente, in un certo senso) non è davvero possibile dire in generale.

  • ricorsivo flusso di esecuzione funzione può essere rappresentata come un albero.

  • La stessa logica può essere fatto da un anello, che utilizza una struttura dati per attraversare l'albero.

  • attraversamento in profondità può essere fatto utilizzando una pila, attraversamento in ampiezza può essere fatto utilizzando una coda.

Quindi, la risposta è: sì. Perché: https://stackoverflow.com/a/531721/2128327

.
  

Può una ricorsione essere fatto in un unico ciclo? Sì, perché

     

una macchina di Turing fa tutto ciò che fa eseguendo un singolo ciclo:

     
      
  1. prendere un'istruzione,
  2.   
  3. valutarlo,
  4.   
  5. goto 1.
  6.   

Si, è sempre possibile scrivere una versione non ricorsiva. La soluzione banale è quella di utilizzare una struttura dati stack e simulare l'esecuzione ricorsiva.

Sì, utilizzando in modo esplicito uno stack (ma la ricorsione è molto più piacevole da leggere, secondo la mia opinione).

In linea di principio è sempre possibile rimuovere ricorsione e sostituirlo con iterazione in un linguaggio che è stato infinito sia per strutture di dati e per lo stack di chiamate. Questa è una conseguenza fondamentale della tesi di Church-Turing.

Dato un linguaggio di programmazione vero e proprio, la risposta non è così ovvia. Il problema è che è del tutto possibile avere una lingua in cui la quantità di memoria che può essere allocata nel programma è limitato, ma dove la quantità di stack di chiamate che può essere utilizzato è illimitata (32 bit C in cui l'indirizzo di variabili di stack non è accessibile). In questo caso, la ricorsione è più potente semplicemente perché ha più memoria può usare; non c'è abbastanza memoria esplicitamente assegnabile per emulare lo stack di chiamate. Per una discussione dettagliata su questo, vedi questo discussione .

A volte sostituendo la ricorsione è molto più facile di quello. Ricorsione usato per essere la cosa alla moda insegnato in CS nel 1990, e così un sacco di sviluppatori in media da quel momento pensato che se hai risolto qualcosa con la ricorsione, è stata una soluzione migliore. Così avrebbero usato la ricorsione invece di looping all'indietro per ordine, o cose stupide come quella inversa. Così a volte la rimozione di ricorsione è un semplice "duh, che era ovvio" tipo di esercizio.

Si tratta di meno di un problema ora, come la moda si è spostato verso altre tecnologie.

Tutte le funzioni calcolabili possono essere calcolati tramite macchine di Turing e quindi i sistemi ricorsivi e macchine di Turing (sistemi iterativi) sono equivalenti.

La rimozione ricorsione è un problema complesso ed è realizzabile in circostanze ben definite.

I casi che seguono sono tra i facili:

Appart dallo stack esplicito, un altro modello per la conversione ricorsione in iterazione è con l'uso di un trampolino.

Qui, le funzioni o restituiscono il risultato finale, o di una chiusura della chiamata di funzione che avrebbe altrimenti eseguita. Quindi, la funzione di avvio del procedimento (trampolino) tenere invocando le chiusure restituiti fino al raggiungimento del risultato finale.

Questo approccio funziona per le funzioni mutuamente ricorsive, ma temo che funziona solo per le chiamate coda.

http://en.wikipedia.org/wiki/Trampoline_(computers)

Direi di sì - una chiamata di funzione non è altro che un goto e un'operazione di stack (grosso modo). Tutto quello che devi fare è imitare la pila che è costruito durante il richiamo funzioni e fare qualcosa di simile a un goto (si può imitare goto con le lingue che non hanno esplicitamente questa parola chiave troppo).

Dai un'occhiata alle seguenti voci su Wikipedia, è possibile utilizzare come punto di partenza per trovare una risposta completa alla tua domanda.

Segue un paragrafo che può dare qualche suggerimento su dove cominciare:

  

Soluzione del rapporto di ricorrenza significa ottenere un forma chiusa soluzione : un non- funzione ricorsiva di n.

Anche dare un'occhiata all'ultimo paragrafo della questa voce .

  

E 'possibile convertire qualsiasi algoritmo ricorsivo a un non-ricorsiva   uno, ma spesso la logica è molto più complesso e farlo richiede   l'uso di una pila. Infatti, ricorsione si utilizza uno stack: la   funzione di stack.

Maggiori Dettagli: https://developer.mozilla.org / it-IT / docs / Web / JavaScript / Guida / Funzioni

tazzego, ricorsione significa che una funzione chiamare se stesso che vi piaccia o no. Quando le persone si parla di se o non le cose possono essere fatte senza ricorsione, significano questo e non si può dire "no, non è vero, perché non sono d'accordo con la definizione di ricorsività" come una dichiarazione valida.

Con questo in mente, quasi tutto il resto che dici è una sciocchezza. L'unica altra cosa che tu dici che non è una sciocchezza è l'idea che non si può immaginare la programmazione senza stack. Questo è qualcosa che era stato fatto per decenni fino a quando si utilizza uno stack è diventato popolare. Le vecchie versioni di FORTRAN mancava uno stack e hanno lavorato bene.

A proposito, esistono Turing-completo lingue che implementano solo ricorsione (ad esempio SML) come mezzo di loop. Esistono anche Turing-completo lingue che implementano iterazione solo come mezzo di loop (ad esempio FORTRAN IV). La tesi di Church-Turing dimostra che tutto il possibile in una ricorsione solo lingue può essere fatto in una lingua non ricorsivo e vice-versa per il fatto che entrambi hanno la proprietà di turing-completezza.

Ecco un algoritmo iterativo:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top