What are the advantages of using a recursive function in c?

Answer 1

Advantages:
Through Recursion one can Solve problems in easy way while
its iterative solution is very big and complex.
Ex : tower of Hanoi
You reduce size of the code when you use recursive call.

Disadvantages :
Recursive solution is always logical and it is very
difficult to trace.(debug and understand)

Before each recursive calls current values of the varibles
in the function is stored in the PCB, ie process control
block and this PCB is pushed in the OS Stack.
So sometimes alot of free memory is require for recursive
solutions.

Remember : whatever could be done through recursion could be
done through iterative way but reverse is not true.

Answer 2

The only advantages to a recursive function is that it makes use of the call stack. However, this is only useful if you can actually make practical use of the call stack in the first place. Many functions that are naturally-recursive in nature can often be implemented with far greater efficiency using an iterative function instead, simply because the need for the call stack is only required for the initial call but is ultimately redundant if the iterative function can be inline expanded (removing the function call altogether).

While it is true that many iterative functions can be implemented recursively and vice versa, it is not true in all cases. Some functions can only be implemented recursively. However, where an iterative method exists, it is often the method of choice.

The best way to describe a recursive function is to liken it to a clockwork spring which is wound up with each recursive call, and unwound whenever a call returns. This spring may wind and unwind several times over before the initial instance is returned to the original caller, which restores the spring to its original unwound state. However, like all clockwork springs, these springs cannot be wound up infinitely. There is some flexibility regarding how much the spring can be wound, but it is ultimately finite. This is known as the depth of recursion and the maximum depth is ultimately determined by the call stack, which is itself limited by available memory. Some recursive functions will have greater depths than others, but the limit is decided by how much stack space is required by the individual function and how much is actually available at the time.

Thus the first deciding factor on whether or not to use recursion is to first determine just how deep the calls need to be. If the depth is fixed (and therefore known at compile time) and relatively shallow, the iterative function might be the better option in terms of performance. However, if the depth is variable or is so great that it becomes impractical to code iteratively, then recursion is usually the better option.

Prior to each recursion, all the non-static local variables are pushed onto the call stack, including all parameters received by the function. When the call returns, they are all popped from the stack, thus restoring them to their original state. Thus every instance of the function has its own discrete set of variables. When deciding whether to use a recursive function, focus upon the variables used by the main process of the function and whether or not those variables are required after making a recursive call. If not, then do not use recursion.

As an example, consider a function that processes the parameters it receives, creating a set of local variables which, if a condition is met, it then passes to itself via a recursive call. If the function returns to the caller whether the recursive call is made or not, then those local variables will simply fall from scope regardless. It therefore makes far more sense to modify the parameters directly and then recall the exact same instance of the function with a goto (known as a tail call). There is no need for a recursive call at all.

Sometimes functions need to call themselves several times from the same instance, especially when implementing divide-and-conquer algorithms (typically found in sorting algorithms). Such functions cannot be implemented without recursion because the depth of recursion cannot be determined in advance and, even if it could, would be impractical to implement with deeply-nested loops. However if the final action is a recursive call then it can pay to use a tail call here as well. Quick sort is a typical example as the basic form requires two recursive calls to sort each of the two subsets generated by the main body of the function. The final call sorts the second of the two subsets but if the function is engineered so that the final call is made upon the larger of the two subsets, then the function becomes that much more efficient by passing that larger subset into the same instance of the function via a tail call. At that point the parameters and variables used by the function are no longer required so there is no need to maintain them on the stack.

A classic example of a naturally recursive function is the factorial function. For any given positive whole number, n, its factorial (denoted n!) is the product of all positive whole numbers less than or equal to n. Thus 5! is 5 x 4 x 3 x 2 x 1 = 120.

To code this function recursively we'd use the following function:

UINT64 factorial_recur( UINT64 u )

{

return( u > 1 ? factorial_recur( u - 1 ) * u : u );

}

To code this same function iteratively, we'd use the following function:

UINT64 factorial_iter( UINT64 u )

{

UINT64 Result = u;

while( --u > 1 )

Result *= u;

return( Result );

}

Note that a UINT64 is a 64-bit unsigned integer, with the following type definition:

typedef unsigned long long UINT64;

On the face of it, the recursive function looks to be the more concise and elegant of the two, but how do they compare? Let's use the following Windows test program to find out using high-performance timers. The test system has a minimum resolution of 1/100th of a microsecond, which is 100 millionth of a second, which is more than sufficient for our needs:

#include

#include

int main()

{

UINT64 x, y, z;

LARGE_INTEGER Freq, Start, Finish;

double Recur, Iter;

QueryPerformanceFrequency( &Freq );

char strFormat[] = "Factorial %I64u\t%s: %.2f microseconds\tAnswer: %I64u\n";

printf( "Print factorials from 1 to 20\n\n" );

for( x = 1; x <= 20; ++x )

{

QueryPerformanceCounter( &Start );

y = factorial_recur( x );

QueryPerformanceCounter( &Finish );

Recur = ( double ) ( Finish.QuadPart - Start.QuadPart ) / Freq.QuadPart;

printf( strFormat, x, "Recursive", Recur * 1000000, y );

QueryPerformanceCounter( &Start );

z = factorial_iter( x );

QueryPerformanceCounter( &Finish );

Iter = ( double ) ( Finish.QuadPart - Start.QuadPart ) / Freq.QuadPart;

printf( strFormat, x, "Iterative", Iter * 1000000, z );

printf( "\n" );

}

return( 0 );

}

