Give simple tail-recursive function in C++. What other kinds of recursion are there besides tail recursion?

Tail-Recursive Function in C++

A tail-recursive function is a recursive function where the recursive call is the last operation in the function, with no further computation required after the call returns. This enables compilers to optimize the recursion by reusing the same stack frame, avoiding stack overflow for deep recursion.

Example: Tail-Recursive Factorial in C++

#include <iostream>

// Tail-recursive factorial function
int factorialHelper(int n, int accumulator) {
    if (n == 0 || n == 1) {
        return accumulator;
    }
    return factorialHelper(n - 1, accumulator * n); // Tail call
}

int factorial(int n) {
    return factorialHelper(n, 1);
}

int main() {
    std::cout << "Factorial of 5 is: " << factorial(5) << std::endl; // Output: 120
    return 0;
}

Explanation:

• factorialHelper carries an additional parameter (accumulator) that holds the result of the calculations.
• The recursive call to factorialHelper is the last operation in the function, making it tail-recursive.

Types of Recursion Besides Tail Recursion

1. Head Recursion

   • The recursive call is made at the beginning of the function, and computation happens after the call returns.
   • Example:

     void printReverse(int n) {
         if (n == 0) return;
         printReverse(n - 1); // Recursive call first (head recursion)
         std::cout << n << " ";
     }

2. Linear Recursion

   • Each function calls itself at most once, forming a straight chain of calls.
   • Example:

     int sum(int n) {
         if (n == 0) return 0;
         return n + sum(n - 1); // Single recursive call
     }

3. Tree Recursion

   • The function makes multiple recursive calls at each step, creating a tree-like structure of calls.
   • Example:

     int fibonacci(int n) {
         if (n <= 1) return n;
         return fibonacci(n - 1) + fibonacci(n - 2); // Multiple recursive calls
     }

4. Indirect Recursion

   • A function calls another function that eventually calls the first function, creating a cycle of calls.
   • Example:

     void funcA(int n);
     void funcB(int n) {
         if (n <= 0) return;
         funcA(n - 1); // Calls funcA
     }
     void funcA(int n) {
         if (n <= 0) return;
         funcB(n - 1); // Calls funcB
     }

5. Mutual Recursion

   • A specific case of indirect recursion where two or more functions call each other directly.
   • Example:

     bool isEven(int n);
     bool isOdd(int n) {
         if (n == 0) return false;
         return isEven(n - 1); // Calls isEven
     }
     bool isEven(int n) {
         if (n == 0) return true;
         return isOdd(n - 1); // Calls isOdd
     }

6. Nested Recursion

   • A function calls itself within its own recursive call.
   • Example:

     int nestedRecursion(int n) {
         if (n > 100) return n - 10;
         return nestedRecursion(nestedRecursion(n + 11)); // Calls itself within its call
     }

Summary of Recursion Types

By understanding these types, you can choose the appropriate recursive strategy for solving problems effectively. Tail recursion is particularly useful for avoiding stack overflow when recursion depth is significant, provided the compiler supports tail call optimization.