Some Coding Techniques For Beginners

Introduction

This article is for all the people out there who are trying to code graphics but are finding it hard to even implement their ideas, or understand what is going on in other people's code. I'll introduce some coding methods used by slightly more advanced coders here, firstly (in this article) recursion. GET LOST if you are 3x10^4 + 1x10^3 + 3x10^2 + 3x10 + 7.

Code Recursion

You may or may not have heard of this technique before, it's very common and very, very powerful. It's identified by a function calling itself, for example,

void CodeRecursiveFunction(int HowManyTimesCalled)
{
   if(HowManyTimesCalled > 5) return;
   else CodeRecursiveFunction(HowManyTimesCalled + 1);
   return;
}

What will that do? We'll think about it later. Let's talk about when to use recursion, recursion is used when you are trying to do something, and after each step of the algorithm, you are left with the same problem (or things to do) but on a smaller scale. Recursion is very often used for trying all possibilities of something, here is a problem, which recursion can be applied to:

Problem: A man called Willie lives on a 4x4 grid, each unit of the grid is raised to a certain height, like in the diagram:

		      кФФФФТФФФФТФФФФТФФФФП
		 Г 1  Г 8  Г 2	Г 4  Г
		 УФФФФХФФФФХФФФФХФФФФД
		 Г 3  Г 2  Г 1	Г 4  Г
		 УФФФФХФФФФХФФФФХФФФФД	     (who says ascii sucks?)
		 Г 6  Г 6  Г 2	Г 2  Г
		 УФФФФХФФФФХФФФФХФФФФД
		 Г 5  Г 5  Г 8	Г 3  Г
		 РФФФФСФФФФСФФФФСФФФФй

The numbers represent the heights of each unit, our job is to find the longest path Willie can take steping only to units which are either of the same height as the current unit or one above or below it and visiting each unit of this longest path only once. In this case, he should start at the '3' (at 0, 1) and then to the '2' to the right, then the '1' to the right, then the '2' below, then the '2' to the right, and then the '3' below that. That is the longest path visiting each square (unit) only once and all squares (units) are either one above or below or the same height as the next.

Anyone who's coded recursive stuff before is already smiling at the ease with which that can be programmed.

What happens when we make a particular move? We are left with the same problem on a smaller scale. What are we trying to do? Try all possible moves to find the longest sequence that satisfy the conditions of the problem.

Let's start with a slightly easier problem to warm up.

Problem: Write a recursive function to work out the some of the first N natural numbers.

To do this problem we'll analyse the first function we wrote, ok, here it is:

void CodeRecursiveFunction(int HowManyTimesCalled)
{
   if(HowManyTimesCalled > 5) return;
   else CodeRecursiveFunction(HowManyTimesCalled + 1);
   return;
}

Let's analyse the code a bit, what does it contain? Firstly, a condition (contained within the if statement) upon which the function will terminate or return. Secondly it calls itself. All this function does is do the equivilant of a for loop the number of times denoted by HowManyTimesCalled.

Here is a summary of something ALL terminating recursive functions have:

(i) A termination condition.
(ii) A call to the function in progress.

Right, so let's do our problem about the sum of the first N natural numbers:

// global variable
int Total = 0;

void FindSum(int HowManyNaturalNumbers)
{
   if(!HowManyNaturalNumbers) return;
   Total += HowManyNaturalNumbers;
   FindSum(HowManyNaturalNumbers - 1);
   return;
}

If we give that function the number 5 it gives us 5 + 4 + 3 + 2 + 1 in the variable Total, admittedly, this could be done more easily with a for loop, but this is function is just for illustration.

Let's observe what happens in detail, first FindSum is called, it adds the value of HowManyNaturalNumbers to Total and the calls itself with HowManyNaturalNumbers - 1, then this new call to FindSum calls FindSum having added total, until the argument is zero, then the latest version of FindSum returns. Then all the others. Compile and run this code as an illustration of what is happening:

int Total = 0;
const int InitialValue = 5;

void FindSum(int HowManyNaturalNumbers)
{
   if(!HowManyNaturalNumbers)
   {
      cout << "FindSum Version " << InitialValue - HowManyNaturalNumbers  + 1
	   << " returned under termination condition and Total is now "
	   << Total << endl;
      return;
   }
   cout << "In FindSum Version " << InitialValue - HowManyNaturalNumbers + 1
	<< " Total is: " << Total << endl;
   Total += HowManyNaturalNumbers;
   FindSum(HowManyNaturalNumbers - 1);
   cout << "FindSum Version " << InitialValue - HowManyNaturalNumbers + 1
	<< " returned\n";
   return;
}

A call to FindSum with InitialValue as the argument yields the output:

In FindSum Version 1 Total is: 0
In FindSum Version 2 Total is: 5
In FindSum Version 3 Total is: 9
In FindSum Version 4 Total is: 12
In FindSum Version 5 Total is: 14
FindSum Version 6 returned under termination condition and Total is now 15
FindSum Version 5 returned
FindSum Version 4 returned
FindSum Version 3 returned
FindSum Version 2 returned
FindSum Version 1 returned

It's all beginning to make sense. Now we'll try and code a function to find the factorial of a number, the factorial of 5, is 5x4x3x2x1 (and is written as 5!)

