Cos'è la ricorsione e quando dovrei usarla?

Question

Uno degli argomenti che sembrano emergere regolarmente nelle mailing list e nelle discussioni online sono i meriti (o la mancanza di essi) di conseguire una laurea in Informatica.Un argomento che sembra emergere più e più volte a favore della parte negativa è che hanno codificato per un certo numero di anni e non hanno mai utilizzato la ricorsione.

Quindi la domanda è:

1. Cos'è la ricorsione?
2. Quando dovrei usare la ricorsione?
3. Perché le persone non usano la ricorsione?

Answer 1

Ci sono una serie di buone spiegazioni di ricorsione in questo thread, questa risposta riguarda il motivo per cui non dovresti usarlo nella maggior parte delle lingue.* Nella maggior parte delle principali implementazioni dei linguaggi imperativi (ad es.tutte le principali implementazioni di C, C++, Basic, Python, Ruby, Java e C#) iterazione è di gran lunga preferibile alla ricorsione.

Per capire perché, segui i passaggi utilizzati dai linguaggi sopra indicati per chiamare una funzione:

1. lo spazio è ritagliato la pila per gli argomenti della funzione e le variabili locali
2. gli argomenti della funzione vengono copiati in questo nuovo spazio
3. il controllo passa alla funzione
4. viene eseguito il codice della funzione
5. il risultato della funzione viene copiato in un valore restituito
6. la pila viene riavvolta nella posizione precedente
7. il controllo torna al punto in cui è stata chiamata la funzione

L'esecuzione di tutti questi passaggi richiede tempo, in genere leggermente superiore a quello necessario per scorrere un ciclo.Tuttavia, il vero problema è nel passaggio n. 1.Quando molti programmi vengono avviati, allocano un singolo pezzo di memoria per il loro stack e quando esauriscono quella memoria (spesso, ma non sempre a causa della ricorsione), il programma si blocca a causa di un errore. overflow dello stack.

Quindi in queste lingue la ricorsione è più lenta e ti rende vulnerabile al crash.Tuttavia ci sono ancora alcuni argomenti per utilizzarlo.In generale, il codice scritto ricorsivamente è più breve e un po’ più elegante, una volta che si sa come leggerlo.

Esiste una tecnica che gli implementatori del linguaggio possono utilizzare chiamata ottimizzazione delle chiamate in coda che può eliminare alcune classi di stack overflow.Detto in breve:se l'espressione restituita da una funzione è semplicemente il risultato di una chiamata di funzione, non è necessario aggiungere un nuovo livello allo stack, puoi riutilizzare quello corrente per la funzione che viene chiamata.Purtroppo, poche implementazioni di linguaggi imperativi hanno l'ottimizzazione delle chiamate di coda incorporata.

* Adoro la ricorsione. Il mio linguaggio statico preferito non usa affatto i cicli, la ricorsione è l'unico modo per fare qualcosa ripetutamente.Semplicemente non penso che la ricorsione sia generalmente una buona idea nelle lingue che non sono sintonizzate per essa.

** A proposito, Mario, il nome tipico per la tua funzione ArrangeString è "join" e sarei sorpreso se il tuo linguaggio preferito non ne avesse già un'implementazione.

Answer 2

Semplice esempio inglese di ricorsione.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Answer 3

Nel senso più elementare dell'informatica, la ricorsione è una funzione che richiama se stessa.Supponiamo che tu abbia una struttura di elenchi collegati:

struct Node {
    Node* next;
};

E vuoi scoprire quanto è lungo un elenco collegato puoi farlo con la ricorsione:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Questo potrebbe ovviamente essere fatto anche con un ciclo for, ma è utile come illustrazione del concetto)

Answer 4

Ogni volta che una funzione richiama se stessa, creando un ciclo, si parla di ricorsione.Come per ogni cosa, ci sono usi buoni e usi cattivi per la ricorsione.

L'esempio più semplice è la ricorsione in coda dove l'ultima riga della funzione è una chiamata a se stessa:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Tuttavia, questo è un esempio noioso, quasi inutile perché può essere facilmente sostituito da un’iterazione più efficiente.Dopotutto, la ricorsione soffre del sovraccarico delle chiamate di funzione, che nell'esempio precedente potrebbe essere sostanziale rispetto all'operazione all'interno della funzione stessa.

