Recursion in C - Example With Explanation

What is recursion ?

C programming language provides a feature known as recursion. Recursion is a process in which a function calls itself.

Rules for using recursion

1. Recursive function must include a terminating condition which will stop the recursion process.
2. Generally a recursive function contains if-else branching. One branch contains recursive calls and other branch contains a terminating condition.
3. Implement the recursive function such that each time the function is called recursively it must be closer to the solution.

Example:

Consider the example where we want to calculate the factorial of a number. We either do multiplication of all numbers from 1 to that number or from that number to 1. For example, if we want to calculate factorial of 5, we first multiply 1 and 2 i.e 1 x 2 = 2 then multiply the result by 3 i.e 2 x 3 = 6 and continue this process until the number comes into multiplication process for which we are calculating the factorial. so this includes this is recursive process.

This recursion can be represented by a statement as

if num=0 or num=1
	num!=1;
else
	num*(num-1)!

Recursive function to find the factorial of number

int factorial(int num)
{
	if(num==0 || num==1) // terminating condition 
		return 1;
	else
		return num*factorial(num-1);
}

Explanation of the recursive function

Suppose num=5. When we enter the function if condition evaluates to false so the control is transferred to else part we try to return product of num and return value of factorial() function for num-1 i.e factorial(5-1) i.e factorial(4). This return is stored into the internal stack of the system. So again we are in the factorial function, the condition is checked which evaluates to false, control is transferred to else part and the return is store again in the stack and factorial(4-1) is called. This process terminates when factorial() function is called with num=1 i.e factorial(2-1).

The return statements are carried out as

return 5*factorial(5-1);
return 4*factorial(4-1);
return 3*factorial(3-1);
return 2*factorial(2-1);
return 1;

Return value of line 5 is replaced at function call in line 4. Return value of line 4 is replaces at function call in line 3. Similarly this process continues until the first (topmost) return statement and the the function returns factorial of a number.