Modo di andare dalla ricorsione all'iterazione
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho usato molto la ricorsione nei miei molti anni di programmazione per risolvere problemi semplici, ma sono pienamente consapevole che a volte hai bisogno di iterazioni a causa di problemi di memoria / velocità.
Quindi, in un passato molto lontano sono andato a cercare di scoprire se esistesse qualche "schema" o un modo da manuale per trasformare un approccio di ricorsione comune all'iterazione e non ha trovato nulla. O almeno nulla che io possa ricordare sarebbe di aiuto.
- Ci sono regole generali?
- Esiste un modello "quot"?
Soluzione
Di solito, sostituisco un algoritmo ricorsivo con un algoritmo iterativo spingendo su uno stack i parametri che sarebbero normalmente passati alla funzione ricorsiva. In effetti, stai sostituendo lo stack del programma con uno tuo.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
Nota: se al suo interno sono presenti più chiamate ricorsive e si desidera conservare l'ordine delle chiamate, è necessario aggiungerle nell'ordine inverso allo stack:
foo(first);
foo(second);
deve essere sostituito da
stack.push(second);
stack.push(first);
Modifica: l'articolo Eliminazione di stack e ricorsione (o Link al backup dell'articolo ) approfondisce questo argomento.
Altri suggerimenti
In realtà, il modo più comune per farlo è mantenere il proprio stack. Ecco una funzione ricorsiva quicksort in C:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
Ecco come potremmo renderlo iterativo mantenendo il nostro stack:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
Ovviamente, questo esempio non controlla i limiti dello stack ... e davvero potresti ridimensionare lo stack in base al caso peggiore dato dai valori destro e sinistro. Ma hai avuto l'idea.
Sembra che nessuno abbia affrontato dove la funzione ricorsiva si chiama più di una volta nel corpo e gestisce il ritorno a un punto specifico della ricorsione (cioè non primitivo-ricorsivo). Si dice che ogni ricorsione può essere trasformata in iterazione , quindi sembra che ciò sia possibile.
Ho appena trovato un esempio in C # di come farlo. Supponiamo che tu abbia la seguente funzione ricorsiva, che agisce come un attraversamento postordine e che AbcTreeNode è un albero 3-ary con puntatori a, b, c.
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
La soluzione iterativa:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
Sforzati di effettuare la tua chiamata ricorsiva Ricorsione della coda (ricorsione in cui l'ultima affermazione è la chiamata ricorsiva ). Una volta ottenuto questo, convertirlo in iterazione è generalmente abbastanza facile.
Bene, in generale, la ricorsione può essere imitata come iterazione semplicemente usando una variabile di memoria. Si noti che ricorsione e iterazione sono generalmente equivalenti; uno può quasi sempre essere convertito nell'altro. Una funzione ricorsiva della coda viene convertita molto facilmente in una iterativa. Basta rendere la variabile accumulatore una locale e iterare invece di recurse. Ecco un esempio in C ++ (C se non fosse per l'uso di un argomento predefinito):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
Conoscendomi, probabilmente ho fatto un errore nel codice, ma l'idea è lì.
Anche l'uso dello stack non converte un algoritmo ricorsivo in iterativo. La ricorsione normale è ricorsione basata sulla funzione e se usiamo lo stack, diventa ricorsione basata sullo stack. Ma è ancora ricorsione.
Per gli algoritmi ricorsivi, la complessità dello spazio è O (N) e la complessità temporale è O (N). Per gli algoritmi iterativi, la complessità dello spazio è O (1) e la complessità temporale è O (N).
Ma se usiamo le cose in pila in termini di complessità rimane la stessa. Penso che solo la ricorsione della coda possa essere convertita in iterazione.
impila e elimina la ricorsione articolo coglie l'idea di esternalizzare il frame dello stack sull'heap, ma non fornisce un modo semplice e ripetibile per la conversione. Di seguito è uno.
Durante la conversione in codice iterativo, bisogna essere consapevoli del fatto che la chiamata ricorsiva può avvenire da un blocco di codice arbitrariamente profondo. Non sono solo i parametri, ma anche il punto di tornare alla logica che resta da eseguire e allo stato delle variabili che partecipano ai condizionali successivi, che contano. Di seguito è riportato un modo molto semplice per convertire in codice iterativo con meno modifiche.
Considera questo codice ricorsivo:
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
Codice iterativo:
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
Nota come la struttura del codice rimane fedele alla logica ricorsiva e le modifiche sono minime, con conseguente minor numero di bug. Per confronto, ho contrassegnato le modifiche con ++ e -. La maggior parte dei nuovi blocchi inseriti, ad eccezione di v.push_back, sono comuni a qualsiasi logica iterativa convertita
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
Cerca su Google " Stile di passaggio di continuazione. " Esiste una procedura generale per la conversione in uno stile ricorsivo della coda; esiste anche una procedura generale per trasformare le funzioni ricorsive della coda in anelli.
Solo ammazzare il tempo ... Una funzione ricorsiva
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
può essere convertito in
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
Generalmente la tecnica per evitare l'overflow dello stack per le funzioni ricorsive è chiamata tecnica del trampolino che è ampiamente adottata dagli sviluppatori Java.
Tuttavia, per C # esiste un piccolo metodo di supporto qui che trasforma la tua funzione ricorsiva in iterativa senza richiedere la modifica della logica o la comprensione del codice. C # è un linguaggio così carino che è possibile fare cose fantastiche.
Funziona avvolgendo parti del metodo con un metodo helper. Ad esempio la seguente funzione ricorsiva:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
Si trasforma in:
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
Pensando a cose che hanno effettivamente bisogno di uno stack:
Se consideriamo il modello di ricorsione come:
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
Ad esempio, la classica Torre di Hanoi
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
Questo può essere tradotto in un ciclo che lavora su uno stack esplicito, riaffermandolo come:
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
Per la Torre di Hanoi questo diventa:
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
Qui c'è una notevole flessibilità nel modo in cui si definisce il proprio stack. Puoi rendere il tuo stack un elenco di oggetti Command che fanno cose sofisticate. Oppure puoi andare nella direzione opposta e renderlo un elenco di tipi più semplici (ad es. Un'attività " potrebbe essere 4 elementi in una pila di int , piuttosto che un elemento in una pila di compito ).
Tutto ciò significa che la memoria per lo stack è nell'heap anziché nello stack di esecuzione Java, ma ciò può essere utile in quanto si ha un maggiore controllo su di esso.
Uno schema da cercare è una chiamata di ricorsione alla fine della funzione (la cosiddetta ricorsione di coda). Questo può essere facilmente sostituito con un po 'di tempo. Ad esempio, la funzione foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
termina con una chiamata a foo. Questo può essere sostituito con:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
che elimina la seconda chiamata ricorsiva.
Ho appena annullato la risposta suggerendo di usare uno stack esplicito che penso sia la soluzione giusta ed è di applicabilità generale.
Voglio dire che puoi usarlo per trasformare qualsiasi funzione ricorsiva in una funzione iterativa. Basta controllare quali valori vengono salvati tra le chiamate ricorsive, quelle che devono essere locali per la funzione ricorsiva e sostituire le chiamate con un ciclo in cui le spingerete su uno stack. Quando lo stack è vuoto, la funzione ricorsiva sarebbe stata terminata.
Non posso resistere nel dire che la prova che ogni funzione ricorsiva equivale a una funzione iterativa su un diverso tipo di dati, è uno dei miei ricordi più cari dei miei tempi universitari. Questo è stato il corso (e il professore) che mi ha fatto davvero capire di cosa trattava la programmazione informatica.
Una domanda che era stata chiusa come duplicata di questa aveva una struttura di dati molto specifica:
Il nodo aveva la seguente struttura:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
La funzione di eliminazione ricorsiva sembrava:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
In generale, non è sempre possibile evitare uno stack per funzioni ricorsive che si richiamano più di una volta (o anche una volta). Tuttavia, per questa particolare struttura, è possibile. L'idea è di appiattire tutti i nodi in un unico elenco. Ciò si ottiene inserendo il child del nodo corrente alla fine dell'elenco della riga superiore.
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
Questa tecnica può essere applicata a qualsiasi struttura collegata ai dati che può essere ridotta a un DAG con un ordinamento topologico deterministico. I figli dei nodi correnti vengono riorganizzati in modo che l'ultimo figlio adotti tutti gli altri bambini. Quindi il nodo corrente può essere eliminato e l'attraversamento può quindi iterare al figlio rimanente.
La ricorsione non è altro che il processo di chiamata di una funzione dall'altra, solo questo processo viene fatto chiamando una funzione da sola. Come sappiamo quando una funzione chiama l'altra funzione, la prima funzione salva il suo stato (le sue variabili) e quindi passa il controllo alla funzione chiamata. La funzione chiamata può essere chiamata usando lo stesso nome di variabili ex fun1 (a) può chiamare fun2 (a). Quando facciamo chiamate ricorsive non succede nulla di nuovo. Una funzione si chiama passando lo stesso tipo e simili nelle variabili dei nomi (ma ovviamente i valori memorizzati nelle variabili sono diversi, solo il nome rimane uguale) a se stesso. Ma prima di ogni chiamata la funzione salva il suo stato e questo processo di salvataggio continua. IL RISPARMIO È FATTO SU UNA PILE.
ORA LO STACK È IN GIOCO.
Quindi, se scrivi un programma iterativo e salvi lo stato su uno stack ogni volta e poi fai uscire i valori dallo stack quando necessario, hai convertito con successo un programma ricorsivo in uno iterativo!
La dimostrazione è semplice e analitica.
Nella ricorsione il computer mantiene uno stack e nella versione iterativa dovrai mantenere lo stack manualmente.
Pensaci, basta convertire un programma ricorsivo di ricerca approfondita (su grafici) in un programma iterativo dfs.
Tutto il meglio!
Una descrizione approssimativa di come un sistema accetta qualsiasi funzione ricorsiva e la esegue usando uno stack:
Questo intendeva mostrare l'idea senza dettagli. Considera questa funzione che stamperebbe i nodi di un grafico:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
Ad esempio grafico: A- > B A- > C show (A) stamperebbe B, A, C
Chiamate di funzione significano salvare lo stato locale e il punto di continuazione in modo da poter tornare indietro, quindi saltare la funzione che si desidera chiamare.
Ad esempio, supponiamo che show (A) inizi a funzionare. La chiamata di funzione sulla linea 3. mostra (B) significa - Aggiungi elemento allo stack che significa " dovrai continuare alla riga 2 con nodo stato variabile locale = A " - Vai alla riga 0 con nodo = B.
Per eseguire il codice, il sistema esegue le istruzioni. Quando viene rilevata una chiamata di funzione, il sistema invia le informazioni necessarie per tornare al punto in cui si trovava, esegue il codice della funzione e, al termine della funzione, visualizza le informazioni su dove deve andare per continuare.
Questo link fornisce alcune spiegazioni e propone l'idea di mantenere " posizione " per essere in grado di raggiungere il posto esatto tra diverse chiamate ricorsive:
Tuttavia, tutti questi esempi descrivono scenari in cui una chiamata ricorsiva viene effettuata un fisso volte. Le cose si complicano quando hai qualcosa del tipo:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
Esiste un modo generale di convertire un attraversamento ricorsivo in iteratore usando un iteratore pigro che concatena più fornitori di iteratori (espressione lambda che restituisce un iteratore). Vedi il mio Conversione di Traversal ricorsivo in Iteratore .
Un altro esempio semplice e completo di trasformare la funzione ricorsiva in funzione iterativa usando lo stack.
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
