A program is called recursive when an entity calls itself while a program is called iterative when there is a loop or repetition.

Recursive function means a function calling itself till it reaches a base condition also known as halt condition.

Emphasis on iteration:

Repeat execution of some lines of instruction until the task is done. Please refer iteration section for more details.(for loop, while loop, do-while loop)

Emphasis on recursion:

The problem is divided into small sub-problems(divide and conquer) until we reach the trivial version of the problem that is the base condition.

Example:

Program to get factorial of a number using recursion

#include <stdio.h>

int fact( int n)
{
   if ( n >=1)
     return n * fact (n-1);
   else 
     return 1;
}

int main()
{
  int fact_no = 3;
  int result = fact(fact_no);
  printf("\n The result is: %d\n", result);
  return 0;
 }

 Output:
 The result is: 6

In the above example, the fact() function is called from main() function with the value of 3. Inside the fact() function, the function fact(2), fact(1) and fact(0) are called recursively.

In this program execution process, the function call fact(3) remains under execution till the execution of function fact(2),fact(1) and fact(0) gets completed. Similarly, the function call fact(2) remains under execution until the execution of function calls fact(1) and fact(0) gets completed. In the same way the function call fact(1) remains under execution till the execution of function calls fact(0) gets completed. The complete flow is depicted below.

Program to get factorial of a number without recursion

#include <stdio.h>

int main()
{
  int fact_no =6;
  int ret =1;
  while (fact_no >=1)
  {
     ret = ret * fact_no;
     fact_no = fact_no -1;
   }
   printf("\n The result is %d\n", ret);
   return 0;
 } 

 output:
 The result is 720

Two key points to consider while using recursive functions are:

• They are slower as for each function call the compiler needs to maintain an activation record (properties of the caller function on the stack) and again needs to restore the old context.
• Finding the base condition otherwise, the function will keep calling itself and there is a serious problem called stack overflow.

Types of recursion:

There are two types of recursion:

• Head Recursion: If the recursive function instructions are at the start of the program.
• Tail Recursion: If the recursive function instructions are at the end of the program.

Relevant Posts:

• Functions in C
• Types of function
• Parameter passing: call-by-vale and call-by-reference
• Memory layout of C program

Categories: C Language