Quindi l'intera ragione per eseguire la ricorsione anziché l'iterazione dovrebbe essere quella di sfruttare il metodo stack di chiamate per fare delle cose intelligenti.Ad esempio, se chiami una funzione più volte con parametri diversi all'interno dello stesso ciclo, questo è un modo per realizzarlo ramificazione.Un classico esempio è il Triangolo di Sierpinski.

Puoi disegnarne uno molto semplicemente con la ricorsione, dove lo stack di chiamate si ramifica in 3 direzioni:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Se provi a fare la stessa cosa con l'iterazione, penso che scoprirai che ci vuole molto più codice per realizzarla.

Altri casi d'uso comuni potrebbero includere l'attraversamento delle gerarchie, ad es.crawler di siti web, confronti di directory, ecc.

Conclusione

In termini pratici, la ricorsione ha più senso ogni volta che è necessaria una ramificazione iterativa.

Answer 5

La ricorsione è un metodo per risolvere i problemi basato sulla mentalità del divide et impera.L'idea di base è prendere il problema originale e dividerlo in istanze più piccole (più facilmente risolvibili), risolvere quelle istanze più piccole (di solito utilizzando di nuovo lo stesso algoritmo) e quindi riassemblarle nella soluzione finale.

L'esempio canonico è una routine per generare il Fattoriale di n.Il Fattoriale di n si calcola moltiplicando tutti i numeri compresi tra 1 e n.Una soluzione iterativa in C# è simile alla seguente:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Non c'è nulla di sorprendente nella soluzione iterativa e dovrebbe avere senso per chiunque abbia familiarità con C#.

La soluzione ricorsiva si trova riconoscendo che l'n-esimo Fattoriale è n * Fatto(n-1).O per dirla in altro modo, se sai cos'è un particolare numero fattoriale puoi calcolare quello successivo.Ecco la soluzione ricorsiva in C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

La prima parte di questa funzione è conosciuta come a Caso base (o talvolta clausola di guardia) ed è ciò che impedisce all'algoritmo di funzionare per sempre.Restituisce semplicemente il valore 1 ogni volta che la funzione viene chiamata con un valore pari o inferiore a 1.La seconda parte è più interessante ed è conosciuta come Passo ricorsivo.Qui chiamiamo lo stesso metodo con un parametro leggermente modificato (lo decrementiamo di 1) e poi moltiplichiamo il risultato con la nostra copia di n.

Quando lo si incontra per la prima volta, questo può creare confusione, quindi è istruttivo esaminare come funziona quando viene eseguito.Immaginiamo di chiamare FactRec(5).Entriamo nella routine, non veniamo presi dal caso base e quindi finiamo così:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Se rientriamo nel metodo con il parametro 4 ancora una volta non siamo fermati dalla clausola di guardia e quindi ci ritroviamo a:

// In FactRec(4)
return 4 * FactRec(3);

Se sostituiamo questo valore restituito nel valore restituito sopra otteniamo

// In FactRec(5)
return 5 * (4 * FactRec(3));

Questo dovrebbe darti un'idea di come si arriva alla soluzione finale, quindi seguiremo un percorso rapido e mostreremo ogni passaggio verso il basso:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

La sostituzione finale avviene quando viene attivato il caso base.A questo punto abbiamo una semplice formula algrebrica da risolvere che equivale in primo luogo direttamente alla definizione di Fattoriali.

È istruttivo notare che ogni chiamata al metodo comporta l'attivazione di un caso base o una chiamata allo stesso metodo in cui i parametri sono più vicini a un caso base (spesso chiamata chiamata ricorsiva).In caso contrario, il metodo verrà eseguito per sempre.

Answer 6

La ricorsione risolve un problema con una funzione che chiama se stessa.Un buon esempio di ciò è una funzione fattoriale.Il fattoriale è un problema di matematica in cui il fattoriale di 5, ad esempio, è 5 * 4 * 3 * 2 * 1.Questa funzione risolve questo problema in C# per numeri interi positivi (non testato: potrebbe esserci un bug).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Answer 7

