Recursion

From TRCCompSci - AQA Computer Science
Revision as of 08:57, 4 January 2017 by Admin (talk | contribs)
Jump to: navigation, search

Basics of recursion

Recursion 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

General Case

Recursion & the 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.