Types of Recursions - GeeksforGeeks

Types of Recursion

Recursion are mainly of two types depending on whether a function calls itself from within itself or more than one function call one another mutually. The first one is called direct recursion and another one is called indirect recursion.

Other Types of Recursion

• Direct Recursion.

• Indirect Recursion.

• Tail Recursion.

• Head Recursion.

• Linear recursion.

• Tree Recursion.

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

Time Complexity For Tail Recursion : O(n)

Space Complexity For Tail Recursion : O(n)

void fun(int n)
{
    if (n > 0) {
        cout << n << " ";
 
        // Last statement in the function
        fun(n - 1);
    }
}
 
// Driver Code
int main()
{
    int x = 3;
    fun(x);
    return 0;
}

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.

void fun(int n)
{
    if (n > 0) {
 
  // First statement in the function
        fun(n - 1);
 
        cout << " "<< n;
    }
}
 
// Driver code
int main()
{
    int x = 3;
    fun(x);
    return 0;
}

Slides

Recursion and Dictionies.pdf

Code: To Find Factorial Of a Number