Recursion in Data Structure: How Does it Work, Types & When Used

Introduction

Recursion allows codes to get more compact and efficient by calling a similar function inside a function. This is kind of similar to looping functions, however, there are a huge number of differences. Recursion makes coding programs or solutions much faster and simpler.

Recursion also offers code redundancy, making it much more efficient to read and maintain codes. Understanding recursion well can lead to true mastery over functional programming languages and empower programmers to code certain programs rapidly. Some problems are inherently recursive in nature, thus it is very valuable to know recursive functions to solve them faster. 

Besides, recursion is valuable and compulsory in many problems related to advanced algorithms such as tree and graph traversal. Learning the applications of recursion in data structure and how to effectively use recursion to manipulate functions in various programs is the key to a great coding experience. 

What is Recursion in Data Structure? 

A recursive data structure can be defined as a data structure that can be broken down into simple or miniature instances of itself. For example, trees are composed of small trees and leaf nodes while lists can contain smaller lists as their elements.

However, recursion in the data structure can be defined as a method through which problems are broken down into smaller sub-problems to find a solution. This is done by replicating the function on a smaller scale, making it call itself and then combining them together to solve problems.

Recursion provides a natural approach in declaring many algorithms and is very valuable in functional programming. Developers can effectively use recursion instead of loop functions such as “for loop” or “while loop”.

C++, PHP, Scala and functional JavaScript allow recursive functions or developers to write recursion operations. Every iterative problem can be solved through recursion and every recursive problem can be solved by an iterative approach. This is why the importance of recursion in the data structure is more stressed. 

To understand the applications of recursion in data structure or programming, one must first understand a loop. For example, using C++, if we had to create a loop to display all the possible numbers between 14 and 20, then we would have to use the following codes:

for(int i=15;  i<20; i++) {
     cout << "Possible Number: " << i << endl;
}

It would display this as a result:

Possible Number: 15
Possible Number: 16
Possible Number: 17
Possible Number: 18
Possible Number: 19

This is possible as the loops repeat the function as long as the value of “i” is lesser than 20 due to the use of “for loop”. The starting value is “15” as it is the first number that comes after 14 and the “i++” declaration ensures that every time the loop is repeated, 1 is added to the value of “i”. 

Now, let us use the same code to call a function:

void numberFunction(int i) {
  cout << "Possible Number: " << i << endl;
}

