Recursive functions in C/C++

Question

If we consider recursive function in C/C++, are they useful in any way? Where exactly they are used mostly? Are there any advantages in terms of memory by using recursive functions?

Edit: is the recursion better or using a while loop?

Answer 1

Recursive functions are primarily used for ease of designing algorithms. For example you need to traverse a directory tree recursively - its depth it limited, so you're quite likely to never face anything like too deep recursion and consequent stack overflow, but writing a tree traversal recursively is soo much easier, then doing the same in iterative manner.

In most cases recursive functions don't save memory compared to iterative solutions. Even worse they consume stack memory which is relatively scarse.

Answer 2

they have many uses and some things become very difficult to impossible without them. iterating trees for instance.

Answer 3

When using recursion, you can store data on the stack (effectively, in the calling contexts of all the functions above the current instance) that you would have instead to store in the heap with dynamic allocation if you were trying to do the same thing with a while loop. Think of most divide-and-conquer algorithms where there are two things to do on each call (that is, one of the calls is not tail-recursive).

And with respect to Tom's interesting comment/subquestion, this advantage of recursive functions is maybe particularly noticeable in C where the management of dynamic memory is so basic. But that doesn't make it very specific to C.

Answer 4

There are two reasons I see for using recursion:

• an algorithm operates on recursive data structures (like e.g. a tree)
• an algorithm is of recursive nature (often happens for mathematical problems as recursion often offers beautiful solutions)

Handle recursion with care as there is always the danger of infinite recursion.

Answer 5

Dynamic programming is a key area where recursion is crucial, though it goes beyond that (remembering sub-answers can give drastic performance improvements). Algorithms are where recursion is normally used, rather than typical day to day coding. It's more a computer-science concept than a programming one.

Answer 6

Recursive functions make it easier to code solutions that have a recurrence relation.

For instance the factorial function has a recurrence relation:

 factorial(0) = 1
 factorial(n) = n * factorial(n-1)

Below I have implemented factorial using recursion and looping.

The recursive version and recurrence relation defined above look similar and is hence easier to read.

Recursive:

double factorial ( int n )
{
 return ( n ? n * factorial ( n-1 ) : 1 );
}

Looping:

double factorial ( int n )
{
 double result = 1;
 while ( n > 1 )
 {
  result = result * n;
  n--;
 }
 return result;
}

One more thing:

The recursive version of factorial includes a tail call to itself and can be tail-call optimized. This brings the space complexity of recursive factorial down to the space complexity of the iterative factorial.

Answer 7

Implement QuickSort with and without using recursion, then you can tell by yourself if it's useful or not.

Answer 8

Recursion definitively has advantages at problems with a recursive nature. Other posters named some of them.

To use the capability of C for recursion definitively has advantages in memory management. When you try to avoid recursion, most of the time an own stack or other dynamic data type is used to break the problem. This involves dynamic memory management in C/C++. Dynamic memory management is costly and errorprone!

You can't beat the stack

On the other hand, when you just use the stack and use recursion with local variables -- the memory management is just simple and the stack is most of the time more time-efficient then all the memory management you can do by yourself or with plain C/C++ memory-management. The reason is that the system stack is such a simple and convenient data structure with low overhead and it is implemented using special processor operations that are optimized for this work. Believe me, you can't beat that, since compilers, operation systems and processors are optimized for stack manipulations for decades!

PS: Also the stack does not become fragmented, like heap memory does easily. This way it is also possible to save memory by using the stack / recursion.

Answer 9

I often find recursive algorithms easier to understand because they involve less mutable state. Consider the algorithm for determining the greatest common divisor of two numbers.

unsigned greatest_common_divisor_iter(unsigned x, unsigned y)
{
    while (y != 0)
    {
        unsigned temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

unsigned greatest_common_divisor(unsigned x, unsigned y)
{
    return y == 0 ? x : greatest_common_divisor(y, x % y);
}

There is too much renaming going on in the iterative version for my taste. In the recursive version, everything is immutable, so you could even make x and y const if you liked.

Answer 10

One thing that is worth mentioning is that in most functional languages (Scheme for example), you can take advantage of tail call optimizations, and thus you can use recursive functions without increasing the amount of memory in your stack.

Basically, complex recursive tail calls can runs flawlessly in Scheme while in C/C++ the same ones will create a stack overflow.