Direct Recursion

Direct recursion occurs when a function directly calls itself within the same function. Direct Recursion can be further categorized into four types:

Tail Recursion

If a recursive function calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion. After that call the recursive function performs nothing. The function has to process or perform any operation at the time of calling and it does nothing at returning time.

Time Complexity For Tail Recursion : O(n) 
Space Complexity For Tail Recursion : O(n)

Head Recursion

If a recursive function calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion. There’s no statement, no operation before the call. The function doesn’t have to process or perform any operation at the time of calling and all operations are done at returning time.

Time Complexity For Head Recursion: O(n) 
Space Complexity For Head Recursion: O(n)

Tree Recursion:

To understand Tree Recursion let’s first understand Linear Recursion. If a recursive function calling itself for one time then it’s known as Linear Recursion. Otherwise if a recursive function calling itself for more than one time then it’s known as Tree Recursion.

Time Complexity For Tree Recursion: O(2^n) 
Space Complexity For Tree Recursion: O(n)

Nested Recursion:

In this recursion, a recursive function will pass the parameter as a recursive call. That means “recursion inside recursion”. Let see the example to understand this recursion.

This Recursion Notes for the GATE Exam provides a comprehensive guide to one of the fundamental concepts in computer science, recursion, specifically tailored for those preparing for the Graduate Aptitude Test in Engineering (GATE). Recursion is a powerful problem-solving technique where a function calls itself during its execution, and it plays a significant role in algorithm design and programming.