Tag: recursion

Interesting programming exercise- no loops

Interesting programming exercise- no loops

Posted on by David
Recursive fractal
Image by Pete Linforth from Pixabay

I read about a university course where the students had to write C code without using For, While or Goto for loops. Instead they had to use recursion.

Yes it’s bound to be inefficient compared to the looping structure but that’s not the point. For instance for a loop like this:

for (int i=0;i<10;i++) {
   DoSomething(i);
}

It could be done as

void DoSomething(int i) {
   if (i==10) return;
  // Do whatever here
   DoSomething(i+1);
}

DoSomething(0);

The point isn’t to teach you to write inefficient code but to think a bit differently. I’ve used recursion quite extensively in the Slay tutorials code. Here’s an example. It sets a field continent in all adjacent land squares where continent == -1.

void FillIn(int x, int y, int island) {
	if (onMap(x, y)) {
		if (island == map[x][y].island && map[x][y].continent == -1) {
			map[x][y].continent = numContinents;
			allContinents[numContinents].count++;
			FillIn(x - 1, y, island);
			FillIn(x + 1, y, island);
			FillIn(x, y - 1, island);
			FillIn(x, y + 1, island);
			FillIn(x - 1, y - 1, island);
			FillIn(x + 1, y - 1, island);
			FillIn(x + 1, y + 1, island);
			FillIn(x - 1, y + 1, island);
		}
	}
}
Using recursive fill to count maps

Using recursive fill to count maps

Posted on by David

Terrain hexagonsIn the Empire game (yes, just one last mention!) during the map generation the program counts up the size of individual islands and sea areas. This is don by recursion and quite useful. Otherwise, the usual place you see recursion mentioned is in calculating factorials and Fibonacci sequences.

The map struct holds not only the terrain type and other information but a continent number. This is set initially to 0.  After the land and seas have been generated, the program picks a random land point on the map (just keep picking a random location until it has land with a continent number of 0).

It then counts by calling itself 8 times. It calls itself recursively at location y,x with directions (y-1,x-1) that’s NorthWest, (y-1,x)  and so on round to West (y,x-1).  But it only does it as long as each of those locations is land type with a continent number of 0. And as it does it, it sets the continent numbers in each location to 1 for the first continent and so on.

This recursive algorithm means that every contiguous land location gets reached. A similar thing is done with seas and lakes but you have to be careful that the stack is large enough.

void FillIn(int x,int y,int locis) {
  if onMap(x,y) {
    if (locis==map[x][y].locis && map[x] 
 [y].continent==UNALLOCATED) { 
      map[x][y].continent=numconts;
      allconts[numconts].count++;
      FillIn(x-1,y,locis);
      FillIn(x+1,y,locis);
      FillIn(x,y-1,locis);
      FillIn(x,y+1,locis);
      FillIn(x-1,y-1,locis);
      FillIn(x+1,y-1,locis);
      FillIn(x+1,y+1,locis);
      FillIn(x-1,y+1,locis);
    }
  }
}

This is used for both land and sea, so locis can be either. It’s an efficient algorithm and quite quick.

Those graphics? They were the initial hexagon graphics…