Inledning

Rekursivitet är en teknik som kan användas för att lösa vissa uppgifter inom programmering. Olika språk hanterar detta olika. C#, Java, C++, m.fl. har for- och while-loopar som löser i princip de flesta problem utan att involvera rekursivitet. Andra språk, som t.ex. Haskell, saknar helt for- och while-loopar och förlitar sig helt på rekursivitet. Här finns en typisk skillnad mellan sk. imperativa språk och funktionella språk.

Alan Turing skrev en historiskt viktig avhandling 1936. Den beskriv inte bara hur en dator skulle kunna konstrueras utan även vad den var kapabel att lösa för problem. Han bevisade redan då att en tänkt dator (Turingmaskin) skulle kunna lösa alla problem som var beräkningsbara. Rekursivitet var något centralt i tanken kring en "dator" och hur problem skulle kunna lösas.

På gymnasienivå, i kursen Programmering 1, fanns det länge ett krav att kunna rekursivitet för vissa betygsnivåer. Sedan hösten 2015 har formuleringarna ändrats och nu finns det inget formellt krav längre på detta. Läraren kan fritt välja "enklare algoritmer, t.ex. sök- och sorteringsalgoritmer". Det utesluter inte att man går igenom rekursivitet, vilket vi på csharpskolan tycker är viktigt.

Vad krävs?

Rekursiva algoritmer är algoritmer som är implementerade på ett visst vis. Det betyder att det finns både sök- och sorteringsalgoritmer som är rekursiva. Att en algoritm är rekursiv betyder att algoritmen "kallar på sig själv".

Vi definierar rekursiva program/algoritmer som sådana som "anropar sig själva" via metod och som har ett definierat basfall.

För att kalla, eller anropa, sig själv så måste algoritmen implementeras i en metod.

För att en rekursiv algoritm inte ska anropa sig själv i all evighet så krävs det också ett definierat basfall som talar om när algoritmen är klar.

Faktum är att alla problem/algoritmer kan lösas rekursivt (tack Alan Turing!). Men det omvända, att rekursiva problem kan lösas iterativt, stämmer inte alltid. Vi kan börja med ett enkelt problem löst med iteration. Vi tar ett exempel där vi med en loop skriver ut talen 0 till 10.

using System;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i <= 10; i++)
            {
                Console.WriteLine(i);
            }
		}
	}
}

För att skriva om exemplet ovan till att använda rekursivitet så behöver vi införa en metod och ett basfall.

using System;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            SkrivUtTal(0);
		}
		
		static void SkrivUtTal(int i)
        {
            if (i > 10)
                return;
            Console.WriteLine(i);
            SkrivUtTal(i + 1);
        }
	}
}

Om vi "följer" programmet så börjar vi med att anropa SkrivUtTal men inparametern 0. I metoden görs arbetet att skriva ut talet och sedan anropar metoden "sig själv" med ett ökat värde på inparametern. Detta upprepas ett antal gånger innan vi når basfallet.

Basfallet är då i > 10. Där slutar alla anrop till nya metoder. Programmet börjar sedan återvända till det stället som metoden anropades ifrån. Nu när vi anropat metoden SkrivUtTal flera gånger så återvänder vi flera gånger till samma ställe i koden. Det "cirkelmönster", som rekursivitet är, har brutits med basfallet och vi börjar "nysta upp" anropen igen.

Programmet blir klart och utför exakt samma uppgift som i det iterativa exemplet.

Olika sorters rekursivitet

Inom datavetenskapen pratar man om olika sorters rekursivitet. Problem kan kategoriseras in i följande fyra uppdelningar av rekursivitet:

• Primitive recursive
• Recursive
• Recursively enumerable
• Undecidable

Problem som är primitive recursive är sådana problem som kan lösas med iteration istället för rekursivitet. De flesta algoritmer som presenteras i denna artikel är sådana att vi kan implementera dem iterativt istället. Primitive recursive inkluderar även alla vanliga program och problem som t.ex. använder enkla och nästlade loop'ar.

Algoritmer av typen recursive är sådana problem som inte går att skriva om iterativt. Sorteringsalgoritmen är ett exempel. En annan mer svårberäknad algoritm är Ackermanns funktion.

Nästa steg är algoritmer av typen Recursively enumerable. Här hamnar de algoritmer som, beroende på viss input, kanske aldrig ger ett svar. För viss indata så ges ett svar men för annan indata så kanske algoritmen fortsätter i evighet utan att vi märker det.

Sist men inte minst så har vi de algoritmer, eller problem, där vi helt enkelt inte kan avgöra om det finns ett svar/lösning. De kallas undecidable.

Fibonacci

Vi tänkte diskutera lite mer kring ett enklare exempel; Fibonacci. Fibonacci-serien är en serie av tal som bildas genom att man tar summan av de två föregående talen. Säg att de två första talen är 1, 1. Vad blir det tredje?

Ja 1 + 1 = 2. Serien utvecklar sig enlig följande: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Det som är intressant med Fibonacci är just att t.ex. det sjunde talet, F(7), kan beräknas med F(6) + F(5). Det hela blir just rekursivt. Men när ska vi sluta, dvs. vilket basfall har vi? Vi kan kort säga att både F(1) och F(2) är 1!

Vi tar och kikar på koden:

using System;

namespace Fibonacci
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("#7 i serien är: " + F(7));
        }

        static int F(int sekvens)
        {
            if (sekvens <= 2)
                return 1;

            return F(sekvens - 1) + F(sekvens - 2);
        }
    }
}

