[RIPRODUZIONE DI BRANI MUSICALI] 

DOUG LLOYD: Probabilmente pensate che codice è solo utilizzato per eseguire un compito. Si scrive fuori. Si fa qualcosa. Che è praticamente esso. 

Si compila. Si esegue il programma. Tu sei a posto. 

Ma che ci crediate o no, se si codifica per un lungo periodo di tempo, in realtà si potrebbe venire a vedere codice come qualcosa che è bello. Risolve un problema in un modo molto interessante, o c'è solo qualcosa di veramente accurata circa il suo aspetto. Si potrebbe ridere a me, ma è vero. E ricorsione è un modo per una sorta di ottenere questa idea di bello, codice elegante aspetto. Risolve i problemi in modi che sono interessanti, facile da visualizzare, e sorprendentemente breve. 

Le opere modo ricorsione è una funzione ricorsiva è definita come una funzione che chiama sé come parte della sua esecuzione. Questo potrebbe sembrare un po 'strano, e vedremo un po ' su come funziona in un attimo. Ma ancora una volta, si tratta procedure ricorsive sono sta per essere così elegante perché stanno andando per risolvere questo problema senza avendo tutte queste altre funzioni o questi lunghi cicli. Vedrai che questi ricorsiva le procedure stanno andando a guardare così breve. E hanno davvero intenzione di fare il codice aspetto molto più bello. 

Vi darò un esempio di questo per vedere come una procedura ricorsiva potrebbe essere definito. Quindi, se si ha familiarità con questo dalla classe di matematica molti anni fa, c'è qualcosa chiamato il funzione fattoriale, che è di solito indicato come un punto esclamativo, che è definito su tutti gli interi positivi. E il modo in cui n fattoriale viene calcolato è si moltiplicano tutti i numeri meno o uguale together-- n tutti gli interi meno o uguale a n insieme. 

Quindi 5 fattoriale è 5 volte 4 volte 3 volte 2 volte 1. E 4 fattoriale è 4 volte 3 volte 2 volte 1 e così via. Si ottiene l'idea. 

Mentre i programmatori, non lo facciamo utilizzare n, punto esclamativo. Quindi dovremo definire il fattoriale funzione di realtà di n. E useremo fattoriale per creare una soluzione ricorsiva di un problema. E penso che si potrebbe trovare che è molto più visivamente appello che l'iterativo versione di questo, che ci sarà anche uno sguardo a in un attimo. 

Quindi, ecco un paio di gioco di parole facts-- intended-- factorial-- sulla funzione fattoriale. Il fattoriale di 1, come ho detto, è di 1. Il fattoriale di 2 è 2 volte 1. Il fattoriale di 3 è 3 per 2 per 1, e così via. Abbiamo parlato di 4 e 5 già. 

Ma guardando questo, non è vero? Non è fattoriale di 2 soli 2 volte il fattoriale di 1? Voglio dire, il fattoriale di 1 a 1. Allora, perché non possiamo solo dire che, poiché fattoriale di 2 è 2 volte 1, E 'davvero solo 2 volte il fattoriale di 1? 

E poi estendere tale idea, Non è il fattoriale di 3 solo 3 volte il fattoriale di 2? E il fattoriale di 4 è 4 volte il fattoriale di 3, e così via? Infatti, il fattoriale di un qualsiasi numero può solo essere espressa se noi genere di portare questo fuori per sempre. Possiamo tipo di generalizzare il problema fattoriale Come è N volte il fattoriale di n meno 1. E 'n volte il prodotto tutti i numeri meno di me. 

Questa idea, questo generalizzazione del problema, ci permette in modo ricorsivo definire la funzione fattoriale. Quando si definisce una funzione ricorsivamente, c'è due cose che devono essere una parte di esso. È necessario disporre di qualcosa chiamato un scenario di base, i quali, quando si attiva esso, si fermerà il processo ricorsivo. 

Altrimenti, una funzione che chiama itself-- come si potrebbe imagine-- potrebbe andare avanti per sempre. Funzione chiama la funzione invita le chiamate di funzione la funzione chiama la funzione. Se non si dispone di un modo per fermarlo, il programma saranno effettivamente bloccato in un ciclo infinito. Si andrà in crash alla fine, perché sarà a corto di memoria. Ma non è questo il punto. 

Abbiamo bisogno di avere qualche altro modo per fermare cose oltre il nostro programma di crash, perché un programma che si blocca è probabilmente non bello o elegante. E così noi chiamiamo questo il caso base. Questa è una soluzione semplice ad un problema che ferma il processo ricorsivo di verificarsi. Ecco, questo è una parte del una funzione ricorsiva. 

La seconda parte è il caso ricorsivo. Ed è qui che la ricorsione avrà effettivamente luogo. Questo è dove il Funzione chiamerà se stesso. 

Non si chiamerà esattamente allo stesso modo è stato chiamato. Sarà una piccola variazione che rende il problema è cercando di risolvere un pochino più piccolo. Ma generalmente passa il dollaro di risolvere il grosso della soluzione ad una chiamata differente lungo la linea. 

