Rekursion för nybörjare

Vad är rekursion, när gör man det och hur? Jag delar upp frågan i tre delar:

• Vad är rekursion?
• När använder man rekursion?
• Hur använder man rekursion?

Vad är rekursion

Inom programmering handlar rekursion om att repetera en beräkning fler gånger tills man når sitt mål och då returnera svaret, en beräkning är inte avslutad förens svaret returneras.

Om man skulle göra en liknelse med verkligheten kan man föreställa sig att en person (funktion) har möjligheten att skapa kopior av sig själv genom att ropa en fråga in i en tratt. När ljudet kommer ut ur tratten finns exakt samma person på andra sidan förutom att det är en ny instans, en ny exakt likadan människa. Den människa som tar emot frågan har samma möjligheter som den som ställde frågan att svara på frågan.

Det faktum att personen som tar emot frågan har samma möjligheter att svara på frågan som den som inte kunde svara på frågan kanske låter lite dumt, om dom nu har samma beräkningskapacitet, hur ska då den andra kunna svara på något som inte den första kan? Nu kommer det något finurligt, den som ställer frågan tar inte bara in information i öronen och ropar ut en fråga in i tratten utan förenklar även problemet. Om inte problemet kan förenklas och inte lösas direkt går det inte att lösa alls. Däremot, så länge problemet förenklas för varje rop kommer man någonstans i framtiden att nå slutet. Därifrån ropas sedan svaren tillbaka åt andra hållet genom tratten och den person som tidigare ropade frågan får ett svar. Svaren byggs ihop allteftersom och till slut hamnar det sista svaret hos den första personen i kedjan som slår samman det sista svaret med sin egen förenkling och sedan ropar ut det kompletta svaret.

Det är svårt att göra en liknelse med verkligheten eftersom förutsättningarna är helt olika, det finns inte samma möjligheter att skapa kopior av människor. Jag har inte tagit droger även om det verkar så av beskrivningen. En del av det svåra med rekursion är inte att lyckas genomföra det utan att förstå hur det fungerar. Här är ett exempel på rekursion:

function factorial(n) 
{
  if (n <= 1)
    return 1;
  else
    return n * factorial(n-1);
}

Funktionen anropar sig själv tills parametern n är mindre än eller lika med ett. Då skickas resultatet upp för stegen (enligt bilden i föregående post). För varje anrop ned för trappan minskas värdet (problemet förenklas).

När använder man rekursion

Inom programmering har rekursion i takt med att programmering gått ifrån konst till teknik fasats ut. Vissa problem (exempelvis för att beräkna ett godtyckligt tal i fibonacciserien) går inte att lösa utan rekursion och då används det men i stort innebär rekursion ett stort "NO-NO". Det som väger tyngst mot rekursion är att för varje rekursivt anrop sparas en kopia av föregående funktion i minnet och ja du förstår, till slut tar minnet slut och då når man aldrig lösningen utan i bästa fall avslutas programmet av operativsystemet och i värsta händer ingenting, ingenting alls. Ett annat potentiellt problem är att rekursion, även om det är vackert, kan vara svårt att förstå och speciellt om man inte har skrivit koden själv utan ska försöka tyda någon annans vilket händer allt oftare idag. Om man kan ska man undvika rekursion. Oftast finns en likvärdig lösning utan rekursion som kodsnutten här nedan som gör exakt samma sak som den ovan men utan rekursion utan med en loop:

function factorial(n)
{
  if (n <= 1)
    return 1;
  else
  {
    var result = n;
    while (n-- > 1)
      result *= n;
    return result;
  }
}

Tyvärr finns inte loopar inom strikt funktionell programmering så där får man hålla tillgodo med rekursion. Men vad jag förstår används strikt funktionell programmering främst i den akademiska världen. Exempelvis Lisp (som är ett funktionellt programspråk) tillåter både loopar och rekursion.

Hur använder man rekursion

Ett förvånansvärt enkelt svar är att så fort en funktion anropar sig själv uppstår rekursion. Om du vill använda rekursion kan du alltså låta en funktion anropa sig själv helt enkelt men oftast vill man även utföra en beräkning som i fibonacciberäkningen här nedan som tar ett tal n som motsvarar vilket tal i serien man vill ha ut:

long fibonacci(int n)
{
  if (1 == n || 2 == n) {
    return 1;
  } else {
    return (fibonacci(n-1) + fibonacci(n-2));
  }
}

För att skapa en sådan funktion börjar man vanligtvis med att definiera ett slutvilkor där rekursionen ska vända om (där anropen går ifrån ovansidan av stegen till undersidan i bilden), här utgörs slutvilkoret av att parametern n tar värdet 1 eller 2. Därefter lägger man till det rekursiva anropet, minst ett men kan vara flera som i exemplet. Det är viktigt att problemet förenklas, som här genom att parametern minskar med 1 respektive 2 för varje anrop. Därefter kan funktionen anropas.

Det verkar kanske inte så svårt om man kan programmera men att uppfinna fibonacciserien är en helt annan femma.