A module or function can call itself in some computer programming languages, and Recursion is the name for this method. A function in Recursion either calls itself directly or calls another function, which then calls the original function. The recursive function is the name of the function.


A recursive function, like a loop, can go on indefinitely. There are two properties that a recursive function must satisfy to avoid infinite running:

  • Base criteria: There must be at least one base criteria or condition that, when met, causes the function to stop recursively invoking itself.
  • The recursive calls should be progressed in such a way that each recursive call gets closer to the basic criteria.


Stacks are used in several programming languages to implement Recursion. When a function (caller) calls another function (callee) or itself as callee, the caller function typically transfers execution control to the callee function. This process may also include the transmission of data from the caller to the callee.

This means that the caller function must momentarily halt its execution and restart it when the execution control returns to the callee function. In this case, the caller function must begin execution exactly where it puts itself on hold. It also requires the exact same data values as before. An activation record (or stack frame) for the caller function is created for this purpose.

The information about local variables, formal parameters, return address, and all other information supplied to the caller function is stored in this activation record.

Recursion Analysis

One could argue that iteration can accomplish the same objective as Recursion. The first argument is because Recursion makes a programme more understandable, and Recursion is more efficient than iterations, thanks to modern CPU systems.

Complexity of Time

We count the number of iterations in the case of iterations to determine the time complexity. Similarly, in the case of Recursion, we try to determine the number of times a recursive call is made by assuming everything is constant. A function call is O(1). Hence the (n) number of times a recursive call is made, the recursive function is O(1) (n).

Complexity of Space

The amount of extra space required for a module to execute is measured in space complexity. The compiler doesn't need much extra room when it comes to iterations. The compiler constantly updates the values of variables used in iterations. However, in the case of Recursion, the system must keep an activation record for each recursive call. As a result, it is thought that the space complexity of a recursive function may be larger than that of an iterative function.