Quale di questi sguardi come il caso base qui? Quale di questi sguardi, come la soluzione più semplice per un problema? Abbiamo un po 'di fattoriali, e si potrebbe continuare andando on-- 6, 7, 8, 9, 10, e così via. 

Ma uno di questi sembra una buon caso per essere il caso base. È una soluzione molto semplice. Noi non dobbiamo fare nulla di speciale. 

Il fattoriale di 1 si trova a 1. Non abbiamo a che fare ogni moltiplicazione affatto. Sembra come se stiamo andando per cercare di risolvere questo problema, e abbiamo bisogno di fermare il ricorsione da qualche parte, probabilmente vogliamo fermare quando si arriva a 1. Noi non vogliamo fermare prima. 

Quindi, se stiamo definendo la nostra funzione fattoriale, qui è uno scheletro per come potremmo farlo. Abbiamo bisogno di collegare quei due things-- il caso base e nel caso ricorsivo. Qual è il caso base? Se n è uguale a 1, questo è tornare 1-- davvero un problema semplice da risolvere. 

Il fattoriale di 1 a 1. Non è 1 volte nulla. E 'solo uno. E 'un fatto molto semplice. E così che può essere il nostro caso base. Se ci passati 1 in questo la funzione, ci limiteremo a ritorniamo 1. 

Qual è il ricorsiva caso probabilmente assomigliare? Per ogni altro numero oltre 1, qual è il motivo? Beh, se ci stiamo prendendo il fattoriale di n, E 'n volte il fattoriale di n meno 1. 

Se ci stiamo prendendo il fattoriale di 3, è 3 volte il fattoriale di 3 meno 1, o 2. E così, se non siamo guardando 1, altrimenti ritorno N volte il fattoriale di n meno 1. E 'piuttosto semplice. 

E per il gusto di avere un po ' più pulito e più elegante codice, sapere che se abbiamo loop a linea singola o riga singola rami condizionali, possiamo sbarazzarci di tutto quanto parentesi graffe intorno a loro. Così possiamo consolidare questo a questo. Questo ha esattamente la stessa funzionalità questo. 

Sto solo togliendo il riccio bretelle, perché c'è solo una linea all'interno di quei rami condizionali. Quindi questi si comportano in modo identico. Se n è uguale a 1, 1 ritorno. In caso contrario, tornare n volte il fattoriale di n meno 1. Quindi stiamo rendendo il problema più piccolo. Se n inizia come 5, stiamo andando a ritorno 5 volte il fattoriale di 4. E vedremo tra un minuto quando si parla sulla stack-- chiamata in un altro video dove si parla di chiamare stack-- impareremo sul perché esattamente questo processo funziona. 

Ma mentre fattoriale di 5 dice ritorno 5 volte fattoriale di 4, e 4 sta per dire, OK, bene, il ritorno 4 volte il fattoriale di 3. E come potete vedere, siamo sorta di avvicinamento 1. Ci stiamo avvicinando e più simile a quella del caso base. 

E una volta ci ha colpito il caso base, tutte le funzioni precedenti avere la risposta che cercavano. Fattoriale di 2 diceva ritorno 2 volte il fattoriale di 1. Beh, fattoriale di 1 restituisce 1. Quindi l'invito a fattoriale di 2 può restituire 2 volte 1, e dare che torna a fattoriale di 3, che è attesa per quel risultato. 

E allora può calcolare Il suo risultato, 3 volte 2 è 6, e dare di nuovo al fattoriale di 4. E ancora, abbiamo un video sul stack di chiamate dove ciò è illustrato un po ' più di quello che sto dicendo adesso. Ma è proprio questo. Questo da solo è la soluzione ai calcolare il fattoriale di un numero. 

È solo quattro righe di codice. Che è abbastanza freddo, giusto? È un po 'sexy. 

Quindi, in generale, ma non sempre, una funzione ricorsiva può sostituire un loop in un Funzione non ricorsiva. Così qui, fianco a fianco, è l'iterativo versione della funzione fattoriale. Entrambi questi calculate esattamente la stessa cosa. 

Entrambi calcolare il fattoriale di n. La versione a sinistra utilizza la ricorsione per farlo. La versione a destra utilizza l'iterazione di farlo. 

E notate, dobbiamo dichiarare una variabile un prodotto intero. E poi abbiamo ciclo. Finché n è maggiore di 0, si tenere moltiplicando tale prodotto n e decremento n fino a calcoliamo il prodotto. Quindi queste due funzioni, di nuovo, fare esattamente la stessa cosa. Ma non fanno in esattamente nello stesso modo. 

Ora, è possibile avere più di una base caso o più caso ricorsivo, a seconda su ciò che la funzione sta cercando di fare. Lei non è necessariamente solo limitati a un singolo caso di base o di un singolo ricorsivo caso. Così un esempio di qualcosa con casi multipli di base potrebbe essere il questo-- Sequenza numerica di Fibonacci. 

Si può ricordare da giorni di scuola elementare che la sequenza di Fibonacci è definita come questo-- il primo elemento è 0. Il secondo elemento è 1. Entrambi questi sono solo per definizione. 

