Rekursion


Følgende emne er ret svært at forså, så derfor begynder vi med almindelig metode kald. Hvis du har svært ved at forstå rekursion, også efter denne her gennemgang, så skyldes det helst at referencer og metoder ikke er helt på plads for dig endnu. Du bør derfor gå tilbage til disse emner og så komme tilbage til rekurision på et senere tidspunkt.

Rekursion er det samme som metodekald, bort set fra at det er samme metode som kaldes hele tiden.

Rekursion er en metode som kalder sig selv.

En god måde hvorpå man kan forstå rekursion, er ved at tænke på den stak som metoderne bliver lagt i, når de kaldes. Og her er der ingen forskel på en rekusivet kald eller et almindeligt metode kald, alle metoder bliver lagt i stakken. Denne stak holder nu styr på kaldene og returneringerne.

 

Eksempel 1
Lad os først undersøge et almindeligt metode eksempel, som IKKE er rekursive, men som dog har nogle spændende egenskaber, som rekursive metode kald også har, nemlig rækkefølgen af de forskellige kald.
Kode Udskrift

using System;
namespace Rekursion_kald
{
    class Program
    {
        static void Main(string[] args)
        {
            Bil bil = new Bil();
            Console.WriteLine("------Main start-----");
            bil.metode_a();
            Console.WriteLine("------Main slut-----");
        }
   }
    class Bil
    {
        public void metode_a()
        {
            metode_b();
            Console.WriteLine(" jeg er metode A");
        }
        public void metode_b()
        {
            Console.WriteLine(" jeg er metode B");
        }
    }
}

Læg mærke til at "jeg er metode B" skrives først ud, det er lidt mærkeligt, når man ved at metode_a kaldes først.

Forklaringen ligger i at metode_a kalder metode_b før den selv får lov til at printe ud, og derfor printer metode_b først og så når kontrollen kommer tilbage til metode_a, så får den lov at printe, og så når metode_a har printet ud, er der ikke mere at lave, og kontrollen går helt tilbage til Main, og den næste linje er så "Main slut" linjen, og programmet stopper så efter denne udskrift, fordi der er ikke mere at lave.
Den første print sker i mellem 1 og 2, som er "Main start", men den første interessante udskrift sker først i tidspunkt 4, og det er "Jeg er metode B". Grunden er at i tidspunkt 3 hvor man kunne forvente at metode_a printede, der kalder den metode_b, som så kommer på stakken (tidspunkt 4). Metoden_b har ikke andet arbejde end at printe sig selv, og når den er færdig med det ryger kontrollen tilbage til metode_a og vi får tidspunkt 5, hvor metode_a endelig får lov at printe ud. Dette er forklaringen på, hvorfor metode_b printer FØR metode_a. Det er meget vigtigt at forståe dette i dybden, skal man kunne arbejde med rekursion.







Eksempel 2
Nu skal vi undersøge et RIGTIGT rekursions eksempel. Se hvordan metode_a har et metode kald inde i sig selv, som også kalder metode_a, dette er rekursion. Altså en metode som kalder sig selv.

En metode som kalder sig selv er faktisk en uendelig loop, så vi må sætte en stoppere på denne loop, og det gør vi ved at sende en teller med, og når denne kommer op på 3, så kaldes metode_a ikke mere.
Kode Udskrift

namespace Rekursion_kald
{
    class Program
    {
        static void Main(string[] args)
        {
            Bil bil = new Bil();
            Console.WriteLine("------Main start-----");
            bil.metode_a(0);
            Console.WriteLine("------Main slut-----");
        }
    }
    class Bil
    {
        public void metode_a(int teller)
        {
            teller = teller + 1;
            if (teller < 3)
            {
                metode_a(teller);
            }
            Console.WriteLine(teller + " jeg er metode A");
        }
    }
}

En speciel ting med rekursion er at hvert metodekald, har sine egne variabler. Hvert metodekald er en kopi som lægges på stakken. I tilfældet her, har vi teller som er en lokal variabel for hvert tilfælde som ligger på stakken. Dette er ret vigtigt at forstå. Det er derfor vi får en lidt besynderlig udskrift, men den første teller som 3 og den sidste som nummer 1.
Det hele starter når Main metoden kalder metode_a og medsender teller med værdien 0. Dette er illustreret ved den første Stak og teller = 0. Teller bliver dog hurtigt ændret til 1. Og eftersom teller er 1 kommer vi ind i IF delen, som så kalder på metode_a igen og medsender nu IKKE 0 men 1. Det er stak billede 2. Denne udgave af metode_a modtager altså teller som 1, men teller dens egen udgave op til en værdi 2. Og efter som 2 er mindre end 3, får vi stak udgave 3. Metode_a modtager i stak 3, en teller med værdien 2, og teller den selv op til 3. Og når den tjekker ved IF så må den ikke komme ind. Og Stak 3 udgaven er nu kommet til den første udskrift. Den udskriver sin lokal teller variabel, som jo er 3 og så den tilhørende tekst også, men den er mindre interessant her. Når den har udskrevet, er der ikke mere at lave for metoden og kontrollen går tilbage til den som kaldte, og det er illustreret ved stak 4. Metode_a i stak 4 er nu færdig med det arbejde som var inde i IF, og kommer så ned til print delen. Den printer nu sin egent lokale teller som har en værdi på 2. Og så går kontrollen videre den i stakken og ender ved stak 5, som er den første metode_a i stakken. Og dens teller har hele tiden været 1.

Som du ser, så er det ret indviklet at holde styr på alle disse udgaver af metoden og de forskellige variabler.

Rekursion er ret smart til forskellige ting f.eks. udskrift af træer, MEN man skal passe på, fordi - som du ser her - så laves der en KOPI af hele metoden i stakken hver gang man kalder metoden. Dette kan medføre at computeren bruger hele sin hugkommelse og går ned.