La ricorsione si riferisce a un metodo che risolve un problema risolvendo una versione più piccola del problema e quindi utilizzando quel risultato più qualche altro calcolo per formulare la risposta al problema originale.Spesso, nel processo di risoluzione della versione più piccola, il metodo risolverà una versione ancora più piccola del problema, e così via, fino a raggiungere un "caso base" che è banale da risolvere.

Ad esempio, per calcolare un fattoriale per il numero X, lo si può rappresentare come X times the factorial of X-1.Pertanto, il metodo "ricorre" per trovare il fattoriale di X-1, e poi moltiplica tutto ciò che ha ottenuto X per dare una risposta definitiva.Naturalmente, per trovare il fattoriale di X-1, per prima cosa calcolerà il fattoriale di X-2, e così via.Il caso base sarebbe quando X è 0 o 1, nel qual caso sa che tornerà 1 Da 0! = 1! = 1.

Answer 8

Considera un problema vecchio e ben noto:

In matematica, il massimo comun divisore (gcd) … di due o più numeri interi diversi da zero, è il più grande intero positivo che divide i numeri senza resto.

La definizione di MCD è sorprendentemente semplice:

dove mod è il operatore modulo (cioè il resto dopo la divisione intera).

In inglese, questa definizione dice che il massimo comun divisore di qualsiasi numero e zero è quel numero, e il massimo comun divisore di due numeri M E N è il massimo comun divisore di N e il resto dopo aver diviso M di N.

Se vuoi sapere perché funziona, consulta l'articolo di Wikipedia su Algoritmo euclideo.

Calcoliamo mcd(10, 8) come esempio.Ogni passaggio è uguale a quello immediatamente precedente:

1. MCD(10, 8)
2. mcd(10, 10 mod 8)
3. MCD(8, 2)
4. mcd(8, 8 mod 2)
5. MCD(2, 0)
6. 2

Nel primo passaggio, 8 non è uguale a zero, quindi si applica la seconda parte della definizione.10 mod 8 = 2 perché 8 sta nel 10 una volta con resto 2.Al passo 3 si applica nuovamente la seconda parte, ma questa volta 8 mod 2 = 0 perché 2 divide 8 senza resto.Al passaggio 5, il secondo argomento è 0, quindi la risposta è 2.

Hai notato che mcd appare sia sul lato sinistro che su quello destro del segno di uguale?Un matematico direbbe che questa definizione è ricorsiva a causa dell'espressione che stai definendo ricorre all'interno della sua definizione.

Le definizioni ricorsive tendono ad essere eleganti.Ad esempio, una definizione ricorsiva per la somma di una lista è

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

Dove head è il primo elemento di una lista e tail è il resto della lista.Notare che sum ricorre all'interno della sua definizione alla fine.

Forse preferiresti invece il valore massimo in un elenco:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Potresti definire ricorsivamente la moltiplicazione di interi non negativi per trasformarla in una serie di addizioni:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Se la trasformazione della moltiplicazione in una serie di addizioni non ha senso, prova ad espandere alcuni semplici esempi per vedere come funziona.

Unisci ordinamento ha una bella definizione ricorsiva:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Le definizioni ricorsive sono ovunque se sai cosa cercare.Nota come tutte queste definizioni hanno casi base molto semplici, per esempio., mcd(m, 0) = m.I casi ricorsivi riducono il problema per arrivare alle risposte facili.

Con questa comprensione, ora puoi apprezzare gli altri algoritmi presenti L'articolo di Wikipedia sulla ricorsione!

Answer 9

1. Una funzione che chiama se stessa
2. Quando una funzione può essere (facilmente) scomposta in una semplice operazione più la stessa funzione su una parte più piccola del problema.Dovrei dire, piuttosto, che questo lo rende un buon candidato per la ricorsione.
3. Loro fanno!

L'esempio canonico è il fattoriale che assomiglia a:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

