Recursive Programming

[aym]

I need non-mathematical examples of recursive programming, I'll program them in java, but I prefer examples that can be programmed in any language.
Thanks in advance.

[aym]

No one

[DrZaius]

Hi aym_7,

Well, the most popular recursion problem is to computer factorials, but since you said non-math examples, here is a different one.

Imagine that on your hard drive you can have types of object, folders and files. Each folder can only contain more folder and files. Now, say you want to go through the drive and print out the name of every file. Here is some pseudo-code that shows how recursion works:

function printFiles (name_of_folder)
{
	open (name_of_folder);

	while (there are objects in the folder)
	{
		if (object is a file)
			print (file's name);
		else if (object is a folder)
			printFiles (folder's name);
	}

	close (name_of_folder);
}

The important part of this function is in the while loop. What it basically does is it goes through every object in the first directory you called and asks, "Is this a file or another folder?" If it is a file the it prints the name of that file. If the object is another folder, then it calls the same function on that specific folder so that it can print the files in that folder. What it's doing is splitting up the work that needs to be done. Think of it this way, printFolder is a function and the only thing it can do is print the name of a file in a specific directory, or create a clone of itself. Here is a sample directory structure:

[Main]
hello.txt
+- [Foo]
   foo.txt
   +- [Bar]
      bar.txt

If I call printFiles(Main), the functon will first ask, is "hello.txt" a file or a folder? Since it is a file it will print "hello.txt" Then it will ask "Is Foo a file or a folder?" Since it is a folder, it will stop what it is doing and call a clone of itself to "take of care of" the foo folder, which in turn will repeat the same process. And since the [Foo] directory contains another sub-directory the function will call yet another clone of the printFiles function to print all the contents of that directory.

I hope that makes some sense, if not I'll try to explain it better.

[aym]

Thanks DrZ! I understand them very well, I'm not a newbie in programming, but I needed some examples for teaching purposes.

[DrZaius]

Thanks DrZ! I understand them very well, I'm not a newbie in programming, but I needed some examples for teaching purposes.

Ohh, sorry then, I though you needed an explanation. Hope it helps anyway.

[Paul Victorey]

I think, as Dr Zaius's example illustrates, anything which natively has a "tree" structure lends itself to recursion. The windows file system (for that manner, ANY file system that supports directories), the windows registry, etc. are good recursive choices.

I used recursion last to take information which I was gathering in a tree window (which was the most intuitive interface for the task) and build arrays of objects, to save to disk for import into another app. Pseudo-code looked somthing like this:

void TreeRecursion::Recurse(TreeNode * n){
   BeforeChildren();
   TreeNode * nextNode;
   for (nextNode = n.GetFirstChild();nextNode != NULL;nextNode=n.GetNextSibling()){
      Recurse(n);
   }
   AfterChildren();
}

I needed, due to how I was building tables, to do some processing before any child nodes were processed, and some after all the node's children were done, hence the BeforeChildren() and AfterChildren().

[Felix]

Hi there,

I'll add an example which I read once in a campus booklet my older brother brought home. Look at the picture:

                ****************
        ********        ********
    ****    ****    ****    ****
  **  **  **  **  **  **  **  **
 * * * * * * * * * * * * * * * *

It's the flag of the recursive states of computania. Unfortunately it's the flag of the iterative states of computania, too... Thus they have all sorts of troubles together because each of them blaims the other to have the flag stolen.

Finally they agreed to make a contest. Each country builds a team of programmers. Each team works and codes and tries hard to make a short, smooth program that builds up the flag of the recursive states of computania... ummm... or was it the iterative states?

Now, go and try to code both of them, the recursive and the iterative version. Which code is smaller? Which looks smoother? Which is easier to understand? What other things do you note?

Hope that helps
Felix

[mosquito]

which code does not cause stack overflows.

[Felix]

of course, but let me add two comments:

1) stack overflows is not an issue with the 5-lines flag shown above.
2) stack overflow is always an issue with recursive programming.

[mosquito]

But the checks to prevent stack overflow are usually omitted. That's what I find in code reviews.

Another real life example for recursive programming is Currency rate triangulation over time, but that sucks so much you don't even want to know how it works.

[aym]

Thank you Felix for the example, I found another good one, it's a puzzle from the Far East:
We have 3 sticks and a set of discs (of different sizes), these discs are placed in the form of a tower around the first stick, and we have to move them to the third stick (using the second stick), and there are two rules:
1. We can move only one disc at a time.
2. The discs on each stick should always look like a tower.
The solution of this puzzle can be programmed in a recursive method:

//n is the number of discs around the SourceStick
//I will refer to the sticks by numbers (1,2,3)

void moveDiscs(int n, int SourceStick, int TempStick, int TargetStick) {
    if (n == 1)
        println("Move from " + SourceStick + " to " + TargetStick);
    else {
        moveDiscs(n - 1, SourceStick, TargetStick, TempStick);
        println("Move from " + SourceStick + " to " + TargetStick);
        moveDiscs(n - 1, TempStick, SourceStick, TargetStick);
    }
}

[Demosthenes]

The good old Towers of Hanoi. It is the definitive example of stacks, recursion, induction, etc. It is very versatile. There is a good story that goes with it, too. The Monks of some monastery had a whole room with 63 (or whatever) giant gold rings and three pegs. They believed that when someone moved the entire stack from one peg to another, the world would be destroyed. Calculate how many steps this would require.

Respectfully,

Demosthenes