Recursion

From TRCCompSci - AQA Computer Science
Revision as of 09:12, 16 May 2017 by Cameron (talk | contribs) (General Case)
Jump to: navigation, search

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.

Base Case

In the base case, the routine does not call itself. But, when a routine does have to call itself in order to complete its sub-task, then that is known as the recursive case. So, there are 2 types of cases when using a recursive algorithm: base cases and recursive cases.

General Case

Recursively using a stack

Example

 
using System;

class Program
{
    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.