>> ZAMYLA: Al fine di comprendere ricorsione, è necessario
prima capire la ricorsione.
Avendo ricorsione in programma mezzi di progettazione che si deve auto-referenziale
definizioni.
Strutture dati ricorsive, per esempio, sono strutture di dati che
si comprenderà in loro definizioni.
Ma oggi, stiamo andando a fuoco sulle funzioni ricorsive.
>> Ricordiamo che funzioni accettano ingressi, argomenti e restituire un valore come loro
uscita rappresentata dalla questo diagramma qui.
Penseremo della scatola come il corpo di la funzione contenente il gruppo di
istruzioni che interpretano il input e fornire un'uscita.
Dando un'occhiata più da vicino all'interno del corpo di la funzione potrebbe rivelare chiamate
altre funzioni.
Prendete questa semplice funzione, foo, che prende una singola stringa come input e
Stampe quante lettere che la stringa ha.
La funzione strlen, per la lunghezza della stringa, è chiamato, la cui uscita è
richiesto per la chiamata a printf.
>> Ora, ciò che rende una funzione ricorsiva speciale è che si chiama.
Possiamo rappresentare questa ricorsiva chiamare con questo freccia arancione
di tornare a se stesso.
Ma l'esecuzione di sé ancora una volta solo sarà effettuare un'altra chiamata ricorsiva, e
altro e un altro.
Ma le funzioni ricorsive non può essere infinito.
Devono finire in qualche modo, o il vostro programma verrà eseguito sempre.
>> Quindi abbiamo bisogno di trovare un modo per rompere fuori delle chiamate ricorsive.
Noi chiamiamo questo il caso base.
Quando la condizione caso base è soddisfatta, la funzione restituisce senza fare
un'altra chiamata ricorsiva.
Prendete questa funzione, hi, una funzione void che prende un int n come input.
Il caso base viene prima.
Se n è minore di zero, bye stampa e ritorno Per tutti gli altri casi, l'
funzione di stampa hi ed eseguire la chiamata ricorsiva.
Un'altra chiamata alla funzione hi con un valore di ingresso decrementato.
>> Ora, anche se stampiamo ciao, l' funzione non terminerà fino a quando
ritorno il tipo restituito, in questo caso vuoto.
Quindi per ogni n diverso il caso base, questa funzione hi tornerà hi
di n meno 1.
Poiché questa funzione è nulla, però, siamo non esplicitamente digitare ritorno qui.
Ti basta eseguire la funzione.
Così chiamata hi (3) stampa ciao e eseguire hi (2) che esegue hi (1) una
che esegue hi (0), in cui la condizione di scenario di base è soddisfatta.
Così hi (0) stampa bye e ritorna.
>> OK.
Quindi, ora che abbiamo capito le basi del funzioni ricorsive, che hanno bisogno
almeno un caso base e un chiamata ricorsiva, passiamo ad un
esempio più significativo.
Uno che non si limita a tornare annullare qualunque cosa.
>> Diamo uno sguardo al fattoriale funzionamento più comunemente utilizzato in
calcolo delle probabilità.
Fattoriale di n è il prodotto di ogni numero intero positivo inferiore
e pari a n.
Così cinque fattoriale è 5 volte 4 volte 3 volte 2 volte 1 per dare 120.
Quattro fattoriale è 4 volte 3 volte 2 volte 1 per dare 24.
E vale la stessa regola qualsiasi numero intero positivo.
>> Così come potremmo scrivere un ricorsiva funzione che calcola il fattoriale
di un numero?
Bene, abbiamo bisogno di identificare sia l' caso base e la chiamata ricorsiva.
La chiamata ricorsiva sarà lo stesso per tutti i casi, eccetto per la base
caso, il che significa che dovremo trovare un modello che ci darà il nostro
risultato desiderato.
>> Per questo esempio, vedere come 5 fattoriale coinvolge moltiplicando 4 da 3 per 2 per 1
E quella stessa moltiplicazione si trova qui, l'
definizione di 4 fattoriale.
Così vediamo che 5 fattoriale è a soli 5 volte 4 fattoriale.
Ora si applica questo modello 4 fattoriale così?
Sì.
Vediamo che 4 fattoriale contiene il moltiplicazione 3 volte 2 volte 1, la
stessa definizione, 3 fattoriale.
Quindi 4 fattoriale è pari a 4 volte 3 fattoriale, e così via e così via il nostro
modello bastoni fino al 1 fattoriale, che per definizione è uguale a 1.
>> Non c'è nessun altro positivo interi sinistra.
Così abbiamo il modello per la nostra chiamata ricorsiva.
n fattoriale è pari a n volte il fattoriale di n meno 1.
E il nostro caso base?
Questo sarà solo la nostra definizione di 1 fattoriale.
>> Così ora possiamo passare alla scrittura codice per la funzione.
Per il caso base, avremo l' condizione n è uguale uguale a 1, dove
torneremo 1.
Poi di passare la chiamata ricorsiva, torneremo n volte l'
fattoriale di n meno 1.
>> Ora cerchiamo di testare questa nostra.
Proviamo fattoriale 4.
Per la nostra funzione è uguale per 4 volte fattoriale (3).
Fattoriale (3) è pari a 3 volte fattoriali (2).
Fattoriale (2) è pari a 2 volte fattoriale (1), che restituisce 1.
Fattoriale (2) restituisce ora 2 volte 1, 2.
Fattoriale (3) ora può tornare 3 volte 2, 6.
E, infine, fattoriale (4) restituisce 4 volte 6, 24.
>> Se stai incontrando difficoltà con la chiamata ricorsiva, fingere che
la funzione funziona già.
Quello che voglio dire è che si dovrebbe fiducia le chiamate ricorsive di ritorno
i giusti valori.
Per esempio, se so che fattoriale (5) è pari a 5 volte
fattoriale (4), ho intenzione di fiducia che fattoriale (4), mi darà 24.
Pensate a come una variabile, se si sarà, come se già definito
fattoriale (4).
Quindi per qualsiasi fattoriale (n), è il prodotto di n e
il fattoriale precedente.
E questo precedente fattoriale viene ottenuto chiamando
fattoriale di n meno 1.
>> Ora, vedere se è possibile implementare un ricorsiva funzionare da soli.
Caricare il terminale, o run.cs50.net, e scrivere una somma funzione
che prende un intero n e restituisce il somma di tutti positivi consecutivi
interi da n a 1.
Ho scritto le somme di una certa I valori per aiutarti nostra.
In primo luogo, capire il stato scenario di base.
Poi, guarda sum (5).
Si può esprimere in termini di un'altra somma?
Ora, che dire sum (4)?
Come si può esprimere sum (4) in termini di un'altra somma?
>> Una volta che avete sum (5) e sum (4) espressa in termini di altre somme, vedere
se è possibile identificare un modello per la somma (n).
In caso contrario, provare alcuni altri numeri ed esprimere le proprie somme in
termini di un altro numero.
Identificando modelli di discreta numeri, siete sulla buona strada per
identificare il modello per ogni n.
>> La ricorsione è uno strumento davvero potente, così naturalmente non è limitato a
funzioni matematiche.
La ricorsione può essere utilizzato in modo molto efficace quando si tratta di alberi, per esempio.
Scopri la breve sugli alberi per un più approfondito esame, ma per ora
ricordare che gli alberi binari di ricerca, in particolare, sono costituiti da nodi, ciascuno
con un valore e due puntatori nodo.
Di solito, questo è rappresentato dal nodo padre con una linea di puntamento
al nodo figlio sinistro e uno al nodo figlio destro.
La struttura di una ricerca binaria albero si presta bene
ad una ricerca ricorsiva.
La chiamata ricorsiva passa sia nella sinistra o destra del nodo, ma più
di che nel breve albero.
>> Dire che si desidera eseguire un'operazione su ogni singolo nodo in un albero binario.
Come si potrebbe fare per questo?
Beh, si potrebbe scrivere un ricorsiva funzione che esegue l'operazione
sul nodo padre e fa un ricorsiva chiamare per la stessa funzione,
passando sinistra e nodi figlio destro.
Ad esempio, questa funzione foo, che modifica il valore di un dato nodo e
tutti i suoi figli a 1.
Il caso base di un valore NULL cause nodo la funzione di tornare, indicando
che non ci sono nodi lasciato in quella sub-tree.
>> Camminiamo attraverso di essa.
Il primo genitore è 13.
Cambiamo il valore di 1, e quindi chiamare la nostra funzione sulla sinistra e
come il diritto.
La funzione foo, è chiamato a sinistra sub-tree prima, in modo che il nodo di sinistra
saranno riassegnate a 1 e foo sarà essere chiamati figli di quel nodo,
prima sinistra e poi destra, e così via e così via.
E dire loro che i rami non hanno qualsiasi più bambini così lo stesso processo
proseguirà per i bambini giuste fino a quando i nodi dell'intero albero sono
riassegnato al 1.
>> Come si può vedere, non si sono limitati ad una sola chiamata ricorsiva.
Proprio come molti come otterrà il lavoro fatto.
E se aveste un albero dove ogni nodo aveva tre figli,
Sinistra, centro e destra?
Come si potrebbe modificare foo?
Beh, semplice.
Basta aggiungere un'altra chiamata ricorsiva e passare il puntatore nodo centrale.
>> La ricorsione è molto potente e non menziona elegante, ma può essere un
concetto difficile in un primo momento, in modo da essere paziente e prendere il vostro tempo.
Inizia con il caso base.
Di solito il più facile da identificare, e poi si può lavorare
indietro da lì.
Sai che è necessario per raggiungere il tuo scenario di base, in modo che la forza
vi darò alcuni suggerimenti.
Cercate di esprimere un caso specifico termini di altri casi, o in sottoinsiemi.
>> Grazie per guardare questo breve.
Per lo meno, ora è possibile capire gli scherzi come questo.
Il mio nome è Zamyla, e questo è CS50.
>> Prendete questa funzione, ciao, un funzione di vuoto che prende
un int, n, come input.
Il caso base viene prima.
Se n è minore di 0, stampa "Bye" e ritorno.