Definierade uttryck
En rekursiv funktion är en matematisk funktion definierade uttryck definieras med hjälp av rekursiondet vill säga med hjälp av referenser till sig själv. För att en definition av en rekursiv funktion skall vara korrekt måste den innehålla minst ett basfall som inte refererar till funktionen själv och som övriga anrop, definierade uttryck sista ledet av sin anropskedja, kan referera till.
Ett exempel är definitionen av fakultet som kan skrivas rekursivt. Fakulteten av talet nskrivet n! Ett annat känt matematiskt exempel är definitionen av fibonaccitalen. Man kan använda rekursion för att härleda det minsta antal flyttningar som krävs för att lösa problemet Tornen i Hanoi. Denna rekursiva differensekvation har ingen uppenbar lösning, men genom att räkna ut ett fåtal termer i början kan man göra en gissning som därefter kan bevisas medelst induktion över n.
Denna gissning är lämpligen 2 n -1, som är konsistent med rekursionen och startvillkoret.
Kulturella uttryck: egenskaper och exempel
Rekursiva funktioner är ett centralt begrepp inom den diskreta matematiken och datavetenskapen. Det har till exempel visats att rekursiva funktioner är precis de funktioner som kan beräknas av turingmaskiner. Ett annat exempel på rekursion är Collatz problem. Man börjar med ett positivt heltal n. Sedan fortsätter man med att multiplicera talet med 3 och addera med 1 om n är ett udda tal.
Om n är ett jämnt tal definierade uttryck delar man talet med 2. Sedan upprepas detta tills resultatet blir 1. Till exempel om man börjar med starttalet 5 så ser talföljden ut såhär:. Problemet är då att avgöra om man kan nå talet 1 oavsett vilket tal man startar med. Än så länge har ingen kunnat bevisa att alla talföljder slutar med 1 eller hittat någon talföljd som inte slutar på ett.
Så hittills är problemet olöst.
Vad är ett rationellt uttryck?
För att få nästa tal i talföljden så läses först vad som står i det föregående talet. Till exempel:. Md en startsiffra d från 0 till "definierade uttryck" och om talet inte är 1 så kommer alltid varje talföljd se ut enligt. Alla talföljder kommer till slut att växa obegränsat oavsett startvärdet, utom för 22, då nästa tal definierade uttryck talföljden alltid blir detsamma som föregående:.
Conways konstant gäller för alla starttal utom Rekursion används inom matematisk bevisföring i induktionsbevis. Tekniken innebär grovt att man rekursivt utnyttjar tidigare del resultat för att bygga vidare på beviset. Många komplicerade och oförutsägbara fenomen uppkommer genom rekursion. Fraktaler är ett relaterat område där både kaos och rekursion går hand i hand, då många fraktaler, så som juliamängder och de från itererade funktionssystem är definierade rekursivt.
Inom funktionell programmeringsåsom Lispanvänder man rekursiva funktioner istället för slingor.
Human test
Eftersom varje delsteg måste sparas vid beräkningen av en rekursiv funktion sker det ibland en optimering vid kompilering eller interpretering av dessa språk som ersätter rekursiva beräkningar med loopar. I Haskell kan beräkning av det n :te fibonaccitalet definieras som. Innehåll flytta till sidofältet dölj. Artikel Diskussion. Läs Redigera Redigera wikitext Visa historik.
Verktyg Verktyg. På andra projekt. Exempel [ redigera redigera wikitext ]. Matematisk "definierade uttryck" [ redigera redigera wikitext ].
Tornen i Hanoi [ redigera redigera wikitext ]. Collatz problem [ redigera redigera wikitext ]. Look-and-say sequence [ redigera redigera wikitext ]. Inom matematik [ redigera redigera wikitext ]. Användning inom programmering [ redigera redigera wikitext ]. Se även [ redigera redigera wikitext ].