Your One-Stop Solution to Understand Recursive Algorithm in Programming

You will encounter recursive problems in competitive programming. And when you attempt to solve these problems using different programming paradigms, you will first formulate recursive logic for them. In programming, recursive reasoning is extremely essential. It assists you in breaking down large complex problems into smaller ones. Hence, it is used all the time in almost every programming language.

What Is a Recursive Algorithm?

A recursive algorithm calls itself with smaller input values and returns the result for the current input by carrying out basic operations on the returned value for the smaller input. Generally, if a problem can be solved by applying solutions to smaller versions of the same problem, and the smaller versions shrink to readily solvable instances, then the problem can be solved using a recursive algorithm.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

To build a recursive algorithm, you will break the given problem statement into two parts. The first one is the base case, and the second one is the recursive step.

  • Base Case: It is nothing more than the simplest instance of a problem, consisting of a condition that terminates the recursive function. This base case evaluates the result when a given condition is met.
  • Recursive Step: It computes the result by making recursive calls to the same function, but with the inputs decreased in size or complexity.

For example, consider this problem statement: Print sum of n natural numbers using recursion. This statement clarifies that we need to formulate a function that will calculate the summation of all natural numbers in the range 1 to n. Hence, mathematically you can represent the function as:

F(n) = 1 + 2 + 3 + 4 + …………..+ (n-2) + (n-1) + n 

It can further be simplified as:

Recursive_1

You can breakdown this function into two parts as follows:

Problem_Breakdown-Recursive_Algorithm

Different Types of Recursion

There are four different types of recursive algorithms, you will look at them one by one.

  • Direct Recursion

A function is called direct recursive if it calls itself in its function body repeatedly. To better understand this definition, look at the structure of a direct recursive program.

int fun(int z){

  fun(z-1);  //Recursive call

}

In this program, you have a method named fun that calls itself again in its function body. Thus, you can say that it is direct recursive.

  • Indirect Recursion

The recursion in which the function calls itself via another function is called indirect recursion. Now, look at the indirect recursive program structure.

int fun1(int z){       int fun2(int y){                   

  fun2(z-1);               fun1(y-2)

}                      }

In this example, you can see that the function fun1 explicitly calls fun2, which is invoking fun1 again. Hence, you can say that this is an example of indirect recursion.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

  • Tailed Recursion

A recursive function is said to be tail-recursive if the recursive call is the last execution done by the function. Let’s try to understand this definition with the help of an example. 

int fun(int z)

{

  printf(“%d”,z);

  fun(z-1);    

  //Recursive call is last executed statement

}

If you observe this program, you can see that the last line ADI will execute for method fun is a recursive call. And because of that, there is no need to remember any previous state of the program.

  • Non-Tailed Recursion

A recursive function is said to be non-tail recursive if the recursion call is not the last thing done by the function. After returning back, there is something left to evaluate. Now, consider this example.

int fun(int z)

{

  fun(z-1);

  printf(“%d”,z);

  //Recursive call is not the last executed statement

}

In this function, you can observe that there is another operation after the recursive call. Hence the ADI will have to memorize the previous state inside this method block. That is why this program can be considered non-tail recursive. 

Moving forward, you will implement a C program that exhibits recursive algorithmic nature.

[Related reading: How to Learn Programming?]

Program to Demonstrate Recursion

You will look at a C program to understand recursion in the case of the sum of n natural numbers problem.

#include<stdio.h>

int Sum(int n){

    if(n==0){

        return 0;

    }

    int temp = Sum(n-1);

    return n + temp;

}

int main()

{

    int n;

    printf("Enter the natural number n to calculate the sum of n numbers: ");

    scanf("%d",&n);

    printf("%d",Sum(n));

}

Output:

The output for the sum of n natural numbers program is represented in the image below.

Output_Sum_of_n-Recursive_Algorithm

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Memory Allocation of Recursive Method

Each recursive call generates a new copy of the function on stack memory. Once the procedure returns some data, the copy is deleted from storage. Each recursive call maintains a separate stack because all parameters and other variables defined inside functions are kept on the stack. The stack is deleted after the value from the relevant function is returned. 

Recursion is quite complicated in terms of resolving and monitoring the values at each recursive call. As a result, you have to maintain the stack and track the values of the variables specified in it. To better understand the memory allocation of recursive functions, examine the following example.

//Fibonacci program recursive Function

int Fib(int num)

{

   if ( num == 0 )

      return 0;

   else if ( num == 1 )

      return 1;

   else

      return ( Fib(num-1) + Fib(num - 2) );

//Let’s say we want to calculate Fibonacci number for n=5

Fib(5)

Now, have a look at this recursive Fibonacci code for n = 5. First, all stacks are preserved, each of which prints the matching value of n until n becomes zero. When the termination condition is achieved, the stacks are destroyed one at a time by returning 0 to their calling stack. To understand the call stack hierarchy, look at the figure below.

Call_Stack_Fibonacci_Series

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Conclusion

In this recursive algorithm tutorial, you learned what a recursive algorithm in programming is. After that, you discovered different types of recursion and their function call structures. You also looked at the programming implementation of the sum of n natural numbers recursive problem. Finally, you also understood the memory allocation of a recursive method inside the memory stack.

If you're looking for more in-depth training that goes beyond data structures and covers the foundations of interactive application development, Simplilearn's Post Graduate Program in Full Stack Web Development will prove ideal for you. The program is offered in collaboration with Caltech CTME and is a globally-recognized program designed to improve your odds of becoming a software developer by aiding you in mastering the art of software development. So, go ahead and start exploring!

Have any questions about this article on the recursive algorithm? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!

About the Author

Omkar Prabhakar Ghadage.Omkar Prabhakar Ghadage.

Omkar holds a bachelor's degree in computer science with a machine learning minor. Artificial intelligence and automation are two topics that he's passionate about. Python, R, and C++ are among his programming languages of choice. He enjoys watching web series.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
  • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors