Tags:    .net Emnet i denne artikel er måske kendt af de fleste. Rekursion bruges typisk når man skal udføre den samme opgave flere gange efter hinanden. Rent teknisk laves det på en sådan måde at man bygger en metode der kalder sig selv!

Applikationen

For at forstå mere omkring rekursion har jeg valgt at tage udgangspunkt i at bygge et directory-tree, det vil sige en oversigt over alle filer og mapper på min computer. Grunden til at dette skal gøres rekursivt er at jeg ikke ved hvor dybt jeg har behov for at komme ned i mine mapper, vidste jeg det kunne jeg sagtens have lavet en for-løkke for hver niveau og så liste mine filer og mapper i en liste. Denne løsning dur dog ikke dag jeg ikke ved hvor dybt jeg skal ned, så jeg er nødt til at vælge en anden løsning - Rekursion. Hvis man kigger på den opgave der skal udføres er det altid en god ide at sætte sig ind i de delopgaver denne består af. Jeg gør det typisk ved at "lade" som om jeg er metoden og så lave en liste over det "jeg" skal udføre, i dette tilfælde vil det så nogenlunde således ud:

Jeg har et root directory
Jeg skal liste alle de filer der er i det root directory
Jeg skal liste alle de mapper der er i det directory
for hver mappe skal jeg kalde mig selv med mappens sti (så starter det forfra og mappens sti bliver til root directory)

Det første vi starter med er at lave en ny Windows Applikation i Visual Studio og laver et TreeView der docker i center (fill).



For at vores applikation skal se lidt godt ud vil vi have et mappe ikon for alle de mapper der er og et fil ikon for alle filerne. Tilføj nu en ImageList til løsningen og indsæt to billeder i listen.



Det betyder at vi nu har en ImageList der indeholder to billeder (de skal helst være PNG eller GIF for at bevare deres transparency)


Når dette er gjort vil vi knytte vores ImageList til vores treeview, dette gøres for at fortælle vores treeview hvilke billeder der er tilgængelige for de Nodes vil vil indsætte deri.

Koden

Når vi har fået lavet vores layout og lidt ekstra eye-candy er det tid til at lave vores reelle funktionalitet. Vi holder for øje den liste vi tidligere har lavet der beskriver hvordan den rekursive funktion er opbygget. Dette betyder at jeg laver en funktion der kan gøre det vi tidligere har beskrevet, den kommer til at se således ud (bemærk at der skal importeres System.IO for at kunne bruge DrectoryInfo of FileInfo):

1 private void ShowTree(string root, TreeNode dirnode)
2 {
3 	ShowFiles(root, dirnode);
4	DirectoryInfo rootdirectoryinfo = new DirectoryInfo(root);
5	DirectoryInfo[] mydirs = rootdirectoryinfo.GetDirectories();
6	for(int j=0;j<mydirs.Length;j++)
7	{
8		DirectoryInfo localinfo = mydirs[j];
9		TreeNode folderNode = new TreeNode();
10		folderNode.Text = localinfo.Name;
11		folderNode.ImageIndex = 1;
12		if(dirnode != null)
13		{
14			dirnode.Nodes.Add(folderNode);
15		}
16		else
17		{
18			treeView1.Nodes.Add(folderNode);
19		}
20		ShowTree(localinfo.FullName, folderNode);
21	}
22 }

