What are the problems involved in using the recursive functions?

Answer 1

There are no problems when they are used correctly. The main problem is that inexperienced programmer's often assume that a recursive algorithm requires a recursive function when it is not the case at all; most recursive algorithms can be implemented as an iterative loop. However, even when recursion is required, often it is implemented incorrectly.

Consider the recursive algorithm to find the factorial of an unsigned value:

const unsigned factorial (const unsigned n)

{

return n<2?1:n*factorial (n-1);

}

The problem with this is that we are calculating a constant expression at runtime. E.g., the factorial of 5 is always going to be 120. Therefore it makes more sense to calculate the factorial at compile time rather than at runtime.

constexpr unsigned factorial (const unsigned n)

{

return n<2?1:n*factorial (n-1);

}

So, when we write the following:

constexpr unsigned x = factorial (5);

The compiler will automatically generate the following equivalent code for us:

constexpr unsigned x = 120;

In other words, the recursive function is completely optimised away. That's fine when we're dealing with constant expressions, but when we deal with variables we have a problem because there are no variables at compile time:

unsigned y = rand (); /* a random value */

unsigned x = factorial (y);

Now we cannot take advantage of compile time recursion, we must sacrifice runtime performance in order to calculate the factorial of y, whatever y happens to be at runtime.

Thus if y were 5, we incur the following series of function calls:

factorial (5)

factorial (4)

factorial (3)

factorial (2)

factorial (1)

That's 5 function calls in total. Once we reach the exit condition (n<2), the functions unwind to calculate the result:

factorial (1) = 1

factorial (2) = 2*factorial(1) = 2*1 = 2

factorial (3) = 3*factorial(2) = 3*2 = 6

factorial (4) = 4*factorial(3) = 4*6 = 24

factorial (5) = 5*factorial(4) = 5*24 = 120

That's a lot of work that has to be done at runtime.

Now let's look at the iterative solution:

unsigned factorial (unsigned n)

{

unsigned result=1;

while (1<n) result*=n--;

return result;

}

Now we only incur one function call at runtime. We can still use the constant expression version for compile time recursion, but for variables we gain better performance at runtime. Moreover, given the simplicity of the function, the compiler can still optimise away the function call entirely through inline expansion. Thus:

unsigned y = rand (); /* a random value */

const unsigned x = factorial (y);

Becomes the equivalent of:

unsigned y = rand (); /* a random value */

unsigned t1 = y;

unsigned t2 = 1;

while (1<t1) t2*=t1--;

const unsigned x = t2;

We still have to perform the calculation, of course, but we no longer incur the penalty of making any unnecessary function calls. At worst, there will be just one function call and only when expanding the function is not possible (which is unlikely in this case).

So the only time we really need recursion at runtime is when the benefit of inline expansion becomes counter-productive, resulting in runtime code that is overly-complicated. Typical examples are divide-and-conquer algorithms such as the quicksort algorithm where two recursions are necessary. However, when the final call to a function is a recursion, then we can take advantage of tail-call recursion to eliminate the second recursion; we simply modify the variables and re-invoke the current instance of the function rather than invoking a new instance. However, we can only do this when the local variables would not be required when we return from a recursion.