Programming - Fortress Productions

This section is targeted toward experienced programmers who would like to learn how to write programs with optimal efficiency. The basic concepts and elementals of the languages presented here are beyond the scope of this guide. If you'd like to learn Z80 Assembly, click here. If you'd like to learn TI-83 Plus BASIC, refer to chapter 16 of the TI-83 Plus guidebook.

Programming is a fun and educational concept. If you plan on being a professional programmer, you will need to master a concept called efficiency. Efficiency involves two things - memory and time.

For easy reference, you can use these links to jump to a specific topic on this page:

Note on Recursion

Recursion is a very efficient yet sophisticated concept. Depsite how efficient it is, if used improperly, it can be potentially damaging. Please be sure to carefully read how to use recursion before attempting to use it in your programs.

What is Recursion?

A recursive function is a function that calls itself. Recursion is a much more efficient alternative to conventional methods. Conventionally, functions are written iteratively, repeating a process until a specific condition is met. It would be more efficient, however, to do the same thing, except recursively. By framing the process recursively, you are putting it in terms of a simpler case of itself.

When to use Recursion

Recursion is used whenever you need to repeat a process until a certain conition is true. For an example, if you wanted to write a function that would calculate the factorial of a number, you would need to make it loop, multiplying the number by each number between it and 1. So the number starts off by being multiplied by itself, and the final condition is when it is multiplied by 1. In other words, recursion is a much more efficient alternative to a for, do, or while loop.

So if you have a function that does nothing but a single loop, chances are that it could be rewritten recursively.

General Form of Simple Recursive Functions

Simple recursive functions that have no specific return type are generally written like this:

void RecursiveFunc( ... )

{

if (terminating condition)

Output some values

else

{

Perform some action

RecursiveFunc( ... );

}

}

NOTES:

The termination condition is called the base case. It typically occurs for the simplest case of the problem, such as when an integer has a value of 0 or 1. Other examples of base cases are when some terminating character is encountered, or an end-of-file is reached.
In the else part of this framework, Perform some action and RecursiveFunc can sometimes be interchanged without altering the net effect of the algorithm. What changes is the order of executing statements. This can sometimes be significant, or even disastrous.

Example 1

void Drawline(int n)

{

if (n==0)

cout << "That's all, folks!" << endl;

else

{

for (int i=1; i<=n; i++)

cout << '*';

cout << endl;

Drawline(n-1);

}

}

The function call Drawline(3) will produce this output:

***

**

*

That's all, folks!

NOTES:

A function that has no pending statements following the recursive call is an example of tail recursion. Function Drawline is such a case.
The base case in the Drawline example is n==0. Notice that each subsequent call, Drawline(n-1), makes progresses toward termination of the function. If your function has no base case, or if you never reach the base case, you will create infinite recursion. This is a catastrophic error that will cause your computer to eventually run out of memory and give you heart-stopping messages like STACK OVERFLOW or SEGMENTATION FAULT (CORE DUMPED).

Example 2

// illistrates inifinite recursion

void Catastrophe(int n)

{

cout << n << endl;

Catastrophe(n+1);

}

Try running the case Catastrophe(1) if you have lots of time to waste!

How to Write Recursive Functions

In order to write a recursive function, you need to frame the process that is to be performed. A good stradegy is to start off by stating the algorithm recursively in words or pictures.
For an example, let's write a function that calculates that factorial of a number. First, let's state how the algorithm will work:

n! defined iteratively n! defined recursively

0! = 1
0! = 1

1! = (1)
1! = (1)(0!)

2! = (2)(1)
2! = (2)(1!)

3! = (3)(2)(1)
3! = (3)(2!)

4! = (4)(3)(2)(1)
4! = (4)(3!)

...
...

Based on the conditions stated above, we can write this algorithm for factorial n!:

It should be easy to see why using recursion would be so much more efficient.
Now that we have the algorithm written, let's provide some code that will use the algorithm. To keep things simple, we will be using C++ to write the program. Here's how it will turn out:

// Factorial - returns n!
// long int is used to avoid integer overflow.
// Precondition: n >= 0
long int factorial(int n)
{
if (n==0)
return 1;
else
return factorial(n-1);

}
You could just use if (n>0) instead of else, but it will not make a difference since n is always greater than or equal to 0.

Source: Barron's How to Prepare for the AP Computer Science Advanced Placement Examination

Learn how to optimize your programs, maintain efficiency, and even learn about some of the most sophisticated concepts in the world of programming.

Choose from these Chess topics:

Select a platform that you would like to download software for: