Rekursive funksjoner

Rekursive funksjoner, eller funksjoner som kaller seg selv, kan virke svært attraktive ved første øyekast. Men i de aller fleste tilfeller er rekursjon i PHP noe du bør forsøke å unngå.

Iterative funksjoner, dvs. funksjoner som benytter seg av løkker istedenfor rekursjon, er i de aller fleste tilfeller raskere enn sine rekursive motparter. Viktigst av alt er at det alltid er mulig å skrive om en rekursiv funksjon til en iterativ funksjon.

Det aller vanligste eksempelet å bruke her, er Fibonacci-tallene. Rent matematisk er Fibonacci-tallene en rekke som begynner med 0 og 1, og resten av tallene er summen av de to foregående tallene. De første 14 tallene i rekken blir da 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 og 233.

Å skrive en rekursiv funksjon som beregner disse tallene er svært enkelt;

<?php
    function recursiveFibonacci($n)
    {
        if ($n == 1) return 0;
        elseif ($n == 2) return 1;
        else return (recursiveFibonacci($n - 1) + recursiveFibonacci($n - 2));
    }
?>

Å bruke denne funksjonen til å regne ut det 25. Fibonacci-tallet tar omtrent 0,3 sekunder. Det 30. tallet tar 3,6 sekunder, og det 35. tallet tok hele 39,5 sekunder. Det 36. tallet brøt 60-sekundersgrensen for kjøretid (legg merke til at PHP som standard har denne grensen satt ved 30 sekunder).

Hvorfor er recursiveFibonacci så rask på de første 25 tallene, men likevel så treig på det 35. tallet? Svaret ligger i de rekursive kallene. Om vi ser på hvor mange ganger recursiveFibonacci-funksjonen blir kalt når vi spør etter det femte Fibonacci-tallet, ser man det enkelt;

Hver firkant i dette treet representerer ett kall til recursiveFibonacci, og for det femte Fibonacci-tallet ser vi at funksjonen blir kalt 9 ganger. For å finne det sjette Fibonacci-tallet, må vi kalle funksjonen 15 ganger, for å finne det syvende må vi kalle funksjonen 25 ganger, og så videre. Tallet øker fort, og vi hadde ikke hatt plass til å tegne opp et slikt tre for recursiveFibonacci(8).

Hva gjør man?

Det første man kan gjøre for å gjøre den rekursive funksjonen raskere, er å innføre minne. Funksjonen husker da verdier den har regnet ut tidligere, og man kan da kutte omtrent halvparten av treet ovenfor. Koden blir da som følger;

<?php
    function recmemFibonacci($n, &$mem = Array(0, 1))
    {
        if (isset($mem[$n-1]))
            return $mem[$n-1];
        else
        {
            $new = recmemFibonacci($n-1, &$mem) + recmemFibonacci($n-2, &$mem);
            $mem[$n-1] = $new;
            return $new;
        }
    }
?>

Denne nye funksjonen gjør at det ikke lenger vil være vanskelig å regne ut det 35. Fibonacci-tallet, og utregningen følger fremdeles det rekursive prinsippet. Forskjellen er at vi har innført et minne som husker alle Fibonacci-tallene vi har regnet ut tidligere, og det er denne tankegangen vi ønsker å følge.

Ved å tenke litt på hva det egentlig er vi gjør, ser vi at utregningen også kan gjøres ved hjelp av en for-løkke istedet for rekursjonen;

<?php
    function itermemFibonacci($n)
    {
        $mem = Array(0, 1);
        for ($i = 2; $i < $n; $i++)
        {
            $mem[$i] = $mem[$i-1] + $mem[$i-2];
        }
        return $mem[$n-1];
    }
?>

Denne versjonen er svært mye raskere enn recursiveFibonacci, og gjør det også svært lett å finne hele Fibonacci-rekken frem til f.eks. det 35. Fibonacci-tallet. Utregningen av det 100. Fibonacci-tallet var også øyeblikkelig med denne funksjonen, selv om PHP skifter over til normalform når den oppgir så store tall.

Dersom du skal ha flere tall i Fibonacci-rekken er funksjonen over den enkleste, men man kan likevel dra litt mer ut av maskinen dersom man bare skal ha et eneste Fibonacci-tall. Ved å la være å lagre mer enn de 2 siste Fibonacci-tallene når man kjører funksjonen, sparer man noe minne.

<?php
    function iterativeFibonacci($n)
    {
        $oldest = 0;
        $old = 1;
        for ($i = 2; $i < $n; $i++)
        {
            $new = $old + $oldest;
            $oldest = $old;
            $old = $new;    
        }    
        return $new;
    }
?>