int main() {

for(int i=15; i<20; i++) {
  numberFunction(i);
}

When using recursion or recursive functions, we do not need to use “for loop” as the function will call itself. Now, let us recreate this same program using recursion in C++. 

With recursion, we won’t need to use ‘for loop’ because we will set it up so that our function calls itself. Let’s recreate this same program, only this time we will do it without ‘for loop’. We will use a recursion loop instead like this:

void numberFunction(int i) {
  cout << "Possible Number: " << i << endl;
  i++;
  if(i<20) {
    numberFunction(i);
  }
}

int main() {

int i = 15;
numberFunction(i);

The above codes show how a recursive function has been made by creating a single call to the “numberFunction” and then it calls itself repeatedly till “i” reaches the last number before 20.

How do Recursive Functions Work?

A few programming languages allow recursive functions to call themselves directly or indirectly by calling another function that ends up calling the original function. The memory dedicated when a function is called upon is again relocated on top of memory allocated to the calling function while copies of local variables are created for every call.

Once the base problem has been established, functions return their value to functions through which they are called. Once this happens, memories are de-allocated and the cycle repeats. 

One important aspect of a recursive function is the dire need for a base case or termination point. Every program built with recursion must ensure the functions are terminated, failing which might lead to the system crashing or errors.

Five Main Recursion Methods

There are five main recursion methods programmers can use in functional programming. And, they are: 

• Tail Recursion: Even though linear recursion is the most commonly used method, tail recursion is much more effective. When using the tail recursion method, the recursive functions are called in the end.
• Binary Recursion: When using binary recursion, functions are called upon two times instead of being called one by one. This kind of recursion in the data structure is used in operations such as merging and tree traversal.
• Linear Recursion: It is the most popular recursion method. When using this method, functions call themselves in a non-complex manner and terminate the function with a termination condition. This method involves functions making a single call to itself during execution.
• Mutual Recursion: It is the method where a function will use others recursively. Fundamentally, functions end up calling each other in this method. This method is especially used when writing programs using programming languages that do not support recursive calling functions. Hence, applying mutual recursion can act as a substitute for a recursion function. In mutual recursion, base conditions are applied to a single, some or all the functions.
• Nested Recursion: It is an exception where these types of recursions cannot be converted into an iterative format. In this method, recursive functions pass the parameters as recursive calls which fundamentally translate to recursions inside recursions.

Types of Recursion

The five methods of recursion fall under these two main types of recursion – direct and indirect recursion. Let us learn what they are and understand how to implement them.

Direct Recursion

In direct recursion, functions call themselves. This process involves a single step recursive call by the function from inside itself. Let us check how to implement direct recursion to find out the square root of any number. 

 {
  // base case
    if (x == 0)
    {
      return x; 
    }

  // recursive case
  else 
   {
      return square(x-1) + (2*x) - 1;
   }
}
int main() {
  // implementation of square function
  int input=3;
  cout << input<<"^4 = "<<square(input);
  return 0;
}

The output would display this:

3^4 = 9

Indirect Recursion

Indirect recursion is where functions call other functions to call the original function. This process consists of two steps when creating a recursive call, fundamentally making functions call functions to make a recursive call. Mutual recursion can be described as indirect recursion.

Let us check how to implement indirect recursion to print or find out all the numbers from 15 to 27. 

using namespace std;
int n=15;
// declaring functions
void foo1(void);
void foo2(void);

// defining recursive functions
void foo1() 
{ 
  if (n <= 27) 
  { 
    cout<<n<<" ";  // prints n
    n++;           // increments n by 1
    foo2();       // calls foo2() 
  } 
  else
    return; 
} 

void foo2() 
{ 
  if (n <= 27) 
  { 
    cout<<n<<" ";  // prints n
    n++;           // increments n by 1
    foo1();       // calls foo1()
  } 
  else
    return; 
} 

The output would display this:

15 16 17 18 19 20 21 22 23 24 25 26 27 

How to Use Recursion?

Let us learn how to effectively use recursion using various programming languages to build several simple programs or find solutions to different problems. Being one of the most compact and optimised methods of making functions call or deploy functions when programming, recursion can be applied to efficiently use many algorithms and functions.

Using Recursion in C++

Recursion is very commonly used in programming languages such as C++. Let us check how to use the recursive function in C++ to implement recursion when building a program to find the factorial of 6. 

using namespace std;
 
// Factorial function
int f(int n)
{
    // Stop condition
    if (n == 0 || n == 1)
        return 1;
 
    // Recursive condition
    else
        return n * f(n - 1);
}
 
// Driver code
int main()
{
    int n = 6;
    cout<<"The required factorial gathered from "<<n<<" = "<<f(n);
    return 0;
}

The output will be displayed as:

The required factorial gathered from 6 = 720

Using Recursion in C

Let us use recursion in C to find out the sum of consecutive numbers from 0.

#include <stdio.h>
int sum(int n);

int main() {
    int number, result;

    printf("Enter the last number: ");
    scanf("%d", &number);

    result = sum(number);

    printf("Total value of consecutive numbers = %d", result);
    return 0;
}

int sum(int n) {
    if (n != 0)
        // sum() function calls itself
        return n + sum(n-1); 
    else
        return n;
}

The output will be displayed as:

Enter the last number: (Let’s use the positive integer 5, then the consecutive numbers are 1, 2, 3, 4 and 5)

Enter the last number: 5
Total value of consecutive numbers = 15

Using Recursion in JavaScript

Let us use recursion in JavaScript to find the factorial of 5.

function factorial(x) {

    // if number is 0
    if (x === 0) {
        return 1;
    }

    // if number is positive
    else {
        return x * factorial(x - 1);
    }
}

const num = 5;

// calling factorial() if num is non-negative
if (num > 0) {
    let result = factorial(num);
    console.log(`The required factorial gathered from ${num} = ${result}`);
}

The output will be displayed as:

The required factorial gathered from 5 = 120

Using Recursion in Scala

Recursion in data structure and programming is extensively supported by Scala for building effective data-related and solution-centric programs. Let us use recursion to find the factorial of 4 using Scala.

// Creating object
object GFG
{
    // Function define
    def fact(n:Int): Int=
    {
        if(n == 1) 1
        else n * fact(n - 1)
    }
      
    // Main method
    def main(args:Array[String])
    {
        println(fact(4))
    }
}

Frequently Asked Questions

Example of Recursion.

<script>
// JavaScript code to implement factorial
 
// Factorial function
function f(n)
{
   // Stop condition
   if(n == 0 || n == 1)
     return 1;
      
   // Recursive condition
   else
      return n*f(n-1);
}
 
// Initialize variable n.
let n = 7;
document.write("factorial of "+ n +" is: " + f(n));

</script>

Key Takeaways

Learning recursion well can lead to much more compact, elegant and optimised codes when building programs. And, by adopting a recursive approach, programmers can save a lot of time on many common real-world, statistical, functional, operational and mathematical problems.

Creating a recursive function to power programs using the programming language of their choice is a great way to speed up programming and ensure easy post-development debugging. One must place importance on the different types of recursion methods and their various applications in different languages to learn how to effectively use them for maximum utility.

Beginners must also take care to focus on how recursion works by understanding the fundamentals of implementing recursive approaches when coding.