Recursion : how to change from non-tail to tail

(1) Introduce an accumulator parameter in the recursive function. Initialize the accumulator with a value that satisfies two conditions

a) when the smallest value is passed from main() to the recursive function, it can correctly return the result to the main program.

b) it gives the correct intermediate accumulator at the first recursive call

(2) Adjust the base case so that it returns the value of the accumulator.

(3) Ensure that the recursive call is the final operation within the function and include the accumulator as a parameter in the recursive call.

(4) Transfer the variable that operates with recursive call to the function’s parameters, allowing it to interact with the accumulator.

Let’s transform the given non-tail recursive function, which sums the integers from 1 to n, into a tail-recursive function using the methodology mentioned earlier:

[1] int summation(int n) {
[2]    if (n == 1) {
[3]       return 1; //Base case
[4]    } else {
[5]       return n + summation(n-1);  //recursive case
[6]    }
[7] }

(1) In line 1, introduce an accumulator parameter, acc, in the recursive function. The initial value of the accumulator can be determined later, either as 0 or 1.

(2) In line 3, modify the return statement to return the value of the accumulator acc. Update the line to “return acc”.

(3) In line 5, include the accumulator acc as a parameter in the recursive call. The line should be updated to “return n + summation(n-1, acc)”.

(4) Additionally, transfer the variable into the recursive call in line 5. This further modifies the line to “return summation(n-1, n+acc)”. Note that the first intermediate result (n+acc = n+0 = n) is correct only when initial value of acc is 0 instead of 1. Therefore, in line 2 and line 3, the condition should be changed to “if (n == 0) { return acc }”. Consequently, the initial value of the accumulator must be 0.

The final tail recursive function becomes

[1] int summation(int n, int acc = 0) {
[2]    if (n == 0) {
[3]        return acc; // Base case: return accumulated sum
[4]    } else {
[5]        return summation(n - 1, acc + n); // Recursive case: update accumulator with current number
[6]    }
[7] }

Can you try the following recursive function that reverses 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);
    }
}