Selve methoden tager en string og en TreeNode med ind. Den streng der kommer ind er den fulde sti til den mappe vi arbejder med. Den anden parameter er faktisk kun med for at kunne indsætte vores nodes direkte ind i vores TreeView, rent rekursionsmæssigt er den irellevant da den sådan set ikke har nogen funktion andet end blot indsætte vores nodes korrekt i træet. For at lette overblikket har jeg valgt at lave en metode der hedder ShowFiles, det eneste den blot gør er at finde en liste af filer i det directory der sendes med som parameter 1, og derefter lave nogle treenodes den tilføjer til den TreeNode den tager med ind i parameter 2. I linie 4 Laver vi en ny instans af DirectoryInfo klassen hvor parameteret er strengen "root", denne klasse giver os mulighed for at kunne trække en liste af alle de filer der er i den mappe, samt en liste over alle de mapper der er i den mappe. I linie 5 laver vi så en liste over alle de mapper der er i vores root directory (i den rekursive funktion er det den mappe vi er nået til), derefter begynder vi at traversere (gennemløbe) vores liste af mapper (linie 6) og lave en TreeNode og sætte dens billede til det korrekte (linierne 8, 9, 10, 11). Nu kommer der et stykke kode der kun vil blive kørt een gang, nemlig første gang. For at kunne placere vores treenodes korrekt i vores træ, det vil sige under den mappe de hører til ) har vi valgt at sende en TreeNode med ned i metoden som parameter (dirnode), første gang vi kalder denne metode er den null, det betyder at vi skal teste på at hvis den er null, skal vi tilføje vores treenode til roden af vores træ, ellers skal det tilføjes til den node der er parent (linierne 12-19). Nu kommer det sted hvor vi skal holde tungen lige i munden. For at vende tilbage til vores huskeliste for denne rekursive funktion kan vi konstantere at vi nu har udfyldt de tre øverste punkter og skal til at lave den sidste, i denne del skal jeg "kalde mig selv med mappens sti". For at kalde mig selv skal jeg sende to parametre med: parameter 1 er en streng der repræsenterer den fulde stil til den mappe jeg skal arbejde med. Parameter 2 er den TreeNode hvortil jeg skal tilføje både filer og mapper der ligger under den mappe jeg sender med. Dette er hele humlen i en rekursiv funktion, bemærk at jeg i linie 20 kalder "mig selv" det vil sige den funktion jeg selv befinder mig i med parameter 1 som det fulde navn på det directory jeg skal til at arbejde med og med parameter 2 som værende den TreeNode jeg har tilføjet til træet (dette vil altid være en mappe, da det kun er dem jeg gennemløber jævnfør linie 5). Faktisk er disse få liniers kode nok til at lave en hel liste over alle filer og mapper på en harddisk (måske ikke så smart, men et godt eksempel). For en god ordens skyld vil jeg også vise koden til ShowFiles metoden:

private void ShowFiles(string directory, TreeNode foldernode)
{
	DirectoryInfo dirinfo = new DirectoryInfo(directory);
	FileInfo[] files = dirinfo.GetFiles();
	for(int j=0;j<files.Length;j++)
	{
		FileInfo file = files[j];
		TreeNode fileNode = new TreeNode();
		fileNode.Text = file.Name;
		fileNode.ImageIndex = 0;
		if(foldernode != null)
		{
			foldernode.Nodes.Add(fileNode);
		}
		else
		{
			treeView1.Nodes.Add(fileNode);
		}
	}
}

Og selve det metode kald der instantiere hele rekursiviteten:

ShowTree("D:\\\\", null);

Når jeg kører den på mit D: får jeg et træ der ser således ud:

Optimering

Som jeg skrev en komentar om tidligere er det måske ikke så smart at kalde disse funktioner på sit C: da det vil tage en evighed inden der kommer noget i træet, dette skyldes naturligvis at den skal scanne alle filer på disken. En bedre måde at gøre dette på er ved at kun vise det øverste niveau og når brugeren så folder en mappe ud, så loader man det næste niveau og så videre, således man hele tiden kun viser brugeren det denne ønsker at se og derved ikke loader en masse unødvendigheder. Et andet vigtigt element ved rekursioner er at den SKAL tage skridt mod terminering, ellers vil det resultere i en uendelig løkke. I dette eksempel er skridtet mod terminering at den stopper når der ikke er flere filer og mapper på disken den ikke har undersøgt.


Hvad synes du om denne artikel? Giv din mening til kende ved at stemme via pilene til venstre og/eller lægge en kommentar herunder.

Del også gerne artiklen med dine Facebook venner:  

Karma barometer (30 dage)

IT jobs | Kontakt | Om Udvikleren.dk | Om karma | IT nyheds arkiv | Annoncering

X