C++ Recursion: introduction and example codes

In C++, recursion is a programming technique where a function calls itself directly or indirectly. A C++ recursive function typically consists of two parts:

1. Base case: It defines the terminating condition for the recursion. When the base case is met, the recursive function stops calling itself and returns a value or performs a specific action. The base case is essential to prevent infinite recursion.
2. Recursive case: It defines the logic to break down the problem into smaller subproblems of the same type. The recursive function will call itself with modified parameters to solve the smaller subproblems. The recursive case should be designed such that it converges towards the base case.

Write a recursive function to find the factorial of n

int factorial(int n) {
    if (n == 1) {
        return 1; //Base case
    } else {
        return n * factorial(n-1);  //recursive case
    }
}

Write a recursive function to sum the integers from 1 to n

int summation(int n) {
    if (n == 1) {
        return 1; //Base case
    } else {
        return n + summation(n-1);  //recursive case
    }
}

Write a recursive function to compute:
f(n) = 1 x 2 + 2 x 3 + 3 x 4 + … + (n-1) x n

int addition(int n) {
    if (n == 2) {
        return 1*2; //Base case
    } else {
        return (n-1)*n + addition(n-1);  //recursive case
    }
}

Write a recursive function that implements x^n  (i.e. 2^3 = 2 * 2 * 2), where x is any real number and n is a non-negative integer

int power(int x, int n) {
    if (n == 0) {
        return 1; //Base case
    } else {
        return x * power(x, n-1);  //recursive case
    }
}

Write a recursive function to reverse a string

string reverseString(string characters){
    if (characters.length() == 1) {
        return characters; // Base case: single character, return as is
    } else {
        char lastChar = characters.back();
        string remainingChars = characters.substr(0, characters.length() - 1);
        return lastChar + reverseString(remainingChars);
    }
}