In generale, la ricorsione non è necessariamente veloce (il sovraccarico delle chiamate di funzione tende ad essere elevato perché le funzioni ricorsive tendono ad essere piccole, vedere sopra) e può soffrire di alcuni problemi (stack overflow qualcuno?).Alcuni dicono che tendono ad essere difficili da ottenere "giusti" in casi non banali, ma io non ci credo davvero.In alcune situazioni, la ricorsione ha più senso ed è il modo più elegante e chiaro per scrivere una particolare funzione.Va notato che alcuni linguaggi preferiscono soluzioni ricorsive e le ottimizzano molto di più (mi viene in mente LISP).

Answer 10

Una funzione ricorsiva è una funzione che richiama se stessa.Il motivo più comune per cui ho scoperto di usarlo è l'attraversamento di una struttura ad albero.Ad esempio, se ho un TreeView con caselle di controllo (pensa all'installazione di un nuovo programma, alla pagina "scegli le funzionalità da installare"), potrei desiderare un pulsante "seleziona tutto" che sarebbe qualcosa del genere (pseudocodice):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Quindi puoi vedere che checkRecursively controlla prima il nodo a cui viene passato, quindi chiama se stesso per ciascuno dei figli di quel nodo.

Bisogna stare un po' attenti con la ricorsione.Se entri in un ciclo ricorsivo infinito, otterrai un'eccezione Stack Overflow :)

Non riesco a pensare a un motivo per cui le persone non dovrebbero usarlo, quando appropriato.È utile in alcune circostanze e non in altre.

Penso che, poiché è una tecnica interessante, alcuni programmatori forse finiscono per usarla più spesso di quanto dovrebbero, senza una reale giustificazione.Ciò ha dato alla ricorsione una cattiva reputazione in alcuni ambienti.

Answer 11

La ricorsione è un'espressione che fa riferimento direttamente o indirettamente a se stessa.

Considera gli acronimi ricorsivi come un semplice esempio:

• GNU sta per GNU non è Unix
• PHP sta per PHP:Preprocessore Ipertestuale
• YAML sta per YAML non è un linguaggio di markup
• VINO sta per Il vino non è un emulatore
• VISA sta per Associazione dei servizi internazionali Visa

Altri esempi su Wikipedia

Answer 12

La ricorsione funziona meglio con quelli che mi piace chiamare "problemi frattali", dove hai a che fare con una cosa grande fatta di versioni più piccole di quella cosa grande, ognuna delle quali è una versione ancora più piccola della cosa grande, e così via.Se mai dovessi attraversare o cercare qualcosa come un albero o strutture identiche annidate, hai un problema che potrebbe essere un buon candidato per la ricorsione.

Le persone evitano la ricorsione per una serie di motivi:

1. La maggior parte delle persone (me compreso) si è fatto le ossa con la programmazione procedurale o orientata agli oggetti in contrapposizione alla programmazione funzionale.Per queste persone, l'approccio iterativo (in genere utilizzando i loop) sembra più naturale.

2. A quelli di noi che si sono fatti le ossa nella programmazione procedurale o orientata agli oggetti è stato spesso detto di evitare la ricorsione perché è soggetta a errori.

3. Ci viene spesso detto che la ricorsione è lenta.Chiamare e ritornare ripetutamente da una routine implica un sacco di push e pop dello stack, che è più lento del looping.Penso che alcuni linguaggi gestiscano questo problema meglio di altri, e quei linguaggi molto probabilmente non sono quelli in cui il paradigma dominante è procedurale o orientato agli oggetti.

4. Per almeno un paio di linguaggi di programmazione che ho usato, ricordo di aver sentito i consigli di non usare la ricorsione se supera una certa profondità perché il suo stack non è così profondo.

Answer 13

Un'istruzione ricorsiva è quella in cui definisci il processo di cosa fare dopo come una combinazione degli input e di ciò che hai già fatto.

Prendiamo ad esempio il fattoriale:

factorial(6) = 6*5*4*3*2*1

Ma è facile vedere anche factorial(6) è:

6 * factorial(5) = 6*(5*4*3*2*1).

Quindi in generale:

factorial(n) = n*factorial(n-1)

Naturalmente, la difficoltà della ricorsione è che se si vogliono definire le cose in termini di ciò che si è già fatto, è necessario che ci sia un punto da cui iniziare.

