Tail and non-tail recursive function

The provided example showcases the reversal of digits within an integer using two different methods: non-tail recursion and tail recursion. The main() function calls the reverseDigit() function, implemented with both non-tail and tail recursive approaches. By inputting the integer 12345, the function will return the integer 54321. This example provides a clear demonstration of the contrasting coding techniques and their effects.

main.cpp

#include "Reverser.h"
#include <iostream>
#include <string>
using namespace std;

int main(){
    Reverser reverser;
    int reversedNumber = reverser.reverseDigit(12345);
    cout << "Reversed number: " << reversedNumber << endl;
    return 0;
}

(A) Non-tail recursive function

Reverser.h

#ifndef REVERSER_H
#define REVERSER_H
#include <string>
using namespace std;

class Reverser{
    public:
        int reverseDigit(int value);
};
#endif

Reverser.cpp

#include <iostream>
#include "Reverser.h"
#include <string>
#include <cstdio> 
using namespace std;

int Reverser::reverseDigit(int value){
    if (value < 10 ) { 
        return value; // Base case: single-digit number, return as is
    }
    int lastDigit = value % 10;
    int remainingDigits = value / 10;
    int reversed = reverseDigit(remainingDigits);
    // Determine the value of multiplier from returned data 
    int multiplier = 10;
    int temp = reversed;
    while (temp >= 10) {
        temp /= 10;
        multiplier *= 10;
    }
    return (lastDigit * multiplier) + reversed;
}

From the above coding, the recursive call is “reverseDigit(remainingDigits)” . There are pending computations before a value is passed back to the caller using ” return (lastDigit * multiplier) + reversed “

(B) Tail recursive function

Reverser.h

#ifndef REVERSER_H
#define REVERSER_H
#include <string>
using namespace std;

class Reverser{
    public:
        int reverseDigit(int value, int reversedNum=0);
};
#endif

Reverser.cpp

#include <iostream>
#include "Reverser.h"
#include <string>
using namespace std;

int Reverser::reverseDigit(int value, int reversedNum){
    if (value == 0 ) {
        return reversedNum; // Base case: single-digit number, return as is
    }
    int lastDigit = value % 10;
    reversedNum = (reversedNum *10)+ lastDigit;
    return reverseDigit(value/10, reversedNum );
}

The recursive call “reverseDigit(value/10, reversedNum )” is in the tail position since it is the last operation performed before returning the result. The intermediate results are saved in the variable “reversedNum”. When the base case is met, the final result is already saved in the variable “reversedNum”. This final result is returned several times to the main() function.