Rekursive funktioner i C#

Jeg har snakket med et par undervisere omkring kunsten at lære rekursivitet på et simpelt plan, og lovede at smide et par eksempler jeg selv benytter.

Den klassiske rekursive metode er traversering af filsystemet. Opgaven er

Skriv en metode der kan udskrive navnet
på alle filer i en mappe og alle dens undermapper

Dette kunne løses som: 

static void FindFiler(string sti)
{
    var filer = System.IO.Directory.GetFiles(sti);
    foreach (var fil in filer)
        Console.WriteLine(fil);
    var mapper = System.IO.Directory.GetDirectories(sti);
    foreach (var mappe in mapper)
        FindFiler(mappe);
}

Eller – lidt mere funktionsorienteret (kræver “using System.Linq” i toppen af siden):

static void FindFiler(string sti)
{
    System.IO.Directory.GetFiles(sti).ToList().ForEach(i => Console.WriteLine(i));
    System.IO.Directory.GetDirectories(sti).ToList().ForEach(i => FindFiler(i));
}

En mere simpel opgave kunne også være:

Tæl fra et tal til et andet tal –
uden at benytte en løkkestruktur

Her er en mulig løsning:

void RekusivMetode(int start, int stop) {
    Console.WriteLine(start);
    if (start == stop)
        return;
    start++;
    RekusivMetode(start, stop);                
}

Hvis du har tid i undervisningen er tegning og manuel traversering af et binært træ på tavlen også en super god øvelse.

Du præsenterer eleverne for følgende kode (fungerende Console App):

using System;

namespace Rekusivitet
{
    class Program
    {
        static void Main(string[] args)
        {
            Node n = DanTræ();
            PrintTal(n);
        }

        static Node DanTræ() {
            Node n = new Node(2);
            n.VenstreNode = new Node(7);
            n.HøjreNode = new Node(5);
            n.VenstreNode.VenstreNode = new Node(2);
            n.VenstreNode.HøjreNode = new Node(6);
            n.VenstreNode.HøjreNode.VenstreNode = new Node(5);
            n.VenstreNode.HøjreNode.HøjreNode = new Node(11);
            n.HøjreNode.HøjreNode = new Node(9);
            n.HøjreNode.HøjreNode.VenstreNode = new Node(4);
            return n;
        }
        static void PrintTal(Node mor)
        {
            Console.WriteLine(mor.Tal);
            if (mor.VenstreNode != null)
                PrintTal(mor.VenstreNode);
            if (mor.HøjreNode != null)
                PrintTal(mor.HøjreNode);
        }
    }

    class Node
    {
        public int Tal { get; set; }
        public Node HøjreNode { get; set; }
        public Node VenstreNode { get; set; }

        public Node(int tal)
        {
            Tal = tal;
        }
    }
}

Første opgave er at tegne træet på tavlen efter metoden DanTræ() – det giver også en god forståelse for hvordan objekter er placeret på heap’en. Lad en kursist tegne en node hver (giver lidt tid til at “tænke med”). Det skulle gerne ende i noget ala:

Billede fra WikiPedia

Nu skal eleverne så traversere træet ud fra metoden PrintTal(Node n). Målet er at finde ud af i hvilken rækkefølge programmet udskriver tal på konsol. Det skulle gerne blive til følgende:

2
7
2
6
5
11
5
9
4

Et mere forretningsorienteret eksempel kunne være kalkulering af en samlet pris på et tilbud på en kompleks vare som består af mange forskellige varer (eksempelvis en bil, stor maskine eller et typehus). Et tilbud består af en samling varer, samt et eller flere andre tilbud (som igen kan bestå af varer og tilbud, som igen kan bestå af…). Det er typisk set i de fleste ERP systemer, og et godt eksempel på praktisk rekursivitet.