In questo esempio, creiamo semplicemente un caso speciale definendo fattoriale(1) = 1.

Ora lo vediamo dal basso verso l'alto:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Poiché abbiamo definito fattoriale(1) = 1, raggiungiamo il "fondo".

In generale, le procedure ricorsive sono costituite da due parti:

1) La parte ricorsiva, che definisce alcune procedure in termini di nuovi input combinati con ciò che hai "già fatto" tramite la stessa procedura.(cioè. factorial(n) = n*factorial(n-1))

2) Una parte di base, che assicura che il processo non si ripeta all'infinito dandogli un punto da cui iniziare (ad es. factorial(1) = 1)

All'inizio può creare un po' di confusione, ma basta guardare una serie di esempi e tutto dovrebbe combaciare.Se vuoi una comprensione molto più profonda del concetto, studia l'induzione matematica.Inoltre, tieni presente che alcune lingue ottimizzano per le chiamate ricorsive mentre altre no.È abbastanza facile creare funzioni ricorsive incredibilmente lente se non stai attento, ma ci sono anche tecniche per renderle performanti nella maggior parte dei casi.

Spero che questo ti aiuti...

Answer 14

Mi piace questa definizione:
Nella ricorsione, una routine risolve essa stessa una piccola parte di un problema, divide il problema in parti più piccole e poi richiama se stessa per risolvere ciascuna delle parti più piccole.

Mi piace anche la discussione di Steve McConnell sulla ricorsione in Code Complete dove critica gli esempi usati nei libri di informatica sulla ricorsione.

Non utilizzare la ricorsione per i fattoriali o i numeri di Fibonacci

Un problema con i libri di testo per la scienza del computer è che presentano sciocchi esempi di ricorsione.Gli esempi tipici stanno calcolando un fattoriale o calcolando una sequenza di Fibonacci.La ricorsione è uno strumento potente ed è davvero stupido usarlo in uno di questi casi.Se un programmatore che lavorava per me usasse una ricorsione per calcolare un fattoriale, assumerei qualcun altro.

Ho pensato che questo fosse un punto molto interessante da sollevare e potrebbe essere un motivo per cui la ricorsione viene spesso fraintesa.

MODIFICARE:Questa non era una frecciatina alla risposta di Dav: non avevo visto quella risposta quando l'ho postata

Answer 15

1.) un metodo è ricorsivo se può chiamarsi;o direttamente:

void f() {
   ... f() ... 
}

o indirettamente:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Quando utilizzare la ricorsione

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Le persone usano la ricorsione solo quando è molto complesso scrivere codice iterativo.Ad esempio, le tecniche di attraversamento degli alberi come preorder e postorder possono essere rese sia iterative che ricorsive.Ma di solito usiamo il ricorsivo per la sua semplicità.

Answer 16

