We have previously learnt the process of iteration by using for, while and do-while loops. Such iterations or loops can even be created using functions which we call recursive. In this article, we're going to know about Recursion in C.

Recursive Functions in C
Recursive Functions in C

Overview:


What is Recursion?

Recursion is a process where a function calls itself repeatedly either directly or indirectly. Such functions that carry out the process of recursion are called recursive functions. C supports recursion, i.e., a self-calling function. However, programmers must pay attention to prescribe an exit condition from the function, else the program will execute itself to eternity.

Recursive functions are very useful in solving mathematical problems, like finding the factorial of a number, generating a Fibonacci series, and a lot more.



Types of Recursion

Based on the path of calling function, recursion can be classified into different types. Before moving into the types of recursion, let us understand the following example:

If a function f1() calls itself from its own body, it is called recursive. Again, if a function f1() calls another function f2() that again redirects to f1() in the end, then that too can be considered a recursive function.

So let's point down types of recursions:
  1. Linear Recursion
  2. Tail Recursion
  3. Binary Recursion
  4. Multiple Recursion

Linear Recursion:

When a function is invoked in linear recursion, the self-calling is made exactly once. Such recursion allows the size of function to grow in a linear proportion wrt size of the program.

#include<stdio.h>
#define SIZE 10 
int recursiveMax(int *,int);
int max(int,int);
int main()
{
    int arr[SIZE]={1,3,5,4,7,19,6,11,10,2};
    int max=recursiveMax(arr,SIZE);
    printf("Maximum element among array items is: %d\n", max);
}
int recursiveMax(int *arr,int n)
{
    if (n==1)
        return arr[0];
    return max(recursiveMax(arr,n-1),arr[n-1]);
}
/*function to compute max of two decimal integers*/
int max(int n,int m)
{
    if (n>m) 
      return n;
    else
      return m;
}

Output:

Linear Recursion Output
Linear Recursion Output

Tail Recursion:

Just like linear recursion, but the calling is made at the last operation. Also, keep in mind that the last operation and last statement are not identical. If you see at recursiveMax (defined above), then you will find that recursive call to function recursiveMax is the last statement but not last operation, code arr[n-1] yet to be processed to complete the execution of the last statement.

Thus, a tail-recursive function is one where the function call is the last thing the function performs. Any function that uses tail recursion can be converted to non-recursive one, by iterating through the recursive calls instead of calling them explicitly. Reversing array elements is a good example of tail recursion.

#include<stdio.h>
#define SIZE 5
void recursiveRev(int *,int,int);
int main ()
{
    int arr[SIZE]={1,2,3,4,5}; 
    int i;
    recursiveRev(arr,0,SIZE-1);
    printf ("Printing array elements after they are reversed...\n");
    for(i=0;i<SIZE;i++)
        printf("%d\n",arr[i]);
}
void recursiveRev(int *arr,int i,int j)
{
    if(i<j)
    {
        int tmp;
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
        recursiveRev(arr,i+1,j-1);
    }
}

Output:

Tail Recursion Output
Tail Recursion Output

Binary Recursion:

Binary means two units. A function that makes two recursive calls to itself when invoked is a Binary Recursion function. Fibonacci series is a great example to show binary recursion.

#include<stdio.h>
int recursiveFib(int);
int main ()
{
    int n=10;
    printf("%dth fibonacci number is %d\n",n,recursiveFib(n));
}
int recursiveFib(int n)
{
    /*base case*/
    if(n<=1) 
        return n;
    /*binary recursive call*/
    return recursiveFib(n-1)+recursiveFib(n-2);
}

Output:

Binary Recursion Output
Binary Recursion Output

Multiple Recursion:

A generalised form of binary recursion. When a function makes multiple recursive calls (more than two) then it is called multiple recursion.

Conditions of Recursive functions

In recursive program, the solution to base case is provided and solution of bigger problem is expressed in terms of smaller problems.

int fact(int n)
{
    if (n<=1) /*base case*/
        return 1;
    else    
        return n*fact(n-1);    
}

In the above example, base case for n<=1 is defined and larger value of number can be solved by converting to smaller one unless base case is met.

Problem-solving using Recursion

The idea of recursive functions is to represent a problem in terms of one or more smaller problems, and to stop recursion one or more base conditions are added. For example, while computing factorial of n we have to know factorial of (n-1). Base case for factorial would be n=0. The function will return 1 when n=0.

Stack Overflow in Recursive functions

If base case is not reached or not defined, then stack overflow problem may arise. Take a look at following example to understand this:

int fact(int n)
{
    /*wrong base case (might cause stack overflow).*/
    if (n==50) 
        return 1;
    else
        return n*fact(n-1);
}

If fact(20) is called, it will call fact(19), fact(18), fact(17) and so on but number will never reach 50. Thus, the base case is never met. If the memory is exhausted due to these functions on stack, it will result in stack overflow error.



Memory Allocation in Recursive functions

Whenever a recursive function is called in the main() function, memory is allocated to that function on a stack. Every time the recursive function calls itself, memory for the function called is allocated above the function calling and each time a new set of space is allocated for the variables contained in the function body.

Once the condition (base case) is reached, the called function returns its value to the function by whom it is called and memory is de-allocated and the process goes on.

Recursive program vs Iterative program

Let me tell you both recursive, as well as the iterative approach in any program, has almost likely powers. Since the nature of execution in both the approaches remains the same. However, there is a slight difference that goes unnoticed.

In the case of Recursive Approach, until the base condition is met, the functions are stacked as a result of which it consumes a decent amount of space in the memory. Adding to that, a large function will definitely take larger time of execution on calling itself repeatedly.



If you're wondering that Recursive Approach is not profitable then I must mention, the above detail is not all. There are a few advantages of Recursive Functions over Iterations as well.

Recursion needs lesser codes to be written than the iterative version. Recursion codes are cleaner, compact and easy to comprehend.

All programs written in this post are compiled online.

Books I Prefer:



  

I hope this article was helpful to understand recursive functions in C! Comment below, if you've got any question. Head back soon for another interesting article on C Programming.