Rekursiv funktion

Rekursiv funktion, en matematisk funktion som definieras med hjälp av rekursion, d.v.s. 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, mer komplicerade fall kan sedan referera till basfallen.

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 följande steg:

{\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 "en:look-and-say sequence".

Tajföljden börjar såhär: 1, 11, 21, 1211, 111221, 312211, 13112221, ...

För att få fram nästa tal i talföljden så säger man vad som står i det föregående talet. Till exempel:

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

Om man startar med en siffra d från 0 till 9, om talet inte är 1 så kommer alltid varje talföljd se ut såhär.

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

Varje tal slutar alltså på d.

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

22, 22, 22, 22, ...

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

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

där $\scriptstyle \lambda =1.303577269\ldots$ $\lambda$ är en rot till en 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 i programmering

Inom funktionell programmering, såsom Lisp, använder man rekursiva funktioner istället för loopar. 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 man skriva uträkninge för n:te fibonaccitalet som

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

Se även