RECURSIVE ALGORITHM

I learn a lot of programming languages ​​but in this blog I prefer everything to be practical and more detailed and low level. I recently worked on the topic of recursive algorithms.

WHAT IS RECURSIVE ALGORITHM?

A recursive algorithm performs basic operations on the returned value for the smaller input by calling itself with a smaller input and returning a result for the current input. In general, a problem can be solved by applying a solution to a smaller version of the same problem, and a recursive algorithm can be used to solve the problem by compressing the smaller version into an easily solvable instance.

To build a recursive algorithm, we break this condition of the problem into two parts. The first is the basic step and the second is the recursive step.

Base Case: This is just the simplest example of a problem that consists of a condition that terminates a recursive function. This base case evaluates an outcome when a given condition is met.

Recursive step: Recursively call the same function to compute the result, but with reduced input size or complexity.

TYPES OF RECURSION

There are four types of recursive algorithms, let’s look at them one by one.

DIRECT RECURSION

A function is said to be directly recursive when it calls itself multiple times in the function body. To better understand this definition, look at the structure of a direct recursive program.

INDIRECT RECURSION

Recursion, in which a function calls itself through another function, is called indirect recursion.

TAILED RECURSION

A recursive function is said to be tail cursive if the recursive call is the last execution of the function.

NON TAILED RECURSION

A recursive function is said to be non-tail recursive if the recursive call is not the last operation performed by the function. You have to go back and evaluate.

MEMORY ALLOCATION OF RECURSIVE CALL

Each recursive call creates a new copy of the function in the stack memory. As soon as the procedure returns some data, the copy is removed from the repository. Each recursive call supports a separate stack because all parameters and other variables defined inside the function are stored on the stack. After returning a value in that function, the stack is removed.

Recursion is very complex in terms of resolution and monitoring values ​​with each recursive call. As a result, you need to maintain a stack and keep track of the values ​​of variables specified here.

CONCLUSION

In this blog, I learned what recursive programming algorithms. After that, you have discovered other types of recursive and functional calling structures. In addition, I have been implemented to program the amount of N natural number of recursive problems. Finally, we have understood the memory distribution of recursive methods inside the stack of memory.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store