Fino a che la ricorsione eseguire nella vostra funzione in C ++?
https://stackoverflow.com/questions/779282
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
ho scritto funzioni ricorsive con la guida di un amico che sta insegnando mi C ++ (come prima lingua). Comunque, io non capisco cosa sta succedendo. Lui mi ha aiutato (e la comunità SO, pure) scrivere la funzione di merge sort.
std::vector<int> mergeSort(std::vector<int> original)
//code here to create two vectors, farray and sarray, out of the
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int
farray = mergeSort(farray);
sarray = mergeSort(sarray);
//code here merges the two into a single, final sorted std::vector
In questa funzione, assegno:
farray = mergeSort(farray);
sarray = mergeSort(sarray);
Che cosa sta succedendo qui? Chiede Mergesort con Farray e Sarray come parametri e cambia il valore. Fino a che Mergesort esegue in se stessa in modo ricorsivo? Proprio fino alla chiamata di funzione ricorsiva?
Soluzione
Ogni volta che si chiama una funzione in modo ricorsivo, si fa in modo efficace una nuova copia delle informazioni di cui ha bisogno, e va avanti.
Si potrebbe avere un programma che ricorre "infinitamente", vale a dire, fino a quando non esaurisce le risorse, di solito pila spazio - lo spazio in cui tali copie sono in corso. Che sarebbe simile
void recur(){
recur();
}
int main(){
recur();
exit(0); /* won't ever really get here.*/
}
Ovviamente, questo non è molto utile, così si vuole scrivere un programma che ha un certo limite di come spesso si ripete. Ecco un molto semplice programma che gestisce che:
#include <iostream>
using namespace std;
void recurSome(int count){
cout << "RecurSome called with " << count << endl;
if (count > 0){
recurSome(count-1);
cout << "Back at " << count << endl;
}else{
cout << "Bottom." << endl;
}
return;
}
int main(){
recurSome(10);
exit(0); /* now it will get here. */
}
Se compilate ed eseguite che, dire con:
bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc
Si otterrà i risultati:
RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $
Vedi come viene chiamato per 10, poi 9, e così via, e poi dopo aver raggiunto il fondo, lo dimostra a tornare per 1, poi 2, e così via indietro fino alla 10?
La regola di base è che tutti funzione ricorsiva deve avere qualcosa che lo rende un caso base, quella che fa chiamare se stesso ancora una volta. In questo, il caso base è count == 0 e infatti abbiamo potuto scrivere questo come una definizione ricorsiva
recursome:
se c = 0: fondo stampa
se c> 0: conteggio di stampa e recursome (c-1)
Vedrai molte definizioni ricorsive del genere come ci si sposta su in matematica.
Ecco una versione un po 'niftier C con una migliore uscita:
#include <stdio.h>
#include <stdlib.h>
int max = 10;
void recurSome(int count){
printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
if (count > 0){
recurSome(count-1);
printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
}else{
printf("RecurSome %*c Bottom.\n", 2*max, ' ');
printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
}
return;
}
int main(){
recurSome(max);
exit(0); /* now it will get here. */
}
Output:
RecurSome Called with 10
RecurSome Called with 9
RecurSome Called with 8
RecurSome Called with 7
RecurSome Called with 6
RecurSome Called with 5
RecurSome Called with 4
RecurSome Called with 3
RecurSome Called with 2
RecurSome Called with 1
RecurSome Called with 0
RecurSome Bottom.
RecurSome Back at 0
RecurSome Back at 1
RecurSome Back at 2
RecurSome Back at 3
RecurSome Back at 4
RecurSome Back at 5
RecurSome Back at 6
RecurSome Back at 7
RecurSome Back at 8
RecurSome Back at 9
RecurSome Back at 10
Altri suggerimenti
Check it out nel dizionario:
ricorsione : sostantivo. vedi ricorsione
Ora, sul serio, nello scherzo sopra, la definizione di ricorsione è dato in termini di ricorsione stessa. Questo è ricorsione.
Un algoritmo ricorsivo è un algoritmo la cui attuazione si basa sulla stesso algoritmo. Il processo di sviluppo di un tale algoritmo inizia con il caso più semplice, la cui soluzione è sia noto in anticipo o può essere banalmente calcolato. Poi si definisce l'algoritmo in termini di per sé.
Come semplice esempio, il calcolo della potenza n-esima di un dato intero i potrebbe essere un power( int number, int power ) funzione. Come hai potuto attuarlo? in molti modi. Il più semplice è una chiamata a una libreria, seguito da un ciclo, o si potrebbe definire una funzione in termini di per sé:
int power( int number, unsigned int pow )
{
// Basic trivial case, cuts the recursion:
if ( pow == 0 ) return 1;
// Implement power in terms of itself:
return number * power( number, pow-1 );
}
int main()
{
int power = power( 2, 10 );
}
Abbiamo definito la funzione in termini di sé. Si inizia con il caso più semplice (n ^ 0 = 1). Se non siamo nel caso più semplice, è possibile esprimere l'algoritmo in termini di sé.
Il programma dovrebbe iniziare nel principale chiamando power( 2, 10 ) che ricorsione e chiamare power( 2, 9 ) ridurre il problema ad un piccolo problema e sarebbe poi comporre la risposta definitiva in termini del problema più semplice.
La traccia chiamata actuall potrebbe essere:
power( 2, 5 )
power( 2, 4 )
power( 2, 3 )
power( 2, 2 )
power( 2, 1 )
power( 2, 0 ) // simplest case: return 1
return 2 * 1 -> 2 // obtain next solution in terms of previous
return 2 * 2 -> 4
return 2 * 4 -> 8
return 2 * 8 -> 16
return 2 * 16 -> 32
Durante lo sviluppo di algoritmi ricorsivi di solito mi ha aiutato a credere che ho già avuto l'algoritmo in funzione e solo di lavoro sulla riduzione / composizione del nuovo risultato.
ricorsione può essere intesa come applicazione pratica del principio di induzione. Per dimostrare una dichiarazione P (n) per ogni n dove P (n) significa "La somma dei numeri interi da 1 a n è n (n + 1) / 2" dobbiamo dimostrare due cose:
- caso Base: P (n) vale per un intero specifica. P (1) è vero perché 1 = 1 (1 + 1) / 2.
- caso induttivo: Se P (n) è vera, allora P (n + 1) deve essere vero. 1 + ... + n + (n + 1) = n (n + 1) / 2 + (n + 1) = n (n + 1) / 2 + 2 (n + 1) / 2 = (n + 1) ((n + 1) + 1) / 2, che è la statment P (n + 1).
Allo stesso modo, in una funzione ricorsiva come Mergesort abbiamo bisogno di gestire due casi:
- caso Base: Se l'array ha un elemento, è ordinato; altrimenti
- caso ricorsivo:. Dividere la matrice in due matrici più piccole, mergesort ciascuno di essi, e fonderli insieme
La chiave è che i due array sono piccolo di quella originale, altrimenti uno di loro sarà mai colpito il caso base. Poiché gli array sono divisi approssimativamente a metà, la profondità della ricorsione sarà di circa log2 (n) in questo caso.
Per quanto riguarda il codice in questione va, ci sono tre questioni:
- Il caso base manca.
- Riusare le variabili Farray e Sarray non è strettamente necessario e può essere fonte di confusione.
- Il codice sarà molto lenta a causa del numero di std :: vettori che vengono creati e distrutti. La migliore interfaccia per Mergesort richiede due vettori :: iteratori come input, simile alla funzione std :: sort ().
I nuovi programmatori dovrebbero provare a eseguire Mergesort con carta e matita.
Per una funzione ricorsiva di non essere infinito, ci deve essere qualche condizione in cui si ritorna senza chiamare in sé. Per alcuni algoritmi, tale condizione è il punto in cui eseguire la chiamata dei dati rende più senso.
Nel tuo caso, se si divide il passato-in vettoriale e finire con due vettori che ogni contengono solo 1 punto, ha senso chiamare mergesort () su di loro? N
Si potrebbe gestire questo ispezionando la dimensione del Farray e Sarray e decidere se chiamare mergesort () su uno o entrambi prima di combinarli e restituendo la combinazione.
Che cosa succede se uno ha 2 articoli e uno ha 1? Chiamare mergesort () dalla dimensione 2, ma non dalle dimensioni 1.
Quando una chiamata a mergesort () non chiama mergesort () su entrambi Farray o Sarray prima di tornare, la ricorsione inizierà svolgimento.
Dai un'occhiata alla pagina di Wikipedia per merge sort Per ulteriori informazioni su ciò che si' stiamo cercando di fare.
Come sidenote, essere consapevoli del fatto che si sta facendo una copia di ogni vettore si è dato come parametro. Utilizzare vector <> const & anziché.
