Which Data Structure is used for Implementing Recursion?

Last Updated on May 5, 2023 by Prepbytes

Stack(LIFO) data structure is one of the famous data structures used for implementing recursion. Recursion is a method of problem-solving where a function is run repeatedly on smaller inputs until a base case, or the smallest input with a simple answer, is reached.

What is Recursion in Data Structure?

Recursion is the process of repeatedly applying a rule or procedure until one arrives at the solution.

The concept behind recursion is that we have a problem that needs to be solved, and we are trying to find a way to do it by showing that the solution is the outcome of applying a series of sequential computations to the outcome of solving a smaller version of the same problem. The same procedure is used to solve an even smaller version of the problem because the smaller problem is of the same type.

The base condition and the recurrence relation are the two components of recursion. Let’s break them down individually using the factorial of a number as an example.

What is Recurrence?

The link between the same function and different input sizes is known as recurrence, This means that we frequently calculate the answer to a bigger input with a smaller input. For instance, suppose we need to compute the factorial of a number N in this case. We develop a helper function called fact(N), which returns the factorial of a number N.

A factorial of numbers using this function can be represented as
*fact(N) = N fact(N-1)**

With a smaller input, the preceding equation is known as a recurrence relation, even though the function fact(N) calls itself.

What is Base Condition?

This is the situation when the input size is so small that the answer is really simple. As in the factorial of a number example, we can observe that the base condition is a fact(1), meaning that given an input of N=1, we are aware of the answer being 1.

Once it locates the base case, the recursion goes back to the previous input, and the pending temporary function calls are stored in the stack data structure in the memory as shown below.

The stack keeps growing with each function call until the base case, in this instance fact(1) = 1, comes. Each function call is then assessed in the order of last in, first out.

Stack for Recursion

We know that in the stack data structure, we have

1. a list of elements
2. Push element into the stack
3. Pop element from the stack
4. Last In First Out

Computers offer a context comprising all the variables (and other names) currently in scope when they execute a programming language. A new context for the function is "pushed" on top of the old context when a function is called, saving the previous context. The contexts are stack frames, and this is the (system) call stack. All the variables (and functions) declared in the called function are listed in each stack frame.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

int sum(int k) 
{
    if (k <= 1) {
        // base case
        return 1;
    } else {
        // recursive case
        return k + sum(k - 1);
    }
}

int main()
{
    int n = 3;
    int ans = sum(n);
    cout<<ans;
 
}

Output

6

Suppose we want to execute sum(3):
The top of the system stack is exactly the base, thus when we run sum(3), a stack frame is stored, and a new stack frame for the function is "pushed" on top of the stack. The example is as follows:

The top stack frame will be removed from the system stack when the base case has been completed:

The next top stack frame will also be popped after that:

As the process continues, the computer will eventually run the initial programme and provide an accurate response:

Conclusion
We concluded that stack is the data structure used for implementing the recursion and is used to store the activation record of a function call, which includes the address of the calling function, local variables, and arguments. The recursive function’s time complexity is proportional to the number of calls that are made to it and space complexity is equal to the number of calls made to it since the call stack will hold the same number of activation records.

Frequently Asked Questions

Q1. What type of data structure implements a priority queue?
Ans. An array, a linked list, a heap data structure, or a binary search tree can all be used to build a priority queue. One of these data structures that effectively implement priority queues is the heap data structure.

Q2. Which data structure is employed in the implementation of a fixed or static stack?
Ans. The finest example of static data structures is an array, which has a fixed size and allows for subsequent data modification.

Q3. Why is a stack referred to as an abstract data type?
Ans. Because push and pop are the two main operations in a stack, it is known as an abstract data type. Which are when applied to any set of data, it is free from the type of data that the set must contain.

Q4. What is the difference between static and dynamic implementation of a list?
Ans. A static data structure has a defined size and cannot be altered during runtime. As a dynamic list can change to fit the data inside of it, it uses less space overall.

Q5. Can we use an array to implement a stack?
Ans. When using an array, the stack is created using the array. Arrays are utilised for all stack-related tasks.