Rekursiv funktion

En rekursiv funktion är en matematisk funktion som definieras med hjälp av rekursion, det 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, i sista ledet av sin anropskedja, kan referera till.

Exempel

Matematisk fakultet

Ett exempel är definitionen av fakultet som kan skrivas rekursivt. Fakulteten av talet n, skrivet n!, är produkten av talen 1, 2, 3 ... n.

$n!=\left\{{\begin{matrix}1\quad \qquad &&{\mbox{om }}n=0\qquad \qquad \quad \\n(n-1)!&&{\mbox{om }}n\geq 1\qquad \qquad \quad \end{matrix}}\right.$ Denna definition leder för fallet 3! till steget

{\begin{aligned}3!&=3\cdot (3-1)!&=&3\cdot 2!\\&=3\cdot 2\cdot (2-1)!&=&3\cdot 2\cdot 1!\\&=3\cdot 2\cdot 1\cdot (1-1)!&=&3\cdot 2\cdot 1\cdot 0!\\&=3\cdot 2\cdot 1\cdot 1&=&6\\\end{aligned}}

Ett annat känt matematiskt exempel är definitionen av fibonaccitalen.

Tornen i Hanoi

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. Om man låter a_n beteckna det minsta antalet flyttningar som krävs för att flytta ett hanoitorn med n skivor så erhålls rekursionen a_n=2a_n-1+1; a₁=1. 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ⁿ-1, som är konsistent med rekursionen och startvillkoret.

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.

Collatz problem

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 så 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:

a_{0}=5,\ a_{1}=16,\ a_{2}=8,\ a_{3}=4,\ a_{4}=2,\ a_{5}=1

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.

Look-and-say sequence

Ännu ett exempel på rekursion är "look-and-say sequence".

Tajföljden börjar: 1, 11, 21, 1211, 111221, 312211, 13112221, ...

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:

1 läses som "en 1a" eller 11.
11 läses som "två 1or" eller 21.
21 läses som "en 2a, en 1a" eller 1211.
1211 läses som "en 1a, en 2a, två 1or" eller 111221.

Md en startsiffra d från 0 till 9 och om talet inte är 1 så kommer alltid varje talföljd se ut enligt

d, 1d, 111d, 311d, 13211d, 111312211d, 31131122211d, …

Varje tal slutar alltså med d.

Alla talföljder kommer till slut att växa obegränsat oavsett startvärdet, utom för 22, då nästa tal i talföljden alltid blir detsamma som föregående:

22, 22, 22, 22, ...

Talen kommer till slut att växa med ungefär 30% per gång. Om $L_{n}$ är antalet siffror i det $n$ -te talet i talföljden, så ges Conways konstant av

\lim _{n\to \infty }{\frac {L_{n+1}}{L_{n}}}=\lambda

där $\lambda =1.303577269\ldots$

$\lambda$ är en rot till ett polynom av grad 71. Conways konstant gäller för alla starttal utom 22.

Inom matematik

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. Ett klassisk exempel är rekursionen x_n+1=r(1-x_n), som får ett kaotiskt beteende för r>3.57. 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.

Användning inom programmering

Inom funktionell programmering, såsom Lisp, använder man rekursiva funktioner istället för slingor. 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

fib :: Integral t => t -> t
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Se även