Recursion in C-programming

0
14

A recursive function is a function that calls itself either directly or indirectly through another function. Recursive function calling is often the simplest method to encode specific types of situations where the operation to be encoded can be eventually simplified into a series of more basic operations of the same type as the original complex operation.

This is especially true of certain types of mathematical functions. For example to evaluate the factorial of a number, n

n! = n * n-1 * n-2 * ...  * 3 * 2 * 1.

We can simplify this operation into

n! =  n * (n-1)!

where the original problem has been reduced in complexity slightly. We continue this process until we get the problem down to a task that may be solved directly, in this case as far as evaluating the factorial of 1 which is simply 1.

So a recursive function to evaluate the factorial of a number will simply keep calling itself until the argument is 1. All of the previous (n-1) recursive calls will still be active waiting until the simplest problem is solved before the more complex intermediate steps can be built back up giving the final solution.

Program to evaluate the factorial of a number using recursion.

#include <stdio.h>
short factorial( short ) ;
void main()
{
short i ;
printf(“Enter an integer and i will try to calculate its factorial : “ ) ;
scanf( “%d”, &i ) ;
printf( “\n\nThe factorial of %d, %d! is %d\n”, i, i, factorial( i ) ) ;	
}
	
short factorial( short num ) 
{
if ( num <= 1 ) 
return 1 ;
else 
return ( num * factorial( num - 1 ) ) ;
}

This program will not work very well as is because the values of factorials grow very large very quickly. For example the value of 8! is 40320 which is too large to be held in a short so integer overflow will occur when the value entered is greater than 7. Can you offer a solution to this?

While admittedly simple to encode in certain situations programs with recursive functions can be slower than those without because there is a time delay in actually calling the function and passing parameters to it.

There is also a memory penalty involved. If a large number of recursive calls are needed this means that there are that many functions active at that time which may exhaust the machine’s memory resources. Each one of these function calls has to maintain its own set of parameters on the program stack.

You can also read Operator Associativity Here

LEAVE A REPLY

Please enter your comment!
Please enter your name here