Data Structure - Recursion Basics - Data Structure & Algorithms

What is Data Structure Recursion?

A module or function is allowed to call itself by some of the computer programming languages, which is known as Recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

The Example of a function calling itself is -

The Example of a function that calls another function which in turn calls it again is -

What are the properties of Data Structure Recursion?

The Recursive function usually goes like a loop infinitely. The infinite running of the recursive function can be avoided if the recursive function has the following properties -

  • Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.
  • Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

How Data Structure Recursive function is implemented?

Stacks are used by the programming languages to implement recursion. When a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. In the process of transfer, some data can be passed from caller to the callee.

In such cases, the caller function need to suspend the execution on a temporary basis and later when the execution control returns from callee function, can be resumed. Caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For the called function, an activation record (or stack frame) is created for the purpose.

Activation Records

The information about the local variables, formal parameters, and the return address and other information passed to the caller function are kept in the Activation Record.

Analysis of Recursion

Recursions are used instead of iteration as recursion makes the program more readable as it has the latest enhanced CPU systems, and is more efficient that iterations.

Time Complexity

Numbers of iterations are taken to count the time complexity in iterations, while in recursions; number of times a recursive call is made is identified, assuming other things to be constant. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity

The amount of extra space required to execute a module is considered as Space complexity. Compilers usually not require any extra space in iterations, whereas in recursion, the activation record of each of the recursive call made has to be stored. Hence the space complexity of recursive is higher than iteration function.

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd Protection Status

Data Structure & Algorithms Topics