Recursion

The process in which a function calls itself and only works where we call the same operation multiple times with different inputs. In every call, we try to make the problem smaller. There must be a base case where the system will stop the recursion and give you a result back. It internally stores the recursion state in the method call stack. If there is no base condition in the recursion method then it will go into an infinite loop and you might face the StackOverflow Exception.

There are several types of recursion:-

• Head Recursion
• Tail Recursion
• Tree Recursion
• Nested Recursion

Head Recursion

It will call recursively first then at the end do all the computation.

private static int factorial(int number) {
    return (number==1)?
            number :
            number*factorial(number-1) ;
}

factorial(5)
(5* factorial(5-1))
(5* (4* factorial(4-1))
(5* (4* (3*factorial(3-1)))
(5* (4* (3* (2*factorial(2-1))))
(5* (4* (3* (2* (1*1)))))
output = 120

Tail Recursion
It will first do the calculation then do the call recursively, In the end, we don't need to go back again and do the calculation.

private static int tailFactorial(int factorialNumber, int factorialValue) {
    return (factorialNumber == 1) ?
            factorialValue :
            tailFactorial(factorialNumber-1, factorialValue*factorialNumber);
}

tailFactorial(1,5)
tailFactorial(5, (5-1))
tailFactorial(20, (4-1))
tailFactorial(60, (3-1))
tailFactorial(120, (2-1))
tailFactorial(120,1)
output = 120

Tree Recursion
In the above example, we are calling only one time so it is a linear recursion but when I call the same function more than one time with the same input then we call tree recursion. The below tree factorial is not actually calculating the factorial but it's just an example to demonstrate to you the tree recursion internal working.

private static int treeFactorial(int factorialNumber, int factorialValue) {
    return (factorialNumber == 1) ?
            factorialValue :
            treeFactorial(factorialNumber-1, factorialValue * factorialNumber)
            *  treeFactorial(factorialNumber -1, factorialValue * factorialNumber);
}

Nested Recursion
Nested Recursion is nothing but when we pass the same function as an argument of the recursive function call. The example below shows that you nested recursion working; it doesn't calculate the factorial at all.

private static int nestedFactorial(int factorialNumber, int factorialValue) {
    return (factorialNumber == 1) ?
            factorialValue :
            nestedFactorial( factorialNumber-1,
                    nestedFactorial(factorialNumber-1,factorialValue * factorialNumber));
}

We will deep dive into the recursion in the future on the tree, graph, search, divide and conquer, greedy algorithm, and dynamic programming topics. Please stay connected with us and subscribe to our blog.