En rekursiv funktion är en funktion vars värde vid vilken punkt som helst kan beräknas från funktionens värden vid några tidigare punkter. Anta till exempel en funktion f(k) = f(k-2) + f(k-3) som definieras över ett icke-negativt heltal. Om vi har värdet på funktionen vid k = 0 och k = 2, kan vi också hitta dess värde vid vilket annat icke-negativt heltal som helst. Med andra ord kan vi säga att en rekursiv funktion syftar på en funktion som använder sina egna tidigare punkter för att bestämma efterföljande termer och därmed bildar en termsekvens. I den här artikeln kommer vi att lära oss om rekursiva funktioner tillsammans med vissa exempel.
Vad är rekursion?
Rekursion avser en process där en rekursiv process upprepar sig. Rekursiv är en sorts funktion av en och flera variabler, vanligtvis specificerad av en viss process som producerar värden för den funktionen genom att kontinuerligt implementera en viss relation till kända värden för funktionen.
Här kommer vi att förstå rekursionen med hjälp av ett exempel.
Anta att du ska ta en trappa för att nå första våningen från bottenvåningen. Så för att göra detta måste du ta steg ett och ett. Det finns bara ett sätt att gå till det andra steget, det är till det brantade första steget. Anta att du vill gå till det tredje steget; du måste ta det andra steget först. Här kan du tydligt se upprepningsprocessen. Här kan du se att med varje nästa steg lägger du till föregående steg som en upprepad sekvens med samma skillnad mellan varje steg. Detta är själva konceptet bakom den rekursiva funktionen.
Steg 2: Steg 1 + lägsta steget.
Steg 3: Steg 2 + Steg 1 + lägsta steget.
Steg 4: Steg 3 + steg 2 + steg 1+ lägsta steg, och så vidare.
En uppsättning naturliga tal är det grundläggande exemplet på de rekursiva funktionerna som börjar från ett går till oändligheten, 1,2,3,4,5,6,7,8, 9,…….infinitiv. Därför visar uppsättningen naturliga tal en rekursiv funktion eftersom du kan se en gemensam skillnad mellan varje term som 1; den visar varje gång nästa term upprepas av föregående term.
Vad är en rekursivt definierad funktion?
De rekursivt definierade funktionerna består av två delar. Den första delen behandlar den minsta argumentdefinitionen, och å andra sidan behandlar den andra delen den n:te termdefinitionen. Det minsta argumentet betecknas med f (0) eller f (1), medan det n:te argumentet betecknas med f (n).
Följ det givna exemplet.
Antag att en sekvens är 4,6,8,10
Den explicita formeln för ovanstående sekvens är f (n)= 2n + 2
Den explicita formeln för ovanstående sekvens ges av
f (0) = 2
f(n) = f (n-1) + 2
Nu kan vi få sekvenstermerna genom att tillämpa den rekursiva formeln enligt 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
Med hjälp av ovanstående rekursiva funktionsformel kan vi bestämma nästa term.
Vad gör funktionen rekursiv?
Att göra en funktion rekursiv behöver en egen term för att beräkna nästa term i sekvensen. Till exempel, om du vill beräkna den n:e termen i den givna sekvensen, måste du först känna till den föregående termen och termen före den föregående termen. Därför måste du känna till föregående term för att ta reda på om sekvensen är rekursiv eller inte rekursiv. Så vi kan dra slutsatsen att om funktionen behöver föregående term för att bestämma nästa term i sekvensen, anses funktionen vara en rekursiv funktion.
Formeln för den rekursiva funktionen
Om en1, a2, a3, a4, a5, a6, ……..an,……är många uppsättningar eller en sekvens, då måste en rekursiv formel beräkna alla termer som fanns tidigare för att beräkna värdet av en
an= an-1+a1
Ovanstående formel kan också definieras som aritmetisk sekvensrekursiv formel. Du kan tydligt se i sekvensen som nämns ovan att det är en aritmetisk sekvens, som består av den första termen följt av de andra termerna och en gemensam skillnad mellan varje term. Den vanliga skillnaden hänvisar till ett tal som du adderar eller subtraherar till dem.
En rekursiv funktion kan också definieras som den geometriska sekvensen, där talmängderna eller en sekvens har en gemensam faktor eller gemensamt förhållande mellan sig. Formeln för den geometriska sekvensen ges som
an= an-1 *r
Vanligtvis definieras den rekursiva funktionen i två delar. Den första är satsen för den första termen tillsammans med formeln, och en annan är satsen för den första termen tillsammans med regeln relaterad till de på varandra följande termerna.
Hur man skriver en rekursiv formel för aritmetisk sekvens
För att skriva den rekursiva formeln för aritmetisk sekvensformel, följ de givna stegen
Steg 1:
I det första steget måste du säkerställa om den givna sekvensen är aritmetisk eller inte (för detta måste du lägga till eller subtrahera två på varandra följande termer). Om du får samma utdata tas sekvensen som en aritmetisk sekvens.
Steg 2:
Nu måste du hitta den gemensamma skillnaden för den givna sekvensen.
Steg 3:
Formulera den rekursiva formeln med den första termen och skapa sedan formeln genom att använda föregående term och gemensam skillnad; så får du det givna resultatet
an= an-1+d
nu förstår vi den givna formeln med hjälp av ett exempel
anta att 3,5,7,9,11 är en given sekvens
I exemplet ovan kan du lätt hitta att det är den aritmetiska sekvensen eftersom varje term i sekvensen ökar med 2. Så den gemensamma skillnaden mellan två termer är 2. Vi känner till formeln för rekursiv sekvens
an= an-1+d
Given,
d = 2
a1= 3
så,
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, och processen fortsätter.
Hur man skriver en rekursiv formel för geometrisk sekvens?
För att skriva den rekursiva formeln för geometrisk sekvensformel, följ de givna stegen:
Steg 1
I det första steget måste du säkerställa om den givna sekvensen är geometrisk eller inte (för detta måste du multiplicera eller dividera varje term med ett tal). Om du får samma utdata från en term till nästa term tas sekvensen som en geometrisk sekvens.
Steg 2
Nu måste du hitta det gemensamma förhållandet för den givna sekvensen.
Steg 3
Formulera den rekursiva formeln med den första termen och skapa sedan formeln genom att använda föregående term och gemensamt förhållande; så får du det givna resultatet
an= r*an-1
Nu förstår vi den givna formeln med hjälp av ett exempel
java arraylist sorterad
anta att 2,8,32, 128,.är en given sekvens
I exemplet ovan kan du enkelt hitta att det är den geometriska sekvensen eftersom den successiva termen i sekvensen erhålls genom att multiplicera 4 med föregående term. Så det gemensamma förhållandet mellan två termer är 4. Vi känner till formeln för rekursiv sekvens
an= r*an-1
an= 4
an-1= ?
Given,
r = 4
a1= 2
så,
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, och processen fortsätter.
Exempel på rekursiv funktion
Exempel 1:
Bestäm den rekursiva formeln för sekvensen 4,8,16,32,64, 128,...?
Lösning:
Given sekvens 4,8,16,32,64,128,…..
Den givna sekvensen är geometrisk eftersom om vi multiplicerar föregående term får vi de successiva termerna.
För att bestämma den rekursiva formeln för den givna sekvensen måste vi skriva den i tabellform
| Termnummer | Sekvens Term | Funktionsnotering | Subscription Notation |
|---|---|---|---|
| 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 |
Därför ges den rekursiva formeln i funktionsbegreppet av
f(1) = 4, f(n). f(n- 1)
I subscript notation ges den rekursiva formeln av
a1= 4, an= 2. an-1