Output:

Print factorials from 1 to 20

Factorial 1 Recursive: 1.52 microseconds Answer: 1

Factorial 1 Iterative: 1.20 microseconds Answer: 1

Factorial 2 Recursive: 1.32 microseconds Answer: 2

Factorial 2 Iterative: 1.08 microseconds Answer: 2

Factorial 3 Recursive: 1.12 microseconds Answer: 6

Factorial 3 Iterative: 1.08 microseconds Answer: 6

Factorial 4 Recursive: 1.16 microseconds Answer: 24

Factorial 4 Iterative: 1.08 microseconds Answer: 24

Factorial 5 Recursive: 1.20 microseconds Answer: 120

Factorial 5 Iterative: 1.12 microseconds Answer: 120

Factorial 6 Recursive: 1.20 microseconds Answer: 720

Factorial 6 Iterative: 1.08 microseconds Answer: 720

Factorial 7 Recursive: 1.28 microseconds Answer: 5040

Factorial 7 Iterative: 1.12 microseconds Answer: 5040

Factorial 8 Recursive: 1.40 microseconds Answer: 40320

Factorial 8 Iterative: 1.08 microseconds Answer: 40320

Factorial 9 Recursive: 1.44 microseconds Answer: 362880

Factorial 9 Iterative: 1.12 microseconds Answer: 362880

Factorial 10 Recursive: 1.44 microseconds Answer: 3628800

Factorial 10 Iterative: 1.12 microseconds Answer: 3628800

Factorial 11 Recursive: 1.52 microseconds Answer: 39916800

Factorial 11 Iterative: 1.12 microseconds Answer: 39916800

Factorial 12 Recursive: 1.52 microseconds Answer: 479001600

Factorial 12 Iterative: 1.08 microseconds Answer: 479001600

Factorial 13 Recursive: 1.64 microseconds Answer: 6227020800

Factorial 13 Iterative: 1.12 microseconds Answer: 6227020800

Factorial 14 Recursive: 1.68 microseconds Answer: 87178291200

Factorial 14 Iterative: 1.16 microseconds Answer: 87178291200

Factorial 15 Recursive: 1.72 microseconds Answer: 1307674368000

Factorial 15 Iterative: 1.16 microseconds Answer: 1307674368000

Factorial 16 Recursive: 1.80 microseconds Answer: 20922789888000

Factorial 16 Iterative: 1.16 microseconds Answer: 20922789888000

Factorial 17 Recursive: 1.76 microseconds Answer: 355687428096000

Factorial 17 Iterative: 1.20 microseconds Answer: 355687428096000

Factorial 18 Recursive: 1.88 microseconds Answer: 6402373705728000

Factorial 18 Iterative: 1.36 microseconds Answer: 6402373705728000

Factorial 19 Recursive: 2.12 microseconds Answer: 121645100408832000

Factorial 19 Iterative: 1.24 microseconds Answer: 121645100408832000

Factorial 20 Recursive: 2.12 microseconds Answer: 2432902008176640000

Factorial 20 Iterative: 1.28 microseconds Answer: 2432902008176640000

The timings are a bit wayward at times, however this is due to unavoidable background activity. In proper timing tests we'd repeat the full test millions of times and calculate the averages. However, the results from this single pass alone clearly show the iterative function performs better in every case. At the beginning there's actually very little difference, but by the 20th iteration the iterative function is almost twice as fast as the recursive function.

This stands to reason because the recursive function requires 20 function calls to calculate 20!, whereas the iterative function requires no function calls whatsoever (it can easily be inline expanded). So in this particular case, recursion is not advantageous. However, the mere fact that a relatively simple iterative method exists at all is indicative of this; we do not need the stack and the unavoidable use of the stack simply impedes the performance.

Ultimately, recursive functions are best employed whenever iterative functions would be difficult if not impossible to implement. If the depth of recursion is known in advance and is not overly-deep, then an iterative function will generally perform better than a recursive one, even if the recursive function looks simpler. The downside of iteration is that the same process must be repeated at each depth of nested process, resulting in duplicate code. This can be alleviated with an inline expanded function call, however if the function is so complicated that inline expansion would increase the program size to an unacceptable level (impeding overall performance), then recursion would be a better option, if only to simply the code.

As you gain experience with programming you will more quickly recognise when to use recursion and when to use iteration. If you're not sure, then start with iteration and only revert to recursion when it becomes clear the iterative method is either impossible to implement (because the maximum depth is too high) or would otherwise offer no real advantage over recursion. For simple functions where there is a clear choice, the iterative method is usually better but it still pays to test both in order to see the performance difference and make a more informed decision.