What is Recursion?

Hi. I meant to go into this in a bit more detail after using it in some of my scripts. Recursion is a pretty interesting idea and it’s used quite a bit in scripting. I’ll describe it below and then I’ll jump into an example using PowerShell in the next post.

According to Wikipedia;

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other, the nested images that occur are a form of infinite recursion.

In Computer Science and scripting it’s used to define a problem (or to solve a problem) in terms of itself.

An example would be how to define a Russian Doll.  One way to define it would be to use recursion;

A Russian Doll is a doll that contains another, smaller Russian Doll.

In this case there is some end-point where the dolls can’t contain anything smaller because of the restrictions of reality.  In computer-space this restriction doesn’t always apply.

An example would be using a computer to work out a number raised to a power (exponent).  Here’s some pseudo-code;

function Power (Base, Exponent)
{
 if (Exponent=0) return 1;
 Return (Base * Power (Base, Exponent -1);
}

The Power function is defined in terms of itself.  If we wanted to calculate 10 to the power 3 we’d call the function with Power (10, 3) and the following would happen;

• Power is called with Base=10 and Exponent=3
• Exponent doesn’t equal 0 so we skip the first line of the function.
• Power returns 10 * (Power (10, 2).
• Power is called with Base=10 and Exponent=2
• Exponent doesn’t equal 0 so we skip the first line of the function.
• Power returns 10 * (Power (10, 1).
• Power is called with Base=10 and Exponent=1
• Exponent doesn’t equal 0 so we skip the first line of the function.
• Power returns 10 * (Power (10, 0).
• Exponent equals 0 so we return 1.
• We can now return all the values that have been held waiting for each call of Power to return a value;  10 * 10  *  10 * 1
• 1000 is returned.

Another (jokey) example is the dictionary definition of recursion;

Recursion :  See Recursion.

In the next post we’ll look at using PowerShell and recursion to calculate the size of a folder.