Come dovresti affrontare la ricorsione?

Attualmente sto studiando la ricorsione a scuola e ho difficoltà a pensare ai metodi quando ci sono molte chiamate ricorsive. Voglio solo chiedere come dovresti pensare alla ricorsione perché so che tracciare le chiamate del metodo da parte di ogni passaggio diventerà troppo noioso.

Invece di tracciare ogni chiamata ricorsiva, la cosa che abbiamo brevemente trattato stava pensando alla ricorsione per induzione, ma il problema che ho è vedere come l’induzione può essere applicata a situazioni diverse dalla matematica. Come se ci fosse un metodo che stampa in modo ricorsivo numeri come questo:

public void blah(int n) { for (int i = 0; i < n; i++) blah(i); System.out.print(n); } 

Ho problemi a pensare a ciò che viene stampato, e non riesco a vedere come l’induzione possa essere rilevante qui (scusami se non posso usarla ovunque).

Ma immagino che la mia vera domanda sia come puoi affrontare la ricorsione senza dover tracciare ogni singola chiamata di metodo? È la cosa migliore da fare solo per vedere il caso base e il tipo di lavoro all’indietro? (Ma anche allora penso di essere confuso su cosa succede).

come puoi affrontare la ricorsione senza dover tracciare ogni singola chiamata di metodo?

Ci sono diversi modi per “capire” i programmi ricorsivi – uno implica pensare a una chiamata ricorsiva come una scatola nera, e l’altro richiede “suonare” alcuni casi e indovinare il modello.

Il primo metodo presuppone che il metodo ricorsivo sia già stato scritto e che faccia qualche cosa nota. Questo è utile quando si pensa ai parser di discesa ricorsivi; non è buono per i programmi che producono output (al contrario del consumo di input), come il tuo.

Il secondo metodo è più applicabile a programmi simili al tuo esempio. Riproducilo per i valori 0, 1, 2 e 3.

 0 - 0 1 - 0 1 2 - 0 0 1 2 3 - 0 0 1 0 0 1 2 3 

Hai notato lo schema? L’output per N elenca gli output per gli elementi precedenti N-1 e stampa N alla fine. Una volta che pensi di poter continuare il modello, sai di avere una comprensione del tuo programma ricorsivo.

Puoi trovare una bella spiegazione su Pensare ricorsivamente qui

Dal link

  • Scrivi un prototipo per la funzione ricorsiva.

  • Scrivi un commento che descriva cosa fa la funzione.

  • Determina il caso base (ce ne possono essere più di uno) e le sue soluzioni.

  • Determina quale piccolo problema (o problemi) risolvere. Se ti aiuta a seguire più facilmente, salva le soluzioni nel più piccolo
    problemi alle variabili locali (es., piccolo nell’esempio sum ()) .ASSUME la chiamata ricorsiva funziona

  • Utilizzare le soluzioni del problema più piccolo per risolvere il problema più grande. (Se questo è fatto in modo non corretto, le soluzioni del più piccolo
    i problemi saranno anche calcolati in modo errato, quindi, il presupposto in
    il passaggio precedente fallirà).

Ecco come penso alla ricorsione. È piuttosto semplice, in realtà.

  • Cosa devo fare per smettere? Questo è noto come caso base.
  • Cosa faccio se non ho ancora finito?

Prendiamo ad esempio il classico problema ricorsivo: F (n) = n !. 0! è definito come 1 e qualsiasi altra cosa maggiore di 0 è definita come n * F (n-1)

In questo esempio, incontro le mie due condizioni: mi fermo quando prendo 0! E moltiplichiamo qualsiasi valore che ho per il valore (n-1) th.

Un altro approccio che uso: se può essere fatto in modo ricorsivo, può essere fatto in modo iterativo. Vale a dire, se posso scrivere un ciclo per eseguire lo stesso compito, allora posso scrivere un metodo ricorsivo per eseguire anche l’operazione. Spesso è più semplice pensare a determinati problemi in modo ricorsivo (ad es. La funzione di Ackermann ), e altri in modo iterativo (ad es. Camminare lungo una lista collegata).

