Recursive function

Recursive programming is a programming technique that replaces loop instructions with function calls. The mechanism consists, in the vast majority of cases, in creating a function which is called itself one or more times according to different criteria.

The structure of a recursive algorithm is as follows:

 algo ()
{
   condition 1
   condition 2
   ...
   condition n
}

The conditions are usually some « if », they include stop conditions (do not return the function) or conditions of continuity (restart the function or return the function). The continuity conditions modify the inputs of the restarted function. A recursive function must have at least one stop condition.

Simple recursion

A simple recursive function is called only one time at most in each condition..

The mathematical program is as following (example for the calculation of a power):

puissance

Here is a simple example to calculate n!:

 int fact(n)
{
   if (n==0) return 1;
   else return n*fact(n-1);
}

Here we see the fact that recursion behaves like a loop.

Multiple recursion

A multiple recursive function can call itself multiple times in each condition.

The mathematical program is as following(example for Pascal’s relation):

pascal

Which gives the following code:

 int pascal(n, p)
{
   if (p==0 || p==n) return 1;
   else return pascal(p, n-1)+pascal(p-1,n-1);
}

Other types

Two algorithms are « mutually » recursive if one uses the other and vice versa.

An algorithm contains a « nested » recursion if a parameter of the recursion is a call to itself.

Stack of execution

The execution stack of the current program is a memory location for storing parameters, local variables, and return addresses of functions that are running.

This stack operates on the LIFO (last in first out) principle and has a fixed size. Here is the stack for the simple factorial, as soon as the program reads a method, it executes it while retaining the rest of the information in the stack, and it adds the new results at the top of the stack. Since it is LIFO, this last information will be read first, which is why it gives an impression of execution pyramid:

Call fact(3)
   3*fact(2)
   Call fact(2)
      2*fact(1)
      Call fact(1)
         1*fact(0)
         Call fact(0)
            Return 1
         Return 1*1
      Return 2*1
   Return 3*2
Return 6

The execution stack of the Fibonacci suite follows the same principle:

int fibo(n)
{
   return (n<2) ? 1 : fibo(n-1)+fibo(n-2);
}
Fibo(3)
   Fibo(2)+wait
   Call Fibo(2)
      Fibo(1)+wait
      Call Fibo(1)
         Return 1
      1+Fibo(0)
      Call Fibo(0)
         Return 1
      Return 1+1
   2+Fibo(1)
   Call Fibo(1)
      Return 1
   Return 2+1
Return 3

We see here a rollercoaster effect due to the successive removal of the function on the left as soon as it is encountered. It is easier to represent the stack of a multiple recursive function by a path in depth (we go further in the successors) of the tree of its recursive calls:

fibo

Terminal recursion

A function is said to be recursively terminal if the result of this call is the result of the function.

Thus, the stack has nothing in memory throughout the recursion. This means that the value returned is directly the value obtained without there being any additional operation. Let’s take the example of the factorial recursively terminal:

 int fact(n,a)
{
   if (n==0) return a;
   else return fact (n-1, n*a);
} // be careful, the value of a at the start is very important

This is exactly like writing the following loop:

 while (n != 0
{
   n*=a;
   n--;
}

 

Publicités