Problem: Write a recursive function to find the factorial of a number, N.

int Result = 1;

void FindFactorial(int Number)
{
   if(Number == 1) return;
   Result *= Number;
   FindFactorial(Number - 1);
   return;
}

That needs little explaination, I hope, it just multiplies the Result by Number, then Number - 1, then Number - 2, until Number =(=) 1.

Now we can return to the problem at hand, the one about the counters. I'll start a new section for this problem.

Solving this baby

Recall,

Problem: A man called Willie lives on a 4x4 grid, each unit of the grid is raised to a certain height, like in the diagram:

		      кФФФФТФФФФТФФФФТФФФФП
		 Г 1  Г 8  Г 2	Г 4  Г
		 УФФФФХФФФФХФФФФХФФФФД
		 Г 3  Г 2  Г 1	Г 4  Г
		 УФФФФХФФФФХФФФФХФФФФД
		 Г 6  Г 6  Г 2	Г 2  Г
		 УФФФФХФФФФХФФФФХФФФФД
		 Г 5  Г 5  Г 8	Г 3  Г
		 РФФФФСФФФФСФФФФСФФФФй

The numbers represent the heights of each unit, our job is to find the longest path Willie can take steping only to units which are either of the same height as the current unit or one above or below it and visiting each unit of this longest path only once. In this case, he should start at the '3' (at 0, 1) and then do to the '2' to the left, then the '1' to the left, then the '2' below, then the '2' to the right, and then the '3' below that.

All we do is, start a position (0, 1), try going up, down, left and right, then the same when we are there, then again, and again, here's a nice recursive routine:

void Move(int X, int Y, int XDirection, int YDirection)
{
	Visited[X][Y] = TRUE;
	X += XDirection;
	Y += YDirection;
	if(X < 0 || Y < 0 || X > WIDTH || Y > HEIGHT) return;
	if(Visited[X][Y])
	{
		if(Length > MaxLength) MaxLength = Length;
		return;
	}
	Length++;
	if(abs(HeightMap[X][Y] - HeightMap[X + 1][Y]) <= 1) Move(X, Y, +1, 0);
	if(abs(HeightMap[X][Y] - HeightMap[X - 1][Y]) <= 1) Move(X, Y, -1, 0);
	if(abs(HeightMap[X][Y] - HeightMap[X][Y + 1]) <= 1) Move(X, Y, 0, +1);
	if(abs(HeightMap[X][Y] - HeightMap[X][Y - 1]) <= 1) Move(X, Y, 0, -1);
	Visited[X][Y] = FALSE;
	Length--;
	return;
}

Let's see what it does. Ok, firstly, WIDTH and HEIGHT are the width and height of the grid Willie is walking on. HeightMap contains the Heights of the squares and Visited contains which squares we have visited.

What we do is simple, set a square to be visited, try all the possibities from there, then unvisit it and try all the possibilities by moving left first of all, instead of right, then try all those possibilities then try moving down first instead of left or right etc... really simple. Recursion is often described as a divide & conquer algorithm. This illustrates the sheer power of recursion.

A Graphical Application of Recursion And Iterative Algorithms

Another application of recursion is the generation of the Sierpinski Triangle, I use recursion to generate the Sierpinksi Triangular fractal. Here's the code:

void GenerateFractal(int StartBaseXpos, int StartBaseYpos, int Size,
		     int Iterations)
{
   if(Iterations--)
   {
      Line(StartBaseXpos, StartBaseYpos, StartBaseXpos + Size, StartBaseYpos,
	   15);
      Line(StartBaseXpos, StartBaseYpos, (StartBaseXpos + StartBaseXpos +
	   Size) / 2, StartBaseYpos + Size, 15);
      Line(StartBaseXpos + Size, StartBaseYpos, ((StartBaseXpos +
	   StartBaseXpos + Size) / 2), StartBaseYpos + Size, 15);
      GenerateFractal(StartBaseXpos + Size / 4, StartBaseYpos - Size / 2,
		      Size / 2, Iterations);
      GenerateFractal(StartBaseXpos - Size / 4, StartBaseYpos + Size / 2,
		      Size / 2, Iterations);
      GenerateFractal(StartBaseXpos + Size - Size / 4, StartBaseYpos +
		      Size / 2, Size / 2, Iterations);
   }
   return;
}

And that does it, I'm not going to explain all that crap, It is just to show you the power of recursion.

Two kinds of recursion have distinguished themselves:

(i) Code Recursion, when a function calls itself.
(ii) What is called Data Recursion, which is usually got from taking a recursive function and "dismanlting" it.

So, Code recursion is when a function calls itself, Data recursion is a recursive algorithm, where a function doesn't call itself. Data recursive algorithm are often also called iterative algorithms.

Note that all code recursion (recursive algorithms using functions) can be made into data recursive code, i.e. where a function does not call itself, but the algorithm remains recursive. It can be very tricky to switch code from one type to the other.

Conclusion

I hope you enjoyed being introduced to this powerful topic, or revising it, if there is demand I will try and write a few more articles of this kind to show beginners some important coding techniques. That's it from me.

paradox///() { paradox(); }
vivid