Rekursive funktioner

[05.12.2020] [Nørderier/Teori]

Rekursive funktioner
Linearitet

Rekursive funktioner er funktioner defineret på en bestem måde nemlig rekursivt. Ideen i en rekursiv definition er at funktionen returnerer sig selv. Måske er det mest oplagte eksempel fakultetsfunktionen. Fakultet skrives som ! og defineres ud fra følgende:

$0! = 1$
$n! = n \cdot (n - 1)!$

Fakultet er altså en funktion der er defineret som produktet af alle naturlige tal, $n_0$: $n_0 \gt 0$ og $n_0 \leq n$. Feks kan vi vælge $n = 5$, og vi får $$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$$

Fakultet er en funktion, og ovenfor er den defineret rekursivt. Denne definition kan overføres til programmering. Vi ser at $n! = n(n - 1)!$, hvis vi istedet for ! skriver $f(n)$ som en funktion der æder et n som argument, kan vi skrive følgende:

function fakultet (n){ if(n === 0){ return 1; } return n * fakultet(n - 1); }

Og vi har en rekursiv funktion. Det kan måske være en god idé at analysere den lidt, for hvad sker der? Jo, for tilfældet $n = 5$ sker der følgende:

fakultet(5) = 5 * fakultet(5 - 1) fakultet(5 - 1) = 4 * fakultet(4 - 1) fakultet(4 - 1) = 3 * fakultet(3 - 1) fakultet(3 - 1) = 2 * fakultet(2 - 1) fakultet(2 - 1) = 1 * fakultet(1 - 1) fakultet(1 - 1) = 1

Funktionen modtager 5, da 5 ikke er lig med nul, ganger funktion 5 med funktionen selv bare med 4 som argument, og den bliver så ved på denne måde indtil argumentet er reduceret til $0$. Her returneres simpelthen et 1-tal, der modtages af funktionen før der returnerer $1 \cdot 2$ til den næste funktion der returnerer $2 \cdot 3$ osv. For at funktionen ikke skal blive ved med at returnere sig selv i en uendelighed, er det vigtigt at punkt 1 i defintionen er angivet, altså 0! = 1. Læg mærke til, at hvis 0! = 0, ville n! = 0 for alle n.

En anden måske endnu mere almindelig funktion der kan defineres rekursivt, er eksponentialfunktion. Lad os hoppe direkte til koden:

function eksponential(x,n){ if(n === 0){ return 1; } return x * eksponential(x, n - 1); }

Læg mærke til at den er næsten identisk med fakultet. Forskellen er her at vi har en base, x, som ikke forandrer sig, og et n der er antallet af gange basen skal ganges med sig selv. Funktionen tager altså to argumenter denne gang. For $5^5$ får vi følgende:

eksponential(5, 5) = 5 * eksponential(5 - 1); eksponential(5, 5 - 1) = 5 * eksponential(4 - 1); eksponential(5, 4 - 1) = 5 * eksponential(3 - 1); eksponential(5, 3 - 1) = 5 * eksponential(2 - 1); eksponential(5, 2 - 1) = 5 * eksponential(1 - 1); eksponential(5, 1 - 1) = 1;

Den starter med at gange fem med sig selv, og det bliver den ved med indtil $n = 0$ hvor den stopper det rekursive forløb og ganger fem med 1. Derefter går den den anden vej igen, 1 bliver ganget med 5 der bliver ganget med 5 osv. Dette giver definitionen:

$x^{0} = 1$
$x^{n} = x \cdot x^{n - 1}$

Igen i to trin, og igen er n = 0 det vigtige stoptrin uden hvilket funktionen ville vælte derudaf i en uendelighed.

Den sidste rekursive funktion vi skal se på, er en klassiker der faktisk normalt bliver defineret rekursivt. Det er nemlig Fibonnaciotalrækken. Den blev beskrevet i 1200-tallet af den italianske matematiker Fibonacci og handler vist om kaniner. Ideen er at et kaninpar avler to unger der videre formerer sig, men først efter to kanincyklusser. Dette forløb fortsætter så og kan dermed beskrives ved en talrække hvor hvert tal efter det tredje er summen af de to forgående. Det lyder måske mere kompliceret end det er, så lad os bare hoppe direkte til koden:

function fibonacci(n){ if(n >= 2){ return fibonacci(n - 2) + fibonacci(n - 1); } return 1; }

$ n $ er altså det n'te tal i talrækken som er summen af de to forgående. Udregningerne ser således ud for n = 5:

fibonacci(5) = fibonacci(5 - 2) + fibonacci(5 - 1); fibonacci(5 - 1) = fibonacci(5 - 3) + fibonacci(5 - 2); fibonacci(5 - 2) = fibonacci(5 - 4) + fibonacci(5 - 3); fibonacci(5 - 3) = fibonacci(5 - 5) + fibonacci(5 - 4); fibonacci(5 - 4) = 1; fibonacci(5 - 5) = 1;

Som det ses, bliver situationen hurtigt meget kompliceret for computeren. For hvert genkald af funktionen avler den nemlig sig selv to gange da den skal finde to værdier. Den starter med at finde $fibonacci(5 - 2)$ og $fibonacci(5 - 1)$ der finder $fibonacci(5 - 4)$ og $fibonacci(5 - 3)$ hhv. $fibonacci(5 - 3)$ og $fibonacci(5 - 2)$. Antallet af funktioner der er i omløb, vokser altså eksponentielt, de bliver fordoblet for hver gang. Defintionen er:

$F_{0} = 1$ og $F_{1} = 1$
$F_{n} = F_{n - 2} + F_{n - 1} , n \geq 2$

Denne gang er der altså et interval af stopklodser nemlig $[0,1]$ da de to første gennemløb returnerer $1$. De første fjorten elementer med indeks er:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	2	3	5	8	13	21	34	55	89	144	233	377

Og ud fra tabellen er det ikke så svært at danne nye elementer, feks. er element med indeks 14 lig med det trettende plus det tolvte som er $233 + 377 = 610$. Med fjorten kan femten let findes som $377 + 610 = 987$. Den rekursive definition for en computer, altså algoritmen, er måske derfor unødigt kompliceret. Hvis du skriver for store tal, som er tal større end 40, kommer der nok en scriptfejl.

En alternativ (nu rekursiv) måde at programmere Fibonaccifunktionen på kan være:

function fibFast(n,A){ var A = A || [1,1]; if(typeof A[n] === "undefined") { A.push(fibFast(n - 1,A) + fibFast(n - 2,A)); } return A[n]; }

Dette edit er et eksempel på noget der hedder dynamisk programmering. Ideen er den at for hver rekursion slår funktionen op i et array. Hvis værdien allerede eksistere, bruger den opslaget. Det virker fordi den langsomme version af Fibonacci regner en masse værdier 2 gange. Feks. i gennemgangen ovenfor regnes 5 - 3 to steder. Dette undgår vi ved at inkludere et array. Her er funktionen, og denne gang kan den regne ret store værdier af n:

Fibonacci har en historisk status, så mere om ham kan læses her

Index

Del