1 Direct Recursion

Direct recursion occurs when a function calls itself.

Example: Factorial calculation using direct recursion:

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is: " << factorial(num);
    return 0;
}

2 Indirect Recursion

Indirect recursion occurs when a function calls another function, which in turns calls the first function, creating a cycle.

Example: Even and odd numbers using indirect recursion:

#include <iostream>
using namespace std;

void even(int n);

void odd(int n) {
    if (n > 0) {
        cout << n << " ";
        even(n - 1);
    }
}

void even(int n) {
    if (n > 0) {
        cout << n << " ";
        odd(n - 1);
    }
}

int main() {
    int num = 10;
    cout << "Even numbers till " << num << ": ";
    even(num);
    return 0;
}

3 Tail Recursion

A recursive function is said to be tail recursive when the recursive call is the last thing executed by the function. In other words, the result of the recursive call is returned without any additional processing. This allows the compiler to optimize the code by reusing the current stack frame for the next recursive call, thus avoiding stack overflow errors.

Example: Factorial calculation using tail recursion:

#include <iostream>
using namespace std;

int factorial(int n, int result = 1) {
    if (n == 0 || n == 1)
        return result;
    else
        return factorial(n - 1, n * result);
}

int main() {
    int num = 5;
    cout << "Factorial of " << num << " is: " << factorial(num);
    return 0;
}

Code Analysis:

Regular Recursion:

• Time Complexity: O(n)
• Space Complexity: O(n)

Tail Recursion

• Time Complexity: O(n)
• Space Complexity: O(1)

Advantages:

1. Optimized memory usage:
   1. Tail-recursive functions use a constant amount of memory, regardless of the number of recursive calls.
   2. The compiler can optimize tail-recursive functions to reuse the current stack frame for the next recursive call, eliminating the need to keep track of multiple stack frames.
2. Improved performance:
   1. By reusing the current stack frame, tail recursion can execute faster than non-tail-recursive functions.
   2. It eliminates the overhead of maintaining multiple stack frames.

Function stack frame management in Tail Call Elimination:

Recursion uses a stack to keep track of function calls. With every function call, a new frame is pushed onto the stack which contains local variables and data of that call. Let’s say one stack frame requires O(1) i.e, constant memory space, then for N recursive call memory required would be O(N).

Tail call elimination reduces the space complexity of recursion from O(N) to O(1). As function call is eliminated, no new stack frames are created and the function is executed in constant memory space.

It is possible for the function to execute in constant memory space because, in tail recursive function, there are no statements after call statement so preserving state and frame of parent function is not required. Child function is called and finishes immediately, it doesn’t have to return control back to the parent function.

As no computation is performed on the returned value and no statements are left for execution, the current frame can be modified as per the requirements of the current function call. So there is no need to preserve stack frames of previous function calls and function executes in constant memory space. This makes tail recursion faster and memory-friendly.

4 Non-Tail Recursion

A recursive function is non-tail recursive when the recursive call doesn't occur at the end of the function.

Example: Fibonacci sequence using non-tail recursions:

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int num = 6;
    cout << "Fibonacci sequence till " << num << ": ";
    for (int i = 0; i < num; ++i)
        cout << fibonacci(i) << " ";
    return 0;
}

5 Multiple Recursion

Multiple recursion occurs when a function makes more than one recursive call.

Example: Tower of Hanoi problem using multiple recursion:

#include <iostream>
using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        cout << "Move disk 1 from rod " << from_rod << " to rod " << to_rod << endl;
        return;
    }
    towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
    cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl;
    towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main() {
    int num = 3; // Number of disks
    towerOfHanoi(num, 'A', 'C', 'B');  // A, B and C are names of rods
    return 0;
}