• The basic definition of a recursive function can be given as below:

A function that calls itself is known as recursive function and the process in which a function calls itself is known as recursion.

Example of Recursion in C programming

  • To understand the concept of recursion consider the following program calculating sum of first n natural numbers using recursion.
  • Note: Positive integers are known as natural number i.e. 1, 2, 3….n
/* C program to calculate sum of first n natural numbrs.*/
 
#include "stdio.h"
int sum(int n);      // function prototype
void main()
{
    int num,add;
    printf("Enter a positive integer:\n");
    scanf("%d",&num);

    add=sum(num);       // function call
    
    printf("sum=%d",add);
}

/* Recursive function definition */
int sum(int n)    
{
    if(n==0)      /* condition to break recursion */
       return n;
    else
       return n + sum(n-1);    /* recursive call to function sum() */
}

Output:

Enter a positive integer:
5
15
  • In, the above program, sum() function is invoked from within the same function.
  • If n is not equal to 0 then, the function calls itself passing argument 1 less than the argument it was previously called with.
  • Suppose, n is 5 initially. Then, during next function calls, 4 is passed to function and the value of argument decreases by 1 in each recursive call.
  • When, n becomes equal to 0, the condition for breaking recursion evaluates to true and hence the value of n is returned which is the sum numbers from 5 to 1.
  • The below is the complete recursion calls for better visualization of recursion process:
sum(5)        // initial call to sum() function

=5+sum(4)

=5+4+sum(3)

=5+4+3+sum(2)

=5+4+3+2+sum(1)

=5+4+3+2+1+sum(0)

=5+4+3+2+1+0

=5+4+3+2+1

=5+4+3+3

=5+4+6

=5+10

=15
  • Note that there must be some way to end the recursion. In this example when, n is equal to 0, there is no recursive call and recursion ends.

Advantages

  • Recursion is more powerful and requires few variables which make program clean.
  • It can be used to replace complex nesting code by dividing the problem into same problem of its sub-type.
  • Recursion   can replace large program logic with a few line of code and thus, helps to reduce program code.

 Disadvantages

  • The major difficulty with recursion is that it is hard to think the logic of a recursive function.
  • It is also difficult to debug the code containing recursion.

Comparison of Recursion and iteration

Recursion Iteration
Recursion is the term given to the mechanism of defining a set or procedure in terms of itself. Iteration is the block of statement executed
repeatedly using loops.
A conditional statement is required in the body
of the function for stopping the function execution
The iteration control statement itself contains statement for stopping the iteration. At every execution, the condition is checked.
At some places, use of recursion generates extra overhead. so its better to skip when easy solution is available with iteration. All problems can be solved with iteration.
Recursion is expensive in terms of speed and
memory.
Iteration does not create any overhead. All the
programming languages support iteration.
  • While using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go in infinite loop.
  • Recursive function are very useful to solve many mathematical problems like calculating factorial of a number, generating Fibonacci series, etc