Vorresti usare l’iterazione dove preferisci.

Non sono sicuro di come dirti di pensarci, ma penso che questo potrebbe aiutarti a capire come appare il stream. Puoi averne un’idea dopo averlo codificato per un po ‘, ma molte persone lo evitano solo perché li fanno sentire pignoli. Mi scuso per il fatto che non è codificato in Java, ma non si tratta del codice relativo a ciò che viene stampato, quindi basta eseguirlo su qualsiasi box Linux o cygwin.

  perl -e 'sub foo {my $n =shift;my $depth=shift;print "\t"x$depth;print "blah($n)\n";for(my $i=0;$i<$n;$i++){foo($i,$depth+1)};print "\t"x$depth;print $n,"\n"};foo(shift);' 5 

Chiamato con un arg di 3 questo è quello che sembra:

  blah(3) blah(0) 0 blah(1) blah(0) 0 1 blah(2) blah(0) 0 blah(1) blah(0) 0 1 2 3 

Provo come qualcun altro ha detto di visualizzarlo in componenti più piccoli. IE Qual è la funzione che esegue oltre alla ricorsione. In questo caso la funzione conta da 0 a qualche numero. Ora considera in che cosa fa la ricorsione. Per ogni conteggio inizia un nuovo conteggio fino al numero che ha raggiunto. Spesso scopro che aiuta a suddividerlo in più di una funzione in modo tale che ciò che fa realmente sia incapsulato e la ricorsione separata, ma ciò rende la ricorsione meno ovvia.

Penso che aiuti anche a usare problemi del mondo reale, come attraversare una gerarchia di directory o un'altra struttura ad albero.

Il tuo esempio verrà stampato

 0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4 

Se chiamato con blah (4).

In generale, in caso di ricorrenza, assicurati di gestire prima il caso base. Dopo di ciò, gestisci lo stato della ricorsione, quindi la logica può arrivare.

In questo esempio, il controllo del caso base è i < n e si verificherà prima a 0 < 0 che non è vero e interromperà il ciclo for stampando 0. Quindi verrà eseguita l'iterazione successiva, che deve passare da i = 0 to 1 < 1 che stampa nuovamente 0 dopo aver chiamato i = 0 <0. Quindi finisce il ciclo e viene stampato 1. Poi è il turno di 2 secondi, lol. E così via per la linea fino a quando ogni numero ha avuto il suo turno.

Quindi sarò il più schietto qui, o avrai la ricorsione o non lo farai e non c’è assolutamente nulla di sbagliato in questo. È solo una di quelle cose che separa i programmatori ( triste ma vero secondo Joel ). Ora per spiegare la ricorsione come se fossi in cinque è dove il compito diventa un po ‘torbido. Immagina di avere quattro (4) mele e ogni volta che ti chiedo di contarle prendi una delle tue mele e dammela. La prima volta che parlo con te mi dirai che hai quattro mele e ne poni una a me. Ora continuiamo questo processo fino a quando non hai zero mele, questo sarà analogo a quello che altri hanno chiamato il base case o l’ exit statement che garantisce che la tua funzione si interrompa.

Ora, non hai più cinque anni, se ti chiedessi di dimostrare che per tutte le istanze di N che questo funzionerebbe, come faresti? Questo è ciò a cui ti rivolge il tuo professore quando afferma di risolvere un problema per induzione. Un esempio di come risolvere per induzione sarebbe il seguente: ho sei lattine di Mountain Dew sulla mia scrivania e sono in procinto di bere uno di loro. Dico “Wow, questa lattina di Mountain Dew sa di arcobaleno elettrico”. Userei l’induzione per dire che le altre cinque lattine e per estensione tutte le lattine di Mountain Dew hanno un sapore come arcobaleni elettrici. Quindi, nel caso della ricorsione, si dimostra che una funzione terminerà e sarà corretta utilizzando lo stesso processo.

Può aiutare a risolvere un’istanza “banale” del problema come blah(0) and blah(1) and blah(2) questo vi mostrerà che la soluzione tende nella direzione che anticipate così come il fatto che potete usa l’induzione per dire che questo processo terminerà dato qualsiasi input N