Una funció recursiva és una funció que el seu valor en qualsevol punt es pot calcular a partir dels valors de la funció en alguns punts anteriors. Per exemple, suposem una funció f(k) = f(k-2) + f(k-3) que es defineix sobre un nombre enter no negatiu. Si tenim el valor de la funció a k = 0 i k = 2, també podem trobar-ne el valor en qualsevol altre nombre enter no negatiu. En altres paraules, podem dir que una funció recursiva es refereix a una funció que utilitza els seus propis punts anteriors per determinar termes posteriors i, per tant, forma una seqüència de termes. En aquest article, aprendrem sobre les funcions recursives juntament amb alguns exemples.
Què és la recursivitat?
La recursivitat es refereix a un procés en què un procés recursiu es repeteix. La recursiva és un tipus de funció d'una o més variables, normalment especificada per un procés determinat que produeix valors d'aquesta funció mitjançant la implementació contínua d'una relació particular amb els valors coneguts de la funció.
Aquí, entendrem la recursivitat amb l'ajuda d'un exemple.
Suposem que vas a agafar una escala per arribar al primer pis des de la planta baixa. Per tant, per fer-ho, heu de fer passos un a un. Només hi ha una manera d'anar al segon pas que és el primer graó. Suposem que voleu passar al tercer pas; primer has de fer el segon pas. Aquí, podeu veure clarament el procés de repetició. Aquí, podeu veure que amb cada pas següent, esteu afegint el pas anterior com una seqüència repetida amb la mateixa diferència entre cada pas. Aquest és el concepte real darrere de la funció recursiva.
Pas 2: Pas 1 + pas més baix.
Pas 3: Pas 2 + Pas 1 + pas més baix.
Pas 4: Pas 3 + pas 2 + pas 1 + pas més baix, i així successivament.
Un conjunt de nombres naturals és l'exemple bàsic de les funcions recursives que comencen des d'un va fins a l'infinit, 1,2,3,4,5,6,7,8, 9,…….infinitiu. Per tant, el conjunt de nombres naturals mostra una funció recursiva perquè podeu veure una diferència comuna entre cada terme com a 1; es mostra cada cop que el terme següent es repeteix pel trimestre anterior.
Què és una funció definida recursivament?
Les funcions definides recursivament consten de dues parts. La primera part tracta de la definició de l'argument més petit, i d'altra banda, la segona part tracta de la definició del terme enèsimo. L'argument més petit es denota per f (0) o f (1), mentre que l'enèsim argument es denota per f (n).
combinar ordena java
Seguiu l'exemple donat.
Suposem que una seqüència és 4,6,8,10
La fórmula explícita per a la seqüència anterior és f (n) = 2n + 2
La fórmula explícita per a la seqüència anterior ve donada per
f (0) = 2
f(n) = f (n-1) + 2
Ara, podem obtenir els termes de la seqüència aplicant la fórmula recursiva de la següent manera 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
Amb l'ajuda de la fórmula de funció recursiva anterior, podem determinar el terme següent.
Què fa que la funció sigui recursiva?
Fer que qualsevol funció sigui recursiva necessita el seu propi terme per calcular el següent terme de la seqüència. Per exemple, si voleu calcular l'enè terme de la seqüència donada, primer heu de conèixer el terme anterior i el terme anterior al terme anterior. Per tant, cal conèixer el terme anterior per saber si la seqüència és recursiva o no. Així, podem concloure que si la funció necessita el terme anterior per determinar el següent terme de la seqüència, la funció es considera una funció recursiva.
La fórmula de la funció recursiva
Si a1, a2, a3, a4, a5, a6, ……..an,…… són molts conjunts o una seqüència, aleshores una fórmula recursiva haurà de calcular tots els termes que existien anteriorment per calcular el valor d'un
an= an-1 +a1
La fórmula anterior també es pot definir com a fórmula recursiva de seqüència aritmètica. Podeu veure clarament a la seqüència esmentada anteriorment que és una seqüència aritmètica, que comprèn el primer terme seguit dels altres termes i una diferència comuna entre cada terme. La diferència comuna es refereix a un nombre que els sumeu o els resteu.
Una funció recursiva també es pot definir com la seqüència geomètrica, on els conjunts de nombres o una seqüència tenen un factor comú o una raó comú entre ells. La fórmula per a la successió geomètrica es dóna com
an= an-1 *r
Normalment, la funció recursiva es defineix en dues parts. El primer és l'enunciat del primer terme juntament amb la fórmula, i un altre és l'enunciat del primer terme juntament amb la regla relacionada amb els termes successius.
Com escriure una fórmula recursiva per a una seqüència aritmètica
Per escriure la fórmula recursiva per a la fórmula de la seqüència aritmètica, seguiu els passos indicats
Pas 1:
En el primer pas, cal assegurar-se si la seqüència donada és aritmètica o no (per a això, cal sumar o restar dos termes successius). Si obteniu la mateixa sortida, la seqüència es pren com una seqüència aritmètica.
Pas 2:
Ara, heu de trobar la diferència comuna per a la seqüència donada.
Pas 3:
Formula la fórmula recursiva utilitzant el primer terme i després crea la fórmula utilitzant el terme anterior i la diferència comuna; així obtindreu el resultat donat
an= an-1 +d
ara, entenem la fórmula donada amb l'ajuda d'un exemple
Suposem que 3,5,7,9,11 és una seqüència donada
A l'exemple anterior, podeu trobar fàcilment que és la seqüència aritmètica perquè cada terme de la seqüència augmenta en 2. Per tant, la diferència comuna entre dos termes és 2. Coneixem la fórmula de la seqüència recursiva.
an= an-1 +d
Donat,
d = 2
a1= 3
tan,
a2= a(2-1)+ 2 = a1+ 2 = 3+2 = 5
a3= a(3-1)+ 2 = a2+ 2 = 5+2 = 7
a4= a(4-1)+ 2 = a3+ 2 = 7+2 = 9
a5= a(5-1)+ 2 = a + 2 = 9+2 = 11, i el procés continua.
Com escriure una fórmula recursiva per a una seqüència geomètrica?
Per escriure la fórmula recursiva per a la fórmula de la seqüència geomètrica, seguiu els passos indicats:
Pas 1
En el primer pas, heu d'assegurar-vos si la seqüència donada és geomètrica o no (per a això, heu de multiplicar o dividir cada terme per un nombre). Si obteniu la mateixa sortida d'un terme al següent, la seqüència es pren com una seqüència geomètrica.
Pas 2
Ara, heu de trobar la proporció comuna per a la seqüència donada.
Pas 3
Formule la fórmula recursiva utilitzant el primer terme i després creeu la fórmula utilitzant el terme anterior i la relació comuna; així obtindreu el resultat donat
an= r*an-1
Ara, entenem la fórmula donada amb l'ajuda d'un exemple
Suposem que 2,8,32, 128,.és una seqüència donada
A l'exemple anterior, podeu trobar fàcilment que és la seqüència geomètrica perquè el terme successiu de la seqüència s'obté multiplicant 4 al terme anterior. Per tant, la proporció comuna entre dos termes és 4. Coneixem la fórmula de la seqüència recursiva
an= r*an-1
an= 4
an-1= ?
Donat,
r = 4
a1= 2
tan,
a2= a(2-1)* 4 = a1+ * 4 = 2* 4 = 8
a3= a(3-1)* 4 = a2*4 = 8 * 4 = 32
a4= a(4-1)* 4 = a3* 4 = 32* 4 = 128, i el procés continua.
Exemple de funció recursiva
Exemple 1:
Determineu la fórmula recursiva per a la seqüència 4,8,16,32,64, 128,....?
Solució:
Donada la seqüència 4,8,16,32,64,128,...
La seqüència donada és geomètrica perquè si multipliquem el terme anterior, obtenim els termes successius.
Per determinar la fórmula recursiva per a la seqüència donada, hem d'escriure-la en forma tabular
| Números de termes | Terme de seqüència | Notació de funcions | Notació de subíndex |
|---|---|---|---|
| 1 | 4 | f(1) | a1 |
| 2 | 8 | f(2) | a2 |
| 3 | 16 | f(3) | a3 |
| 4 | 32 | f(4) | a4 |
| 5 | 64 | f(5) | a5 |
| 6 | 128 | f(6) | a6 |
| n | . | f(n) | an |
Per tant, la fórmula recursiva en la noció de funció ve donada per
f(1) = 4, f(n) . f(n-1)
ordenar una llista de matrius java
En notació de subíndex, la fórmula recursiva ve donada per
a1= 4, an= 2. an-1