Ecco un semplice esempio:quanti elementi in un insieme.(ci sono modi migliori per contare le cose, ma questo è un bell'esempio ricorsivo semplice.)

Innanzitutto, abbiamo bisogno di due regole:

1. se l'insieme è vuoto, il conteggio degli elementi nell'insieme è zero (duh!).
2. se l'insieme non è vuoto, il conteggio è uno più il numero di elementi nell'insieme dopo la rimozione di un elemento.

Supponiamo di avere un set come questo:[xxx].contiamo quanti elementi ci sono.

1. l'insieme è [x x x] che non è vuoto, quindi applichiamo la regola 2.il numero di elementi è uno più il numero di elementi in [x x] (cioèabbiamo rimosso un elemento).
2. l'insieme è [x x], quindi applichiamo nuovamente la regola 2:uno + numero di elementi in [x].
3. il set è [x], che corrisponde ancora alla regola 2:uno + numero di elementi in [].
4. Ora il set è [], che corrisponde alla regola 1:il conteggio è zero!
5. Ora che conosciamo la risposta al passaggio 4 (0), possiamo risolvere il passaggio 3 (1 + 0)
6. Allo stesso modo, ora che conosciamo la risposta al passaggio 3 (1), possiamo risolvere il passaggio 2 (1 + 1)
7. E finalmente, ora che conosciamo la risposta al passaggio 2 (2), possiamo risolvere il passaggio 1 (1 + 2) e ottenere il conteggio degli elementi in [x x x], che è 3.Evviva!

Possiamo rappresentare questo come:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Quando applichi una soluzione ricorsiva, di solito hai almeno 2 regole:

• la base, il caso semplice che indica cosa succede quando hai "esaurito" tutti i tuoi dati.Di solito si tratta di una variazione di "se non hai dati da elaborare, la tua risposta è X"
• la regola ricorsiva, che stabilisce cosa succede se hai ancora dati.Di solito si tratta di una sorta di regola che dice "fai qualcosa per ridurre le dimensioni del tuo set di dati e riapplica le tue regole al set di dati più piccolo".

Se traduciamo quanto sopra in pseudocodice, otteniamo:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Ci sono molti altri esempi utili (attraversare un albero, per esempio) che sono sicuro che altre persone tratteranno.

Answer 17

Bene, questa è una definizione abbastanza decente che hai.E anche Wikipedia ha una buona definizione.Quindi aggiungerò per te un'altra definizione (probabilmente peggiore).

Quando le persone fanno riferimento alla "ricorsione", di solito parlano di una funzione che hanno scritto e che richiama se stessa ripetutamente finché non ha terminato il suo lavoro.La ricorsione può essere utile quando si attraversano le gerarchie nelle strutture dati.

Answer 18

Un esempio:Una definizione ricorsiva di scala è:Una scala è composta da:- un singolo passaggio e una scala (ricorsione) - o solo un singolo passaggio (terminazione)

Answer 19

Per ricorrere a un problema risolto:non fare nulla, il gioco è fatto.
Per ricorrere ad un problema aperto:fai il passo successivo, poi ricorsi al resto.

Answer 20

In parole povere:Supponiamo che tu possa fare 3 cose:

1. Prendi una mela
2. Annota i segni di conteggio
3. Contare i segni di conteggio

Hai molte mele davanti a te su un tavolo e vuoi sapere quante mele ci sono.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Il processo di ripetere la stessa cosa finché non hai finito si chiama ricorsione.

Spero che questa sia la risposta in "inglese semplice" che stai cercando!

Answer 21

Una funzione ricorsiva è una funzione che contiene una chiamata a se stessa.Una struttura ricorsiva è una struttura che contiene un'istanza di se stessa.Puoi combinare i due come una classe ricorsiva.La parte fondamentale di un elemento ricorsivo è che contiene un'istanza/chiamata di se stesso.

Consideriamo due specchi uno di fronte all'altro.Abbiamo visto il netto effetto infinito che creano.Ogni riflessione è un'istanza di uno specchio, che è contenuta all'interno di un'altra istanza di uno specchio, ecc.Lo specchio che contiene il riflesso di se stesso è la ricorsione.

UN albero di ricerca binario è un buon esempio di programmazione di ricorsione.La struttura è ricorsiva con ciascun nodo contenente 2 istanze di un nodo.Anche le funzioni per lavorare su un albero di ricerca binario sono ricorsive.

Answer 22

Questa è una vecchia domanda, ma voglio aggiungere una risposta dal punto di vista logistico (cioè non dal punto di vista della correttezza dell'algoritmo o dal punto di vista delle prestazioni).

Utilizzo Java per lavoro e Java non supporta la funzione annidata.Pertanto, se voglio eseguire la ricorsione, potrei dover definire una funzione esterna (che esiste solo perché il mio codice si scontra con le regole burocratiche di Java), oppure potrei dover rifattorizzare del tutto il codice (cosa che odio davvero fare).

Pertanto, spesso evito la ricorsione e utilizzo invece l'operazione sullo stack, poiché la ricorsione stessa è essenzialmente un'operazione sullo stack.

Answer 23

Vuoi usarlo ogni volta che hai una struttura ad albero.È molto utile per leggere XML.

Answer 24

La ricorsione applicata alla programmazione consiste fondamentalmente nel chiamare una funzione dall'interno della sua stessa definizione (dentro se stessa), con parametri diversi in modo da svolgere un compito.

Answer 25

"Se ho un martello, faccio sembrare tutto un chiodo."

La ricorsione è una strategia di risoluzione dei problemi per Enorme problemi, dove ad ogni passo semplicemente "trasforma 2 piccole cose in una cosa più grande", ogni volta con lo stesso martello.

Esempio

Supponiamo che la tua scrivania sia ricoperta da un disordine di 1024 fogli.Come si fa a creare una pila di fogli ordinata e pulita dal disordine, usando la ricorsione?

1. Dividere: Distribuisci tutti i fogli in modo da avere solo un foglio in ogni "pila".
2. Conquistare:
   2. Fai il giro, mettendo ogni foglio sopra un altro foglio.Ora hai pile da 2.
   3. Fai un giro, mettendo ogni pila da 2 sopra un'altra pila da 2.Ora hai pile da 4.
   4. Fai un giro, mettendo ogni pila da 4 sopra un'altra pila da 4.Ora hai pile da 8.
   5. ...ancora e ancora ...
   6. Ora hai un'enorme pila di 1024 fogli!

Nota che questo è abbastanza intuitivo, a parte contare tutto (che non è strettamente necessario).In realtà potresti non arrivare fino alle pile di 1 foglio, ma potresti e funzionerebbe comunque.La parte importante è il martello:Con le tue braccia, puoi sempre mettere una pila sopra l'altra per creare una pila più grande, e non importa (entro limiti ragionevoli) quanto sia grande una pila.

Answer 26

La ricorsione è il processo in cui un metodo chiama se stesso per poter eseguire una determinata attività.Riduce la ridondanza del codice.La maggior parte delle funzioni o dei metodi ricorsivi devono avere una condizione per interrompere la chiamata ricorsiva, ad es.impediscigli di richiamare se stesso se una condizione è soddisfatta: questo impedisce la creazione di un ciclo infinito.Non tutte le funzioni sono adatte per essere utilizzate in modo ricorsivo.

Answer 27

ehi, scusa se la mia opinione è d'accordo con qualcuno, sto solo cercando di spiegare la ricorsione in un inglese semplice.

supponiamo di avere tre manager: Jack, John e Morgan.Jack gestisce 2 programmatori, John - 3 e Morgan - 5.darai a ogni manager 300 $ e vorrai sapere quanto costerebbe.La risposta è ovvia: ma cosa succederebbe se due dipendenti di Morgan fossero anche manager?

QUI arriva la ricorsione.inizi dal vertice della gerarchia.il costo estivo è 0$.Inizi con Jack, quindi controlla se ha manager come dipendenti.se trovi che qualcuno di loro lo è, controlla se hanno dei manager come dipendenti e così via.Aggiungi 300$ al costo estivo ogni volta che trovi un manager.quando avrete finito con Jack andate da John, dai suoi dipendenti e poi da Morgan.

Non saprai mai quanti cicli dovrai ripetere prima di ottenere una risposta, anche se sai quanti manager hai e quanto budget puoi spendere.

La ricorsione è un albero, con rami e foglie, chiamati rispettivamente genitori e figli.Quando usi un algoritmo di ricorsione, più o meno consapevolmente stai costruendo un albero a partire dai dati.

Answer 28

In parole povere, ricorsione significa ripetere qualcosa ancora e ancora.

Nella programmazione un esempio è quello di richiamare la funzione al suo interno.

Guarda il seguente esempio di calcolo fattoriale di un numero:

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

Answer 29

Qualsiasi algoritmo viene visualizzato strutturale la ricorsione su un tipo di dati consiste fondamentalmente in un'istruzione switch con un caso per ciascun caso del tipo di dati.

ad esempio, quando lavori su un tipo

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

un algoritmo ricorsivo strutturale avrebbe la forma

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

questo è davvero il modo più ovvio per scrivere qualsiasi algoritmo che funzioni su una struttura dati.

ora, quando guardi gli interi (beh, i numeri naturali) come definiti usando gli assiomi di Peano

 integer = 0 | succ(integer)

vedi che un algoritmo ricorsivo strutturale sugli interi assomiglia a questo

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

La funzione fattoriale troppo nota riguarda l'esempio più banale di questa forma.

Answer 30

la funzione richiama se stessa o utilizza la propria definizione.