Lesson 11 - Recursion

Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C++, this takes the form of a function that calls itself. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to "repeat the process". This makes it sound very similar to a loop because it repeats the same code, and in some ways it is similar to looping. On the other hand, recursion makes it easier to express ideas in which the result of the recursive call is necessary to complete the task. Of course, it must be possible for the "process" to sometimes be completed without the recursive call.

Recursive functions appear to be an infinite loop, however in practice we check to see if a certain condition is true and in that case exit (return from) the function. The case in which we end our recursion is called a base case . Additionally, just as in a loop, we must change some value and incrementally advance closer to our base case.

void myFunction( uint32_t counter )
{
  if ( counter == 0 ) return; // base case
  myFunction( --counter );
  return;

}

Properties of Recursive Functions

We use recursion when a problem can be reduced to a simpler problem that can be solved after further reduction. Every recursion should have the following characteristics:

• A simple base case which we have a solution for and a return value. Sometimes there are more than one base cases.
• A way of getting our problem closer to the base case. I.e. a way to chop out part of the problem to get a somewhat simpler problem.
• A recursive call which passes the simpler problem back into the function.

The key to thinking recursively is to see the solution to the problem as a smaller version of the same problem. The key to solving recursive programming requirements is to imagine that your function does what its name says it does, even before you have actually finish writing it.

Identify the base case(s) and what the base case(s) do. A base case is the simplest possible problem (or case) your function could be passed. Return the correct value for the base case. Your recursive function will then be comprised of an if-else statement where the base case returns one value and the non-base case(s) recursively call(s) the same function with a smaller parameter or set of data. Thus you decompose your problem into two parts:

• The simplest possible case which you can answer (and return for)
• All other more complex cases which you will solve by returning the result of a second calling of your function.

This second calling of your function (recursion) will pass on the complex problem but reduced by one increment. This decomposition of the problem will actually be a complete, accurate solution for the problem for all cases other than the base case. Thus, the code of the function actually has the solution on the first recursion.

Consider writing a function to find the factorial of an integer. For example 7! equals 7*6*5*4*3*2*1. But we are also correct if we say 7! is equal to 7*6!.

In seeing the factorial of 7 in this second way we have gained a valuable insight. We have expressed our problem in terms of a simpler version of the problem and we even know how to make our problem progressively more simple. We have also defined our problem in terms of itself. I.e. we defined 7! in terms of 6!. This is the essence of recursive problem solving. Now all we have left to do is decide what the base case is. 1! equals 1.

uint32_t factorial( uint32_t integer )
{
  if ( integer <= 1 ) return 1;
  return ( integer * factorial( integer - 1 ) );
}

Note:

• Always write the base case in the function as the first statement.
• Forgetting the base case leads to infinite recursion.

Downsides

The program may fail due to stack overflow when using some forms of recursion (head recursion).

The other main problem with recursion is that it can be slower to run than simple iteration. There is always an iterative solution to any problem that can be solved recursively.

The recursive version is usually less efficient because of having to push and pop recursions on and off the run-time stack, so iteration is quicker. On the other hand, you might notice that the recursive versions use fewer or no local variables.

So why use recursion? The answer is predominantly because it is easier to code a recursive solution once one is able to identify that solution. The recursive code is usually smaller, more concise, more elegant, possibly even easier to understand. There are some problems that are very difficult to solve without recursion. Those problems that require backtracking such as searching a maze for a path to an exit or tree based operations are best solved recursively. There are also some interesting sorting algorithms that use recursion.

Tail Recursion

Tail recursion is defined as occurring when the recursive call is at the end of the recursive instruction. This is not the case with the factorial solution above. It is useful to notice when one algorithm uses tail recursion because in such a case, the algorithm can usually be rewritten to use iteration instead. In fact, the compiler will (or at least should depending on optimisation setting etc.) convert the recursive program into an iterative one. This eliminates the potential problem of stack overflow.

This is not the case with head recursion, or when the function calls itself recursively in different places. Of course, even in these cases we could also remove recursion by using our own stack and essentially simulating how recursion would work.

In factorial above the compiler will have to call the recursive function before doing the multiplication because it has to resolve the (return) value of the function before it can complete the multiplication. So the order of execution will be "head" recursion, i.e. recursion occurs before other operations.

To convert this to tail recursion we need to get all the multiplication finished and resolved before recursively calling the function. We need to force the order of operation so that we are not waiting on multiplication before returning. If we do this the stack frame can be freed up.

uint32_t factorial( uint32_t number )
{
  if ( number == 0 ) return 1;
  return factorial_i( number, 1 );
}

uint32_t factorial_i( uint32_t number, uint32_t sum )
{
  if ( number == 1 ) return sum;
  return factorial_i( number - 1, sum * number );
}

Notice that in the call return factorial_i( number - 1, sum * number ); both parameters are immediately resolvable. We can compute what each parameter is without waiting for a recursive function call to return. This is not the case with the previous version of factorial. This streamlining enables the compiler to minimise stack use as explained above.

Types of Recursion

• Tail Recursion: A call is tail-recursive if nothing has to be done after the call returns. I.e. when the call returns, the returned value is immediately returned from the calling function. More simply, tail recursion is when the recursive call is the last statement in the function.
• Head Recursion: A call is head-recursive when the first statement of the function is the recursive call.
• Middle or Multi Recursion: A call is mid-recursive when the recursive call occurs in the middle of the function. I.e. there are other statements before and after the recursive call. If one or more of these statements is another recursive call, then the function is multi-recursive. There is no essential difference between Head Recursion, Middle Recursion and Multi Recursion from the standpoint of efficiency and algorithm theory.
• Mutual Recursion: Function X and Y are called mutually recursive if function X calls function Y and function Y in turn calls function X. This is also called indirect recursion because the recursion occurs in two steps instead of directly.