Det kan vara lite svårt att genomskåda vad som verkligen händer. Det kan bli lite enklare om vi börjar med att fråga oss vad F(2) blir? Svaret är 1 eftersom detta fall är del av basfallet och upptäcks direkt.

Vad blir då F(3)? Denna gång hamnar vi inte i basfallet utan nu blir det på riktigt rekursivt och beräknas med F(2) + F(1), vilket vi båda kommer att få svaret 1 ifrån. Fortsätter vi samma tanke med F(4), F(5) etc. så har vi kanske lättare att inse att det faktiskt fungerar. Det är en snygg och elegant lösning men inte så effektiv.

När vi i exemplet ovan testar att beräkna F(7), vilket ger svaret 13, så sker det en massa rekursiva anrop. Man bör fundera över hur dessa rekursiva anrop "ser ut". Detta kan man åskådliggöra genom att rita upp ett rekursionsträd. I fallet F(7) blir det:

Vill du få en bättre genomgång kring just Fibonacci så har vi diskuterat problemet mer ingående i Klassiska problem .

Stacken

Vad är en stack? Hur används den? Innan vi börjar svara på frågorna så testa följande mycket enkla rekursiva program!

using System;

namespace StackTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Main(null);
		}
	}
}

Som ni kanske märkte så innehöll exemplet ett problem! Vi slutar aldrig de rekursiva anropen, dvs. vi har inte basfall. Efter en ganska kort stund fås följande fel:

Det som händer är ett Stack Overflow!

För att förklara stacken så vill jag att du tänker dig en skola med många salar. Du är "datorn" som ska utföra olika uppgifter. I varje sal finns det ett problem som ska lösas. Till din hjälp har du en penna och ett anteckningsblock. Du börjar jobba med problemet i Sal 1. Efter en kort stund blir du avbryten och ombedd att gå till sal 13. Tyvärr är du inte klar med din uppgift än utan är mitt i några beräkningar.

Eftersom du inte vill göra om allt igen så klottrar du ned en massa minnesanteckningar/delberäkningar i blocket samt en notis om att du ska gå tillbaka till sal 1. I sal 13 är det ett helt nytt problem som väntar. Även denna gång blir du avbryten mitt i arbetet och kallad till sal 7.

Åter igen så anteckar du alla mellanreslutat samt gör en anteckning om att du skall tillbaka till sal 13. Du beger dig till sal 7 och nu får du tid att göra färdigt uppgiften helt i sal 7 utan avbrott.

Hur hittar du sedan tillbaka för att i tur och ordning göra klart uppgiften i sal 13 o 1? Ditt anteckningsblock! Med hjälp av anteckningsblocket vet du vart du ska återvända plus att du har halvfärdiga beräkningar som du kan återuppta.

I metaforen så är skolan själva programmet. Salarna är metoderna. Anteckningsblocket är stacken! Vi hoppade mellan sal 1, 13, 7 och sedan tillbaka i samma ordning. Detta var inte rekursivt men det hade det kunnat vara om vi hade hoppat mellan sal 1, 1 och 1! Vi hade då "startat om" samma problem flera gånger.

Ett stack overflow ges när "anteckningsblocket" är fullt, alltså när minnet till stacken tar slut. Hur mycket minne har man då? Tja det är olika beroende på vilket OS och vilken .NET version som används.

GCD

Vi ska nu titta på en relativt vanlig algoritm kallad GCD = Greatest Common Divisor som oftast implementeras rekursivt. På svenska skulle vi kunna kalla den "största gemensamma delare". På sätt och vis är det en sökalgoritm som försöker hitta den största gemensamma heltalsfaktorn i två heltal.

using System;

namespace GCD
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(gcd(9, 27));
			Console.WriteLine(gcd(111, 259));
        }

        static int gcd(int x, int y)
        {
            if (y == 0)
                return x;
            return gcd(y, x % y);
        }
	}
}

Om vi kikar lite på anropet gcd(111, 259) så kommer anropen att bli:

• = gcd(259, 111% 259)
• = gcd(259, 111)
• = gcd(111, 259% 111)
• = gcd(111, 37)
• = gcd(37, 111% 37)
• = gcd(37, 0)
• = 37

Varför rekursivitet?

Om vi nu kan implementera saker iterativt, varför bry sig om att lära sig tänka rekursivt?

Faktum är att rekursiva implementationer prestandamässigt är sämre än om de hade implementerats iterativt. Detta p.g.a. stacken används så flitigt i varje metod-anrop. Saker ska skrivas på stacken och programmet ska hoppa och eventuellt allokera nytt minne.

Du kommer att uppleva en stor inlärningströskel för funktionella språk, så som t.ex. F# och Haskell, om du inte behärskar rekursivitet.

Det som talar för rekursivitet är helt enkelt att vissa problem måste lösas rekursivt. Sorteringsalgoritmen är ett exempel. Ett annat är problemet att söka efter något i en trädstruktur. Båda dessa problem går att lösa iterativt om man använder en egen "stack" vilket leder oss till sista argumentet.

Rekursivitet är ett mer intuitivt sätt att lösa vissa problem. Koden blir mindre och mer "elegant". Detta förutsätter dock att vi lär oss rekursivitet och när har det någonsin varit en dålig idé att lära sig något som är användbart?

Övningar