Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47
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.

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.