Poi è definita ogni altro elemento come somma di n meno 1 e n meno 2. Così il terzo elemento Sarebbe 0 e 1 è 1. E poi il quarto elemento sarebbe il secondo elemento, 1, più il terzo elemento, 1. E questo sarebbe 2. E così via e così via. 

Quindi, in questo caso, abbiamo due casi di base. Se n è uguale a 1, 0 ritorno. Se n è uguale a 2, ritorno 1. In caso contrario, tornare Fibonacci di n meno 1 più di Fibonacci di n meno 2. 

Ecco, questo è i casi di base più. Che dire di più casi ricorsive? Beh, c'è qualcosa chiamato la congettura di Collatz. Non ho intenzione di dire, si sa di cosa si tratta, perché in realtà è il nostro ultimo problema per questo particolare video. Ed è il nostro esercizio a lavorare insieme. 

Quindi, ecco cosa il Collatz congetture è-- si applica ad ogni intero positivo. E specula che è sempre possibile ottenere indietro a 1 se si segue questa procedura. Se n è 1, stop. Siamo tornati a 1 se n è 1. 

In caso contrario, passare attraverso questo processo di nuovo il n diviso 2. E vedere se si può tornare a 1. In caso contrario, se n è dispari, passare attraverso questo processo nuovamente 3n + 1, o 3 n volte più 1. Quindi qui abbiamo un caso base. Se n è uguale a 1, stop. Non stiamo facendo più ricorsione. 

Ma abbiamo due casi ricorsivi. Se n è pari, facciamo una ricorsiva caso, chiamando n diviso per 2. Se n è dispari, facciamo un altro caso ricorsivo su 3 n volte più 1. 

E così l'obiettivo per questo video è di prendere un secondo, mettere in pausa il video, e cercare di scrivere questo funzione ricorsiva Collatz dove si passa in un valore n, e calcola quanti passi prende per arrivare a 1 se si inizia da n e si seguono questi passaggi sopra. Se n è 1, esso prende 0 passi. In caso contrario, sta andando a fare un passo in più per quanto molti passi che prende su entrambi n diviso 2 se n è pari, o 3n + 1 se n è dispari. 

Ora, io ho messo sullo schermo qui un paio di cose di prova per voi, un paio di test case per voi, per vedere ciò che questi vari numeri Collatz sono, ed anche un'illustrazione dei passi che devono essere attraversato in modo da poter sorta di vedere questo processo in azione. Quindi, se n è uguale a 1, Collatz di n è 0. Non dovete fare qualsiasi cosa per tornare a 1. Sei già lì. 

Se n è 2, ci vuole un passo per arrivare a 1. Si inizia con 2. Ebbene, 2 non è uguale a 1. Quindi sarà un passo oltre tuttavia molti passi it assume n diviso 2. 

2 diviso 2 è 1. Quindi ci vuole un passo più comunque molti passaggi impiegati per 1. 1 prende a zero punti. 

Per 3, come potete vedere, non c'è parecchi gradini coinvolti. Si passa da 3. E poi si va a 10, 5, 16, 8, 4, 2, 1. Ci vogliono sette passi per tornare a 1. E come potete vedere, c'è una paio di altri casi di test qui per testare il programma. Così ancora una volta, mettere in pausa il video. E io andrò ora a saltare indietro ciò che il processo reale è qui, ciò che questa congettura è. 

Vedi se riesci a capire come definire Collatz di n in modo che calcola quante i passaggi che ci vuole per arrivare a 1. Così si spera, si è messo in pausa il video e non sono solo in attesa di me per darvi la risposta qui. Ma se siete, beh, ecco la risposta comunque. 

Quindi, ecco una possibile definizione della funzione Collatz. La nostra base case-- se n è uguale a 1, torniamo 0. Non ci vuole alcuna passi per tornare a 1. 

In caso contrario, abbiamo due di casi, ricorsiva uno per i numeri pari e dispari per uno. Il modo in cui provo per numeri pari è quello di verificare se n mod 2 è uguale a 0. Questo è fondamentalmente, di nuovo, porre la domanda, se vi ricordate cosa è-- mod se io dividere n per 2 non c'è un resto? Questo sarebbe un numero pari. 

E così, se n mod 2 è uguale a 0 è il test è presente un numero pari. Se è così, voglio tornare 1, perché questo è sicuramente facendo un passo più Collatz di qualunque sia il numero è la metà di me. In caso contrario, voglio tornare 1 più di 3 volte Collatz n più 1. Quello era l'altro passo ricorsivo che ci potrebbe prendere per calcolare il Collatz-- il numero di passi ci vuole per ottenere indietro 1 dato un numero. Così si spera, in questo esempio ti ha dato un po ' di un assaggio di procedure ricorsive. Si spera, si pensa codice è un po 'di più bello se attuate in un modo ricorsivo elegante. Ma anche se non, la ricorsione è un strumento davvero potente comunque. E quindi è sicuramente qualcosa per ottenere la testa intorno, perché sarete in grado di creare programmi piuttosto fresco utilizzando la ricorsione che potrebbero altrimenti essere complesso di scrivere se si sta utilizzando loop e iterazione. Sono Doug Lloyd. Questo è CS50.