What is Meant by Recursion in C and How Recursion Works in C

C Recursion – Recursive Function in C With Examples

Recursion in C is the procedure that is created when a function calls a duplicate of itself to work on a smaller issue. Recursive functions, which include all functions that call themselves, are also known as recursive calls. Numerous recursive calls are made during recursion. It’s crucial to impose a recursion termination condition, though. Although iterative code is longer, recursive code is more complex to understand.

C program on recursion is not applicable to all problems, but it works best for those that can be broken down into related subtasks. Recursion can be used to solve problems with sorting, searching, and traversal, for instance.

Due to function call overhead, iterative solutions are typically more effective than recursive ones. Iterative solutions can be used to any problem that can be solved recursively. The Tower of Hanoi, the Fibonacci series, factorial finding, etc. are only a few examples of problems that are best handled through recursion.

You must test the C Language code provided in this lesson in your code editor to validate it. However, if you prefer to execute this code online, we also provide a free C Online Compiler for testing your C Language code.

What is Recursion in C?

Recursion in C is the process of a function calling a copy of itself. To put it briefly, recursion is the process of a function calling itself. Additionally, the function is a recursive function.

When utilizing recursion in your software, you must be more cautious. Simply said, you can’t use recursion for every issue because it will make your program more challenging and complex.

Sorting, searching, and traversal issues are examples of related subtasks where recursion can be applied. You must specify an exit condition on that function when using recursion; otherwise, it will enter an infinite loop.

Syntax of recursive function in C

void recursion()
{
   *************
    recursion();
   *************
}
int main()
{
   *************
   recursion();
   *************
}

How Recursion Works in C?

Here is a diagram showing how recursion operates:

FLOWCHART OF RECURSION IN C

Example 1: Infinite loop through recursive function

#include<stdio.h>
int main()
{
  printf("C programming Tutorial: Infinite loop through Recursive Function!\n");
  main();
  return 0;
}

Output of the above example!

C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!
C programming Tutorial: Infinite loop through Recursive Function!

The example given above will produce an endless loop. By invoking main() from main in the program mentioned above, we are performing recursion (). Additionally, we did not set any requirements for the program to end. Because of this, the output will print indefinitely.

You can try to test here the example above!

Types of Recursion in C

The C programming language supports two different types of recursion.

  • Direct Recursion
  • Indirect Recursion

Direct Recursion in C

Direct recursive functions are those that make direct calls to themselves.

Example 2: Direct Recursive function in C

int fib(int number)
{
    if (number==1 || number==2)
        return 1;
    else
        return (fib(number-1)+fib(number-2));
}

The fib() method is directly recursive in the case above. because the fib() method is directly called by the statements inside of it.

Indirect Recursion in C

An indirect recursive function is one that does not explicitly call itself before calling another function.

Example 3: Indirect Recursive function in C

int recursive_function(int number)
{
    if (number<=2)
        return 2;
    else
        return newRecursive(number);
}
int newRecursive(int number)
{
    return recursive_function(number);
}

recursive_function() in the example above invokes the newRecursive(), which is a brand-new function. The recursive_function() is then called by this newRecursive(). The function is hence indirect recursive.

Example 4: Finding factorial of a given number

#include <stdio.h>  
int factorial(int);  
int main()  
{  
  int number=5,fact;  
  printf("C Programming Tutorial: Factorial of a number using recursion!\n\n");  
  fact = factorial(number);  
  printf("Factorial of %d is: %d\n",number,fact);  
}  
int factorial(int number)  
{  
if (number==0)  
{  
return 0;  
}  
else if (number==1)  
{  
return 1;  
}  
else   
{  
return number*factorial(number-1);  
}  
}

Output of the above example!

C Programming Tutorial: Factorial of a number using recursion!
Factorial of 5 is: 120

You can try to test here the example above!

What is Recursive Function in C

Recursive functions in C carry out tasks by breaking them down into smaller ones. The function has a defined termination condition, which is met by a certain subtask. The recursion ends at this point, and the function returns the ultimate outcome.

The base case is the circumstance in which the function does not recur; in contrast, the recursive case is the circumstance in which the function repeatedly invokes itself to carry out a subtask. It is possible to write all recursive functions in this style.

The following pseudocode can be used to write any recursive function.

if (example_recursive)  
{  
    return some_value;  
}  
else if (test_for_another_recursive)  
{  
    return some_another_recursive;  
}  
else  
{  
    // Statements;  
    recursive call;  
}  

Recursion in C Examples

Here is an illustration of how to determine the nth term in the Fibonacci series.

#include<stdio.h>  
int fibonacci(int);  
void main ()  
{  
    int x,y;  
    printf("Enter the value of n?");  
    scanf("%d",&x);  
    y = fibonacci(x);  
    printf("%d",y);  
}  
int fibonacci (int x)  
{  
    if (x==0)  
    {  
    return 0;  
    }  
    else if (x == 1)  
    {  
        return 1;   
    }  
    else  
    {  
        return fibonacci(x-1)+fibonacci(x-2);  
    }  
}  

Output of the above example!

Enter the value of n? 12
144

You can try to test here the example above!

Memory allocation of Recursive method

That method is duplicated in memory with each recursive call. The copy is erased from memory after the procedure returns some data.

A distinct stack is kept for each recursive call since all variables and other items defined inside functions are saved in the stack. The stack is deleted after the associated function returns its value.

Resolving and tracking the values at each recursive call requires a great deal of complexity in recursion. As a result, we must keep the stack up to date and monitor the values of the variables it contains.

To comprehend how recursive functions allocate memory, let’s look at the example below.

int display (int x)  
{  
    if(x == 0)  
        return 0; // terminating condition  
    else   
    {  
        printf("%d",x);  
        return display(x-1); // recursive call  
    }  
}  

For x = 4, let’s explore this recursive function. Prior to n becoming 0, all stacks are maintained, printing the matching value of n. When the termination condition is met, each stack is destroyed individually by returning 0 to its calling stack. Take a look at the following illustration for more details on the stack trace for the recursive routines.

Advantages of Recursion in C

  • creates an attractive program.
  • The program code becomes more understandable, and the writing of the code takes less time.
  • eases the intricacy of time.
  • For challenges based on tree architectures, it works well.

Disadvantages of Recursion in C

  • Due to the expense of maintaining the stack, it runs slower than non-recursive programs.
  • For the stack, additional RAM is needed.
  • Instead of recursion, utilize loops for greater speed. so recursion moves more slowly.

Significance of Recursion in C

Because recursion helps make C programs short and simple, programmers frequently utilize it in their work. Additionally, it makes the code easier to read.

The run-time of the program code is also decreased with the aid of recursion. However, iteration is another option that offers functionality that is significantly faster than recursion.

Recursion in C is a powerful tool for solving a variety of issues. Recursion can be used to quickly handle a variety of issues, including the factorial of a number, fibonacci series in a specific range, tree algorithm issues, and more.

Difference between tailed and non-tailed recursion in C

A recursive function is referred to be tail-recursive if the recursive call is the final operation carried out by the function. If not, it is referred to as a non-tailed recursion.

Summary

We studied recursion and recursive functions in this course. Recursion’s benefits and drawbacks were also covered. The several C recursion types were also covered.

About Next Tutorial

In the next following post, I’ll create a Variable Arguments in C and try to explain its many components in full details. I hope you enjoy this post on C Recursion – Recursive Function in C With Examples, in which I attempt to illustrate the language’s core grammar.


Leave a Comment