Topic : Recursive Functions
Author : Learntoprogram.com
Page : 1

A recursive function is a function that calls itself. Algorithms that use recursive functions tend to break the problem down in to a solved part and a smaller problem of the same type. Normally there is also a 'base case'. The base case is the simplest of these smaller problems and usually it can be solved directly. Some of the algorithms you've already seen lend themselves naturally to this type of solution.

The mathematical function factorial is naturally recursive. To work out the factorial of a number you multiply it be the number below it and then by the number below that until you reach 1. So, for example, 3! is equal to 3x2x1. If you look at the function you will notice that n! = n.(n-1)! This gives us a nice way to write a factorial function in C++. The base case is 1! which is always 1. So the function is:
long factorial (int n)
{
   if(n==1)
      return 1;
   else
      return n * factorial(n-1);
}


When writing a recursive function make sure that you have a base case and that each time the function is actually doing some useful work to get you to that base case or the recursion will never end. It is quite easy to write recursive functions that never end (that are in effect infinite loops).

The most efficient sorting algorithms that I'm going to give you in this tutorial are actually recursive. So make sure you understand how these work.

To let you see another recursive algorithm I'll write a recursive sum function.
int sum(int *a, int start, int end)
{
   if(start==end)
      return a[end];
   else
      return a[start] + sum(a, start+1, end);
}


Page : 1