What is recursion?

Recursion

In computer programming, recursion is a wonderful programming technique where a function or method call itself repeatedly without using a loop until achieving some satisfied condition. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc. Instead of repeating the task like iteration, a recursive work accomplishes repetition by referring to itself in its own definition. While the concept of recursive programming can be difficult to grasp initially, but in mastering, it can be very useful. While it may not seem like much on the surface, but recursion allows us to write the elegant solution of a problem that may otherwise be very difficult to program.

As an example -

The factorial of an integer n, which is written as n!, is the result of multiplying n by all of the positive integers less than n. For instance, 3! = 3 x 2 x 1, which results in 6, and 4! = 4 x 3 x 2 x 1, which results in 24.

An efficient way to calculate a factorial is by using a recursive function. Here is the implementation of recursion in Java.

Types of recursion

Single recursion - It only contains a single self-reference that can generally be replaced by an iterative computation, running in linear time and requiring constant space. For example: include list traversal - such as a linear search, or computing the factorial function.

Multiple recursion - It contains multiple self-references that require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack. Example include tree traversal - such as in a depth-first search.

 

Multiple recursion can sometimes be converted to single recursion. For example, while computing the Fibonacci sequence naively, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters.

Methods of recursion

Direct recursion - A function fact is called direct recursive if it calls the same function fact.

Example -

void fact() {
    // Some code....
    fact();
    // Some code...
}

 

Indirect recursion - A function fun is called indirect recursive if it calls another function say fun_new and fun_new calls fun directly or indirectly.

Example -

void funcA() {
    // Some code...
    funcB();
    // Some code...
}
void funcB() {
// Some code...
    funcA();
    // Some code...
}