{"id":16160,"date":"2023-05-05T10:02:13","date_gmt":"2023-05-05T10:02:13","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16160"},"modified":"2023-05-05T10:02:13","modified_gmt":"2023-05-05T10:02:13","slug":"which-data-structure-is-used-for-implementing-recursion","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/which-data-structure-is-used-for-implementing-recursion\/","title":{"rendered":"Which Data Structure is used for Implementing Recursion?"},"content":{"rendered":"

\"\"<\/p>\n

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.<\/p>\n

What is Recursion in Data Structure?<\/h2>\n

Recursion is the process of repeatedly applying a rule or procedure until one arrives at the solution.<\/p>\n

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.<\/p>\n

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.<\/p>\n

What is Recurrence?<\/h2>\n

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.<\/p>\n

A factorial of numbers using this function can be represented as
\n*fact(N) = N <\/em> fact(N-1)**<\/p>\n

With a smaller input, the preceding equation is known as a recurrence relation, even though the function fact(N) calls itself.<\/p>\n

What is Base Condition?<\/h2>\n

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.<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

\"\"<\/p>\n

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.<\/p>\n

\"\"<\/p>\n

Stack for Recursion<\/h2>\n

We know that in the stack data structure, we have<\/p>\n

    \n
  1. a list of elements<\/li>\n
  2. Push element into the stack<\/li>\n
  3. Pop element from the stack <\/li>\n
  4. Last In First Out<\/li>\n<\/ol>\n

    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.<\/p>\n

    Code Implementation<\/strong><\/p>\n\t\t\t\t\t\t