Recursion

Basics of recursion

Recursion(the page is calling itself - get it?) is an important programming technique that causes a function to call itself. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method. Recursion and iteration (looping) are strongly related—a function can return the same results either with recursion or iteration. Usually, a particular computation will lend itself to one technique or the other, and you simply choose the most natural or preferable approach.

https://www.youtube.com/watch?v=NlJfb11wzC8&index=5&list=PLCiOXwirraUDd7mhZFyNFCPPwWzCAyh4w

Base Case

In the base case, the routine does not call itself. Each recursive algorithm must have a criteria to end the recursion, otherwise it would run indefinitely. This criteria is what causes the base case.

in the example below the base case is:

	if (value >= 10)
	{
	    // throw new Exception("End");
	    return value;
	}

General Case

This is the bit of code which calls itself.

In the example below this will be:

return Recursive(value + 1, ref count);

Recursively using a stack

The stack is a Last In First Out structure, and each time a recursive call is made a stack frame is created.

A stack frame will include the variable states, environment info, etc. This essentially stores everything required to return to this exact position in the running of the program.

The Last In First Out nature of the static means that once the base case as been meet the recursion will unravel itself.

Example

 
static int Recursive(int value, ref int count)
{
	count++;
	if (value >= 10)
	{
	    // throw new Exception("End");
	    return value;
	}
	return Recursive(value + 1, ref count);
}

static void Main()
{
	//
	// Call recursive method with two parameters.
	//
	int count = 0;
	int total = Recursive(5, ref count);
	//
	// Write the result from the method calls and also the call count.
	//
	Console.WriteLine(total);
	Console.WriteLine(count);
}

Output

10 Total value of 10 was added up.
6 Six method calls.