Recursion in Data Structure: How it Works Types

Types of Recursion in Data Structure

The main types of recursion are as follows:

Direct Recursion

Functions in direct recursion call themselves. This procedure comprises a single-step recursive call from within the function. Let us take an example below in C++:

#include <iostream>
using namespace std;
int solve(int x){
   if(x==0)
       return 1;
   return x*solve(x-1);
}
int main() {
   int y=solve(5);
   cout<<y;
   return 0;
}

OUTPUT

We can see that the function solve calls itself till it hits the base condition. It is direct recursion.

Indirect Recursion

Indirect recursion occurs when a function calls other functions, which eventually leads back to the original function. It's similar to a series of functions calling each other to generate a recursive process.
Let us look at an example below in C++:

#include <iostream>
using namespace std;
int x=10;
void solve2(void);
void solve1(void);
void solve1(){
   if(x>=0){
       cout<<x<<" ";
       x-=1;
       solve2();
   }
   else return;
}
void solve2(){
   if(x>=0){
       cout<<x<<" ";
       x-=1;
       solve1();
   }
   else return;
}
int main() {
   solve1();
   return 0;
}

OUTPUT

We can see that solve1 calls for solve2, which further calls for solve1 until the base cases get hit. This is indirect recursion.

Tailed Recursion

Tail recursion is a unique form of recursion in which the recursive call is the last operation performed in a function. After the recursive call, there won't be any remaining operations that need to be executed.

Let us look at an example in C++ as follows:

void solve(int x){
	if(x==0){
		return;
	}
	cout<<x<" ";
	x-=1;
	solve(x);
}

We can see that the recursive call is at the end of the function.

Non-Tailed Recursion

Non-tail recursion refers to any form of recursion where the recursive call is not the last operation performed in a function. In this case, after the recursive call, some pending operations still need to be completed.

Let us look at an example in C++ as follows:

void solve(int x){
	if(x==10){
		return;
	}
	solve(x+1);
	cout<<x<" ";
}

We can see that after the recursive call has been made, there are still some steps to be done.

Need of Recursion

In computer science, recursion is a common phenomenon used to tackle complex problems by breaking them down into simpler ones. It allows functions to call themselves, breaking down complex tasks into more straightforward, manageable sub-problems. 

Recursion is particularly useful when working with data structures like trees, graphs, and linked lists, where recursive algorithms can traverse and manipulate the elements effectively. It is also essential for searching, sorting, and producing permutations or combinations. Recursion makes code easier to comprehend and maintain, allowing for modular and reusable programming.

Properties of Recursion

All recursive algorithms follow these steps:

Step 1- The algorithms must have a base case.
Step 2- Recursion must have a base case to determine when a recursive call should stop. It serves as the recursion's ending condition and ensures the function does not call itself indefinitely.

Step 3- The algorithms should call themselves recursively.
Recursion involves a recursive phase that splits the original problem into smaller sub-problems of the same kind.

Step 4- The algorithm must change its state and move toward the base case.
By changing the state with each recursive call, the method maintains progress towards the termination condition, breaking down the problem into smaller, more manageable sub-problems until no further recursion is required.

Also Read - Recursive Relationship in DBMS

What is a Recursive Algorithm?

A recursive algorithm is a problem-solving approach that involves breaking down a problem into smaller and smaller subproblems until the subproblems become simple enough to be solved directly. The solution to the original problem is then obtained by combining the solutions to the smaller subproblems. 

A key feature of a recursive algorithm is that it calls itself with a smaller version of the problem as its input. The algorithm uses a base case to terminate the recursion when the problem is small enough that it can be solved directly without further recursion. 

Steps for implementing recursion in a function are as follows:

Step 1- Start with defining a recursive function along with all necessary parameters.
 

Step 2- Determine a base condition. In that base condition, either it will return a specific value or end the recursive function.
 

Step 3- If the base case condition is not met, it will break down the large complex problem into subproblems to reduce its size.
 

Step 4- The same function recursively calls itself. If there are multiple recursive calls made, then they are combined to solve the original problem.
 

Step 5- Defining the termination condition is essential so that it does not create an infinite recursion.

How are recursive functions stored in memory?

A data structure known as the call stack stores recursive functions in memory.
The call stack is a stack-like part of memory that tracks function calls and their associated data. When you call a recursive function, the program creates a new stack frame and pushes it onto the call stack. 

The stack frame contains local variables, parameters, and the return address. Once a base case is reached, the frame of the recursive call pops out from the stack. As the recursion unwinds, the function retrieves the results from each recursive call and merges them to obtain the final result. 

It is vital to remember that a stack overflow error can occur if the recursion depth becomes too wide or if the memory allotted for the call stack exceeds. This situation occurs when the number of nested function calls exceeds a specific limit and insufficient memory is available to store the associated stack frames.

What is the base condition in recursion?

The base condition, also referred to as the base case, is the state that determines when the recursion should terminate, and the function should return a result directly without further recursive calls.

In a recursive function, the base condition acts as a stopping bar to prevent indefinite recursion and confirm that the recursion ends. When you reach a base condition, the recursive function gets terminated, and we ensure that it returns a specific value or performs a particular action.

When the base condition estimates to true, the function performs the logic associated with the base case and returns a result. This result is then used in subsequent recursive calls, helping to solve the overall problem step by step.

How can a particular problem be solved using recursion?

Recursion is a problem-solving method in which we create a function that breaks down a complex problem into a smaller-sub problems. 

Step 1: A recursive function calls itself until the problem size is small. Identifying the base condition to solve the problem without further recursion is essential. 

