Matematik
Spørge til Recursion
Hej SP
Først og fremmest: en der kan forklare mig, hvad recursion er inden for matematik?
Jeg har et lille eksempel, som jeg ikke forstår: Håber der en der kan hjælpe mig med, at forstå det (eksemplet er herunder)
The sequence of Fibonacci numbers. Here one starts with the first two numbers in the sequence p1=p2=1. The rule associates to a pair of natural numbers p,q ∈ (naturlige-tal-tegn), a new natural number R(p,q) (naturlige-tal-tegn). In order to construct the Fib-sequence, we make the choice R(q,q) = p + q and define n (naturlige-tal-tegn): pn+2 = R(pn,pn+1) =pn + pn+1. The resulting sequence of natural numbers p1,p2..... are called the fib-numbers.
Jeg forestår ikke "regnestykket" markeret med rødt
Tak for hjælpen på forhånd
Svar #1
24. august 2018 af Brusebad (Slettet)
Rekursion er når et matematisk objekt defineres termer af objektet selv (og nogle basisværdier).
For eksempel er en følge (xn) rekursivt defineret hivs
x0 = reelt tal
xn = f(xn-1), n > 1, og hvor f er en funktion
her defineres xn ud fra det forrige element. Ændrer man værdien af x0 ændres de resterende værdier sig også.
Eskempler:
Du kender måske n! = n * (n - 1) * (n - 2) * ... * 1. Fakultet (!) defineres gerne rekursivt som
0! = 1
n! = n * (n - 1)! , n > 0
Du kender måske xn = x * ... * x hvor x optræder n gange på højresiden. Det xn defineres gerne rekursivt som
x0 = 1
xn = x * xn - 1, n > 0
Dit eksempel
I dit eksempel, som i øvrigt også er ret kendt (se e.g. https://en.wikipedia.org/wiki/Fibonacci_number), defineres en talfølge (pn) som
p1 = 1,
p2 = 1,
pn = pn - 1 + pn - 2, n > 2 (svarer til det som du har markeret med rød)
Det vil sige for n > 2 så for at finde pn så skal man tage summen af de to forrige elementer i talfølgen eller med andre ord
p3 = p1 + p2 = 1 + 1 = 2
p4 = p2 + p3 = 1 + 2 = 3
p5 = p3 + p4 = 2 + 3 = 5
Så (pn) = (p0, p1, p2, p3, p4, .... ) = (1, 1, 2, 3, 5, ....)
Bemærk at pn for n > 2 er defineret ud fra to foregående værdier hvorfor det var nødvendigt at specifere både p1 og p2
Svar #2
24. august 2018 af peter lind
se https://da.wikipedia.org/wiki/Rekursion
Det med rødt markerede er blot en definiion af fibonaccitallen. Summen af de to forgående tal er det næste fibonaccital med begyndelsesbetingelserne p1=p2 = 1. p3 = p1+p2 = 2, p4 =p1+p2 = 3, p5 = p3+p2 = 5 o.s.v.
Svar #3
24. august 2018 af Eksperimentalfysikeren
Det, der er skrevet med rødt indeholder en fejl. Det korrekte er:
pn+2 = R(pn,pn+1) =pn + pn+1
Hvis f.eks. n=3, så læses det p5 = p3+p4
Generelt benyttes rekursion i matematikken til definition af talfølger. Man starter med at angive værdien af første element og somme tider nogle efterfølgende elementer, samt en formel, hvormed man kan beregne element nummer n ud fra nogle af de foregående elementer. Noget af det simpleste er:
Sagt på en anden måde: n! er produktet af tallene fra 1 til og med n.
Skriv et svar til: Spørge til Recursion
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.