Fredag 19/10: Rekursjon og kursinnhold

Kursinnholdet for IBE150 (les studiehandboka) ble studert, og "Rekursjon" er ikke gjennomgått, men ikke omtalt i læreboken. Det engelske "recur" betyr "gjentakelse". Et fenomen skjer om igjen. Hittil har gjentakelser blitt skrevet ITERATIVT (Do-Loop, For-Next). Men, den kan skrives REKURSIVT. To viktige moment:

• programmet skal kalle SEG SELV minst en gang
• programmet skal bryte ut (med "Return" i VB) når det er ferdig -- dette kalles "base case". Uten dette vil rekursjonen gå for langt, hvert kall spiser minne og til slutt resultere i "Out of Memory" kjøretidsfeil (som jo kan fanges med try-catch).

Prøv gjerne eksemplene under på Deres eget apparat: I. Tabellviser. visTabell(X,l) har dere klokelig kodet iterativt:

 
Sub visTabell (a, l)  ' ITERATIV
 For i As Integer = 0 To a.getupperbound(0)
     l.items.add a(i)
 Next
end sub

Klienten kaller denne opp med visTabell(X,lstA) som i tabellomformeren. Men, prosedyren kan kodes rekursivt (selv om det er lurest å gjøre det iterativt):

Sub visTabell (a, l, Byval pos as integer)  ' REKURSIV
 if pos > a.getupperbound(0) Then
    return     ' ikke gå dypere (ferdig!)
 end if
 l.items.add a(pos)
 visTabell (a, l, pos+1)  ' gå dypere!
End Sub

Ved kjøring av en 4-linjers tabell graves en 4-nivås rekursiv brønn:

visTabell(X, lstA, 0)
   visTabell(a, l, 1)
      visTabell(a, l, 2)
         visTabell(a, 1, 3) -- her stoppes rekursjonen!

Eksempel II. Det "klassiske" eksempel er Fibonaccirekken, som Ole og andre Davincikode-lesere visste var 1, 1, 2, 3, 5, 8, 13 ... regel: Neste i rekken er summen av de to foregående. f(n) = f(n-1) + f(n-2) er en rekursiv definisjon, så vi lager en rekursiv kode:

 Function fib (byval n as integer) as integer  ' REKURSIV
    If n < 3 Then
       Return 1
    End If
    Return fib(n-1) + fib(n-2)
 End Function

Denne kan kalles med f.eks. msgbox ("fib 12 er " & fib(12)). Med fib(41) ble kjøretiden ikke bra. Problemet: Samme fibtall (f.ex. f(7)) regnes ut uhorvelig mange ganger. Den rekursive brønn for fib(5)

  fib(5) -- 3 + 2 = retur 2
     fib(4) -- 2+1 = retur 3
        fib(3) -- 1+1 = retur 2
           fib(2) -- retur 1
           fib(1) -- retur 1
        fib(2) -- retur 1
     fib(3) ... (om igjen!!) -- 1+1 = retur 2
        fib(2) -- retur 1
        fib(1) -- retur 1

Det er (også her) lurere å skrive iterativt og bygge en tabell f( ) fra grunnen av (hvert tall regnes da ut bare EN gang):

function fib (byval n as integer) as integer  ' ITERATIV
 dim f(n) as integer
 f(1) = 1
 f(2) = 1
 for i as integer = 3 to n
    f(i) = f(i-1) + f(i-2)  
 next
 return f(n)
end function