Step 2: We have to express our problem into subproblems to reduce the problem's size. We must call the recursive function on those subproblems until the base condition is achieved. 

Step 3: Then, combine all the results from the recursive function to solve the more significant problem. It is necessary to mention the base condition so that it does not content itself in loops indistinctly.

For example, consider the factorial function. The factorial of a non-negative integer n (denoted as n!) is the product of all positive integers from 1 to n. This function is solved as follows:

factorial(n):
   if n == 0:
      return 1
   else:
      return n * factorial(n-1)

In this example, the base condition is when the n equals 0 and will return 1. The function will call itself with an n-1 argument and continue until the base condition is reached. The sub-problems will be multiplied by n with the factorial of n-1, giving a factorial of n as a result.

Why does Stack Overflow error occur in recursion?

A stack Overflow situation occurs when the recursion is too deep and exceeds the available stack space. Whenever someone calls a recursive function, it creates a new stack frame, which may exhaust the stack's capacity and cause an error. This situation may occur when a base case is not reached, or recursion is not controlled.

Each recursive call consumes memory, including space for local variables and return addresses. If this usage exceeds the stack's capacity, a stack overflow error is triggered, resulting in program termination. Proper termination conditions and efficient use of recursion can help prevent stack overflow errors.

Aslo read - How To Sort A Stack Using Recursion?

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. 

#include<bits/stdc++.h>
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;
}

Output

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;
}

Output

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}`);
}

Output

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))
    }
}

Also check out - Rod Cutting Problem

Example of Recursion in Data Structure

Let us see recursion in data structure in action now with an example.

Swapping Nodes of a Linked List in Pairs

In this scenarios, we have to swap the nodes in pairs. It means that we have to swap every two adjacent nodes in the original linked list without changing their values.

If the input list is as below:

1→3→2→4→NULL

The output should be as follows:

3→1→4→2→NULL

Let us see its recursion code snippet as below in C++:

Node* swapPairs(Node* head) {
        if(head==NULL)
            return NULL;
        int cnt=0;
        Node* curr=head;
        Node* prev=NULL;
        Node* forward=NULL;
        while(curr!=NULL && cnt<2){
            forward=curr->next;
            curr->next=prev;
            prev=curr;
            curr=forward;
            cnt+=1;
        }
        if(forward!=NULL){
            head->next=swapPairs(forward);
        }
        return prev;
    }

We can see that we reverse the linked list for every two nodes using three temporary nodes as curr, prev and, forward. Then, if we are satisfied that there are more elements in the list, we recursively call for the function again else we return our ans. 

Difference between Recursion and Iteration

Also read a brief blog on - Difference between Iteration and Recursion for better understanding.

Advantages of Recursive Programming

There are many advantages to using recursion in data structures, including:

• Recursive solutions often deliver a more intuitive and straightforward representation of the complex problem.
• Recursion can more naturally handle dynamic data structures like trees or graphs than iterative approaches.
• Recursion can sometimes lead to more efficient solutions than iterative approaches, especially with dynamic programming or divide-and-conquer strategies.
• Recursion provides a more clear vision of the algorithm with recursive patterns

Disadvantages of Recursive Programming

There are some potential drawbacks to using recursion in data structures, including:

• Memory usage: Recursive algorithms can use a lot of memory, particularly if the recursion goes too deep or if the data structure is large. Each recursive call creates a new stack frame on the call stack, which can quickly add up to a significant amount of memory usage.
• Stack overflow: If the recursion goes too deep, it can cause a stack overflow error, which can crash the program.
• Performance: Recursive algorithms can be less efficient than iterative algorithms in some cases, particularly if the data structure is large or if the recursion goes too deep.
• Debugging: Recursive algorithms can be more difficult to debug than iterative algorithms, particularly if the recursion goes too deep or if the program is using multiple recursive calls.
• Code complexity: Recursive algorithms can be more complex than iterative algorithms.
  Also read - Data Structure MCQ

Frequently Asked Questions

What problems does recursion solve?

There are many use cases of recursion, such as tree and graph traversals, backtracking problems like N-Queen or maze problems, divide and conquer problems like merge sort, dynamic programming problems like knapsack problems, or used in identifying patterns.

Does recursion affect time complexity?

Yes, recursion affects the time complexity. It depends on how the recursion has been implemented and the number of recursive calls made. This whole affects the time complexity of the program. In some cases, recursion may have a high time complexity to the iterative approach.

What is the difference between direct and indirect recursion?

Functions in direct recursion call themselves. This procedure comprises a single-step recursive call from within the function. But, indirect recursion occurs when a function calls other functions, which eventually leads back to the original function. It's similar to a series of functions calling each other.

What is the difference between tailored and non-tailed recursion?

Tail recursion is a form in which the recursive call is the last operation performed in a function. After this call, there won't be any remaining operations. Non-tail recursion is a form where the recursive call is not the last operation performed in a function. Here, after the recursive call, there are some operations.

Conclusion

In this article, we explore the occurrence of recursion within data structures and the storage of recursive functions in memory. The significance of base conditions and the potential ramifications of a stack overflow condition is discussed. Additionally, we examine the distinctions between direct and indirect recursion and the differences between tailored and non-tailored recursion. The article delves into implementing recursion in different programming languages and offers a comparison with iteration. Furthermore, the advantages and disadvantages of recursive programming compared to iterative programming are thoroughly presented throughout the article.

Recommended Reading:

1. Backtracking and Recursion
2. Recursion and stack
3. Recursion in python

To learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.

Also check out some of the Guided Paths on topics such as, Competitive Programming, Operating Systems, Computer Networks, etc. only on Coding Ninjas Studio.