Recursion

The simple definition of a recursive program is one that calls itself. As well as a recursive function is one that is defined in terms of itself. One important part of a recursive program/function is a terminal condition; that is, a condition upon which the program stops calling itself. Without such conditions recursive programs would never stop.

Here is an example of a recursive definition 

n! = n * (n-1)!
1! = 1
As you can see we define factorial of a number through factorial of a smaller number. We also defined the terminal condition. Using this definition, it is easy to design a factorial() function: 
unsigned int factorial(int n)
{
   if( n == 1 ) return 1;
   return n * factorial(n-1);
}

Although it is easy to design such a function, it turns out to be not the most efficient way to compute the factorial. To illustrate the idea of the effectiveness, we consider another recursive example - the Fibonacci numbers. A sequence of Fibonacci numbers is defined by the following rules: 

f1 = 1
f2 = 1
fn = fn-1 + fn-2
We will compare two different implementations of a function that computes Fibonacci numbers: 
unsigned int fibonacci(int n)
{
   if( n < 3 ) return 1;
   return fibonacci(n-1) + fibonacci(n-2);
}

unsigned int fibonacci(int n)
{
   if( n < 3 ) return 1;
   unsigned int fpp = 1, fp = 1, f;
   for(int i=3;i<=n;i++){
      f = fpp + fp;
      fpp = fp;
      fp = f;
   }
   return f;
}
n Recursive Iterative
28 0 0
30 16 0
32 47 0
34 109 0
36 297 0
38 750 0
40 1,938 0
42 5,141 0
44 13,469 0
46 35,235 0
If we try to measure time that is required for these functions to compute a Fibonacci number with index n, we can see that the time required by the recursive version grows tremendously. It turns out, that despite the recursive function looks much easier, it is much more expensive.


N queens problem

We will consider a problem of setting 8 queens on a chess board in such a way that they do not attack each other. The recursion is a good variant of solving such a problem because we need to look over all possible variations and select the one possible.
For example, on this board we cannot put queens on the squares with black dots.

We can first reformulate this problem to make sound like a recursive problem. We say that we need to put one more queen on a chess board (with may be some queens already set). This process is to be stopped when we put all 8 queens or we cannot put the next one. We will design a recursive function put_queen() that takes one integer argument - the number of the queen to set and returns either true (if we can put all 8 queens on the board with previously set queens), or false (if previously set queens do not allow us to put all 8 queens). This function should do the following:

  1. if the number of the queen i to set is equal 8, then return true;
  2. put a queen in the next available square of the i-th column;
  3. mark all squares this new queen attacks;
  4. call put_queen(i+1);
  5. if it returns true, then return true;
  6. if it returns false, then try to find next available square of the i-th column;
  7. if it is possible, then go to step #2, otherwise return false.
Please find the complete example on the example page.

Evaluating an arithmetic expression

Let us try to define what an arithmetic expression is. 

expression ::= number                  |
               expression + expression |
               expression - expression |
               expression * expression |
               expression / expression |
               ( expression )
This is a descriptive definition, but, unfortunately, it doesn't let us easily write a parser of an arithmetic expression. We will try to rewrite the definition splitting it into three recursively connected definitions: 
expression ::= term              |
               term + expression |
               term - expression

term       ::= factor        |
               factor * term |
               factor / term

factor     ::= number         |
               - factor       |
               ( expression )