Una funzione ricorsiva è una funzione il cui valore in qualsiasi punto può essere calcolato dai valori della funzione in alcuni punti precedenti. Ad esempio, supponiamo che una funzione f(k) = f(k-2) + f(k-3) sia definita su un intero non negativo. Se abbiamo il valore della funzione in k = 0 e k = 2, possiamo anche trovare il suo valore in qualsiasi altro intero non negativo. In altre parole, possiamo dire che una funzione ricorsiva si riferisce a una funzione che utilizza i propri punti precedenti per determinare i termini successivi e quindi forma una sequenza di termini. In questo articolo impareremo le funzioni ricorsive insieme ad alcuni esempi.
Cos'è la ricorsione?
La ricorsione si riferisce a un processo in cui un processo ricorsivo si ripete. Ricorsivo è un tipo di funzione di una e più variabili, solitamente specificata da un certo processo che produce valori di quella funzione implementando continuamente una particolare relazione con valori noti della funzione.
Qui comprenderemo la ricorsione con l'aiuto di un esempio.
Supponiamo che tu voglia prendere una scala per raggiungere il primo piano dal piano terra. Quindi, per fare questo, devi fare uno per uno i passi. C'è solo un modo per andare al secondo gradino che è il primo gradino immerso. Supponiamo di voler passare al terzo passaggio; devi prima fare il secondo passo. Qui puoi vedere chiaramente il processo di ripetizione. Qui puoi vedere che con ogni passaggio successivo aggiungi il passaggio precedente come una sequenza ripetuta con la stessa differenza tra ogni passaggio. Questo è il vero concetto alla base della funzione ricorsiva.
Passo 2: Passo 1 + gradino più basso.
Passaggio 3: Passo 2 + Passo 1 + passo più basso.
Passaggio 4: Passaggio 3 + passaggio 2 + passaggio 1+ passaggio più basso e così via.
Un insieme di numeri naturali è l'esempio base delle funzioni ricorsive che partono dall'uno fino all'infinito, 1,2,3,4,5,6,7,8, 9,…….infinito. Pertanto, l'insieme dei numeri naturali mostra una funzione ricorsiva perché puoi vedere una differenza comune tra ciascun termine come 1; mostra ogni volta che il termine successivo si ripete dal termine precedente.
Cos'è una funzione definita ricorsivamente?
Le funzioni definite ricorsivamente comprendono due parti. La prima parte si occupa della definizione dell'argomento più piccolo e, d'altra parte, la seconda parte si occupa della definizione dell'ennesimo termine. L'argomento più piccolo è indicato con f (0) o f (1), mentre l'argomento n è indicato con f (n).
Segui l'esempio fornito.
Supponiamo che una sequenza sia 4,6,8,10
La formula esplicita per la sequenza precedente è f (n)= 2n + 2
La formula esplicita per la sequenza di cui sopra è data da
f(0) = 2
alfabeto in numeri
f(n) = f(n-1) + 2
Ora possiamo ottenere i termini della sequenza applicando la formula ricorsiva come segue f(2 ) f(1) + 2
f(2) = 6
f(0) = 2
f(1) = f(0) + 2
f(1) = 2 + 2 = 4
f(2) = f(1) + 2
f(2) = 4 + 2 = 6
f(3) = f(2) + 2
f(3) = 6 + 2 = 8
Con l'aiuto della formula della funzione ricorsiva sopra, possiamo determinare il termine successivo.
Cosa rende la funzione ricorsiva?
Per rendere ricorsiva qualsiasi funzione è necessario un proprio termine per calcolare il termine successivo nella sequenza. Ad esempio, se vuoi calcolare l'ennesimo termine di una determinata sequenza, devi prima conoscere il termine precedente e il termine prima del termine precedente. Pertanto, è necessario conoscere il termine precedente per scoprire se la sequenza è ricorsiva o non ricorsiva. Quindi possiamo concludere che se la funzione necessita del termine precedente per determinare il termine successivo nella sequenza, la funzione è considerata una funzione ricorsiva.
Java che ordina un arraylist
La formula della funzione ricorsiva
Se un1, UN2, UN3, UN4, UN5, UN6, ……..UNN,……sono molti insiemi o una sequenza, allora una formula ricorsiva dovrà calcolare tutti i termini che esistevano in precedenza per calcolare il valore di un
UNN= unn-1+UN1
La formula di cui sopra può anche essere definita come formula ricorsiva di sequenza aritmetica. Puoi vedere chiaramente nella sequenza menzionata sopra che si tratta di una sequenza aritmetica, che comprende il primo termine seguito dagli altri termini e una differenza comune tra ciascun termine. La differenza comune si riferisce a un numero che aggiungi o sottrai loro.
Una funzione ricorsiva può anche essere definita come sequenza geometrica, dove gli insiemi di numeri o una sequenza hanno un fattore comune o un rapporto comune tra loro. La formula per la sequenza geometrica è data come
UNN= unn-1 *R
Di solito, la funzione ricorsiva è definita in due parti. La prima è l'enunciato del primo termine insieme alla formula, l'altra è l'enunciato del primo termine insieme alla regola relativa ai termini successivi.
Come scrivere una formula ricorsiva per una sequenza aritmetica
Per scrivere la formula ricorsiva per la formula di sequenza aritmetica, seguire i passaggi indicati
Passo 1:
Nel primo passaggio, devi assicurarti se la sequenza data è aritmetica o meno (per questo, devi aggiungere o sottrarre due termini successivi). Se ottieni lo stesso output, la sequenza viene considerata come una sequenza aritmetica.
Passo 2:
Ora devi trovare la differenza comune per la sequenza data.
Passaggio 3:
Formulare la formula ricorsiva utilizzando il primo termine e quindi creare la formula utilizzando il termine precedente e la differenza comune; in questo modo otterrai il risultato indicato
UNN= unn-1+D
ora capiamo la formula data con l'aiuto di un esempio
supponiamo che 3,5,7,9,11 sia una determinata sequenza
Nell'esempio sopra, puoi facilmente scoprire che si tratta della sequenza aritmetica perché ogni termine nella sequenza aumenta di 2. Quindi, la differenza comune tra due termini è 2. Conosciamo la formula della sequenza ricorsiva
UNN= unn-1+D
Dato,
d = 2
UN1= 3
COSÌ,
UN2= un(2-1)+2 = a1+2 = 3+2 = 5
UN3= un(3-1)+2 = a2+2 = 5+2 = 7
se altrimenti in Java
UN4= un(4-1)+2 = a3+2 = 7+2 = 9
UN5= un(5-1)+ 2 = a + 2 = 9+2 = 11, e il processo continua.
Come scrivere una formula ricorsiva per la sequenza geometrica?
Per scrivere la formula ricorsiva per la formula di sequenza geometrica, seguire i passaggi indicati:
Passo 1
Nel primo passaggio, devi assicurarti se la sequenza data è geometrica o meno (per questo, devi moltiplicare o dividere ogni termine per un numero). Se si ottiene lo stesso risultato da un termine al termine successivo, la sequenza viene considerata come una sequenza geometrica.
Passo 2
Ora devi trovare il rapporto comune per la sequenza data.
Passaggio 3
Formulare la formula ricorsiva utilizzando il primo termine e quindi creare la formula utilizzando il termine precedente e il rapporto comune; otterrai così il risultato indicato
UNN= r*UNn-1
Ora capiamo la formula data con l'aiuto di un esempio
supponiamo che 2,8,32, 128,. sia una data sequenza
Nell'esempio sopra puoi facilmente scoprire che si tratta della sequenza geometrica perché il termine successivo nella sequenza si ottiene moltiplicando 4 per il termine precedente. Quindi, il rapporto comune tra due termini è 4. Conosciamo la formula della sequenza ricorsiva
UNN= r*UNn-1
UNN= 4
UNn-1= ?
Dato,
r = 4
UN1= 2
COSÌ,
UN2= un(2-1)*4 = a1+ * 4 = 2* 4 = 8
int per stringere in Java
UN3= un(3-1)*4 = a2*4 = 8 *4 = 32
UN4= un(4-1)*4 = a3* 4 = 32* 4 = 128 e il processo continua.
Esempio di funzione ricorsiva
Esempio 1:
Determinare la formula ricorsiva per la sequenza 4,8,16,32,64, 128,….?
Soluzione:
Data la sequenza 4,8,16,32,64,128,…..
La sequenza data è geometrica perché se moltiplichiamo il termine precedente otteniamo i termini successivi.
Per determinare la formula ricorsiva per la sequenza data, dobbiamo scriverla in forma tabellare
| Numeri dei termini | Termine di sequenza | Notazione di funzioni | Notazione in pedice |
|---|---|---|---|
| 1 | 4 | f(1) | UN1 |
| 2 | 8 | f(2) | UN2 |
| 3 | 16 | f(3) | UN3 |
| 4 | 32 | f(4) | UN4 |
| 5 | 64 | f(5) | UN5 |
| 6 | 128 | f(6) | UN6 |
| N | . | f(n) | UNN |
Quindi, la formula ricorsiva nella nozione di funzione è data da
f(1) = 4, f(n) . f(n-1)
Nella notazione in pedice, la formula ricorsiva è data da
UN1= 4, aN= 2.an-1