Optimisation using Tail Recursion

Tail Recursion makes the performance efficient both in terms of time and space

Tail Recursive Programs (Beginner Friendly) starts after the end of explanation.

Factorial Of Number
Number of Digits In a Number
Number Of Even Elements In Array
Reverse Integer
Sum Of Digits
Sum Of Elements In Array
Binary Search
Pow(x, n)
Minimum Element In Array
Perfect Number
Sum Of First N Natural Numbers
Number Of Times Digits Encountered
Palindrome Number
Sum Of Proper Divisor
Greatest Common Divisor(GCD)

Non-tail recursion to Tail recursion will lead from slower execution to faster execution and from O(n) space to O(1) space.

Let's try to understand.
Recursion is slow because of the time spend in pushing and popping the activation records on and from the stack for each recursive call and expensive in terms of memory as well because it requires space in the stack to store the activation records for each recursive call and if the stack is too deep, then stack may overflow.

This can be improved by making recursive program as tail recursive as it doesn't involves pushing and popping operations, rather the previous activation record gets overwrittern by the current activation record when a recursive call occurs, while retaining the original return address. So, at a time we have only one activation record on the stack and that too for the currently executing recursive call. So, it doesn't matter that how deep the recursion is, the space requirement will always be constant and improves the overall performance by reducing the time and space/memory requirements.

Non-tail recursion

A recursive call is said to be non-tail recursive if it is not the last statement to be executed inside a function or that call is a part of expression.
eg:

int fact(int num) {
if(num == 1) {
  return 1;
}
return num * fact(num - 1); // not a tail recursive call as it is a part of expression
}

Non-Tail recursive functions have to finish the pending work after the recursive call finishes, so activation record for each recursive call has to be maintained in the stack.

Let's understand by an example,
To find factorial of 5 using non-tail recursion

fact(5)
5 * fact(4)
5 * (4 * fact(3))
5 * (4 * (3 * fact(2)))
5 * (4 * (3 * (2 * fact(1)))) --> Recursive call finishes here
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120

Here, after the recursive call, we still need to remember to multiply later on, in order to get the desired results, and to remember, space is required in order to store the activation record in the stack for each recursive call which will degrade performance and will not be space efficient.

Tail recursion

A recursive call is said to be tail recursive if it is the last statement to be executed inside a function and that call is not a part of expression.
eg:
```
int fact(int num, int res){
if(num == 1){
  return res;
}

return fact(num - 1, num * res);  // tail recursive call
}
```
A recursive function can be converted into a tail recursive function using an auxiliary parameter(like we have used (res) in our case). The result is accumulated in this parameter and this is done in such a way that there is no pending operation left after the recursive call.
In tail recursive function, since no pending operations are left after making a recursive call, so no need to store the record of the previous state i.e. no need to push a new activation record for each recursive call in the stack.

Let's understand by an example
To find factorial of 5 using tail recursion
fact(5, 1)
fact(4, 5)
fact(3, 20)
fact(2, 60)
fact(1, 120)
120

Here, we are performaing running multiplication using the auxiliary variable(res) on the fly as we move along instead of waiting till the end and doing multiplication backwards. So, nothing to remember and therefore no need to store activiation record for each recursive call which results in faster performance and will be space efficient as well.
Tail recursion is a compile level optimisation. Some modern compiler can detect tail recursion and perform the optimisation by converting it to iteration to improve performance.
Java, python don't support tail recursion optimisation while C and C++ do.

Let's see whether Java supports Tail Recursion optimisation or not.

class Sample {
  public static void main(String[] args) {
    System.out.println(new Sample().fact(5, 1));
  }

  private int fact(int num, int res) {
    if(num == 1) {
      System.out.println(10 / 0);
      return res;
    }

    return fact(num - 1, res * num);
  }
}

Exception in thread "main" java.lang.ArithmeticException: / by zero
	at Sample.fact(Sample.java:8)
	at Sample.fact(Sample.java:12)
	at Sample.fact(Sample.java:12)
	at Sample.fact(Sample.java:12)
	at Sample.fact(Sample.java:12)
	at Sample.main(Sample.java:3)

Here, I tried to throw an exception in a tail recursive function and we can see all the recursive calls in the stack trace and it can clearly be seen that Java doesn't support tail recursion optimization and according to Brian Goetz(Java Language Architect @ Oracle) there are number of security sensitive methods in JDK which rely on counting stack frames between JDK library code and calling code to figue out who's calling them.

References:
Data Structures through C in Depth by S.K.Srivastava/Deepali Srivastava,
https://stackoverflow.com/questions/33923/what-is-tail-recursion,
https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all

Let's solve beginner friendly problems using Tail Recursion-

Factorial Of Number

#include<stdio.h>

int fact(int);
int factViaTailRecursion(int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("Factorial of %d is: %d\n", num, fact(num));
  printf("Factorial of %d via tail recursion is: %d\n", num, factViaTailRecursion(num, 1));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int fact(int num) {

  if(num == 1) {
    return 1;
  }

  return num * fact(num - 1);
}

/*
Time: O(n)
Space: O(1)
*/
int factViaTailRecursion(int num, int fact) {

  if(num == 1) {
    return fact;
  }

  return factViaTailRecursion(num - 1, num * fact);
}

Number of Digits In a Number

#include<stdio.h>

int countDigits(int);
int countDigitsUsingTailRecursion(int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("Number of digits in %d are: \n", countDigits(num));
  printf("Number of digits in %d via Tail Recursion are: \n", countDigitsUsingTailRecursion(num, 0));
  return 0;
}

/*
Time: O(log n)
Space: O(log n)
*/
int countDigits(int num) {

  if(num == 0) {
    return 0;
  }

  return 1 + countDigits(num / 10);
}

/*
Time: O(log n)
Space: O(1)
*/
int countDigitsUsingTailRecursion(int num, int count) {

  if(num == 0) {
    return count;
  }

  return countDigitsUsingTailRecursion(num / 10, count + 1);
}

Number Of Even Elements In Array

#include<stdio.h>

int getEvenElementsCount(int[], int);
int getEvenElementsCountViaTailRecursion(int[], int, int);

int main(){
  int arr[] = {3, 9, 2, 6, 7, 4, 5};
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("Total number of even elements: %d\n", getEvenElementsCount(arr, size));
  printf("Total number of even elements via Tail Recursion: %d\n", getEvenElementsCountViaTailRecursion(arr, size, 0));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int getEvenElementsCount(int arr[], int size) {

    if(size == 0) {
      return 0;
    }

    if((arr[size - 1] & 1) == 0) { // equivalent to if((arr[size - 1] % 2) == 0)
      return 1 + getEvenElementsCount(arr, size - 1);
    }

    return getEvenElementsCount(arr, size - 1);
}

/*
Time: O(n)
Space: O(1)
NOTE: In each invocation of the function, only one recursive call will be executed and that recursive call
will be the last one to be executed inside the function. So, both the recursive calls are tail recursive.
i.e. return getEvenElementsCountViaTailRecursion(arr, size - 1, evenElementsCount + 1)
and return getEvenElementsCountViaTailRecursion(arr, size - 1, evenElementsCount)
both are tail recursive.
*/
int getEvenElementsCountViaTailRecursion(int arr[], int size, int evenElementsCount) {

  if(size == 0) {
    return evenElementsCount;
  }

  if((arr[size - 1] & 1) == 0) { // equivalent to if((arr[size - 1] % 2) == 0)
    return getEvenElementsCountViaTailRecursion(arr, size - 1, evenElementsCount + 1);
  }

  return getEvenElementsCountViaTailRecursion(arr, size - 1, evenElementsCount);
}

Reverse Integer

#include<stdio.h>

int reverse(int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("After reversing %d --> %d\n", num, reverse(num, 0));
  return 0;
}

/*
Time: O(log n)
Space: O(1)
*/
int reverse(int num, int rev) {

  if(num == 0) {
    return rev;
  }

  return reverse(num / 10, (rev * 10) + (num % 10));
}

Sum Of Digits

#include<stdio.h>

int sumOfDigits(int);
int sumOfDigitsUsingTailRecursion(int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("Sum of digits of %d is: %d\n", sumOfDigits(num));
  printf("%Sum of digits of %d via Tail Recursion is: %d\n", sumOfDigitsUsingTailRecursion(num, 0));
  return 0;
}

/*
Time: O(log n)
Space: O(log n)
*/
int sumOfDigits(int num) {

  if(num == 0) {
    return 0;
  }

  return (num % 10) + sumOfDigits(num / 10);
}

/*
Time: O(log n)
Space: O(1)
*/
int sumOfDigitsUsingTailRecursion(int num, int sum) {

  if(num == 0) {
    return sum;
  }

  return sumOfDigitsUsingTailRecursion(num / 10, sum + (num % 10));
}

Sum Of Elements In Array

#include<stdio.h>

int sumOfElements(int[], int);
int sumOfElementsViaTailRecursion(int[], int, int);

int main(){
  int arr[] = {5, 18, 11, 46};
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("Sum of elements in array is: %d\n", sumOfElements(arr, size));
  printf("Sum of elements in array via Tail Recursion is: %d\n", sumOfElementsViaTailRecursion(arr, size, 0));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int sumOfElements(int arr[], int size) {

  if(size == 0) {
    return 0;
  }

  return arr[size - 1] + sumOfElements(arr, size - 1);
}

/*
Time: O(n)
Space: O(1)
*/
int sumOfElementsViaTailRecursion(int arr[], int size, int sum) {

  if(size == 0) {
    return sum;
  }

  return sumOfElementsViaTailRecursion(arr, size - 1, sum + arr[size - 1]);
}

Binary Search

#include<stdio.h>

int binarySearch(int[], int, int);
int binarySearchViaTailRecursion(int[], int, int, int);

int main(){

  int arr[] = {10, 20, 30, 40, 50};
  int target;
  printf("Enter the number to find it's index\n");
  scanf("%d", &target);
  int size = sizeof(arr) / sizeof(arr[0]);
  printf("Index of %d is %d\n", target, binarySearch(arr, size, target));
  printf("Index of %d via Tail Recursion is %d\n", target, binarySearchViaTailRecursion(arr, target, 0, size - 1));
  return 0;
}

/*
Time: O(logn)
Space: O(1)
*/
int binarySearch(int arr[], int size, int target) {

  int start = 0;
  int end = size - 1;

  while(start <= end) {

    int mid = start + ((end - start) >> 1);

    if(arr[mid] == target) {
      return mid;
    }

    if(arr[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }

  return -1;
}

/*
Time: O(logn)
Space: O(1)
NOTE: In each invocation of the function, only one recursive call will be executed and that recursive call
will be the last one to be executed inside the function. So, both the recursive calls are tail recursive.
i.e. return binarySearchViaTailRecursion(arr, target, mid + 1, end);
and return binarySearchViaTailRecursion(arr, target, start, mid - 1);
both are tail recursive.
*/
int binarySearchViaTailRecursion(int arr[], int target, int start, int end) {

  if(start > end) {
    return -1;
  }

  int mid = start + ((end - start) >> 1);

  if(arr[mid] == target) {
    return mid;
  }

  if(arr[mid] < target) {
    return binarySearchViaTailRecursion(arr, target, mid + 1, end);
  }

  return binarySearchViaTailRecursion(arr, target, start, mid - 1);
}

Pow(x, n)

/*
Calculate x raised to the power of given n
eg:
2.0 ^ 5 = 32.000000
7.0 ^ 11 =  1977326743.000000
For explanation, refer to the following link
https://leetcode.com/problems/powx-n/discuss/1337794/JAVA-C%2B%2B-%3A-Simple-or-O-log(n)-or-Easy-or-Faster-than-100-or-Explained
*/

#include<stdio.h>

double getPowViaIteration(double, int);
double getPowViaRecursion(double, int);
double getPowViaTailRecursion(double, int, double);

int main() {
  double x = 2.0;
  int n = 5;
  printf("%lf\n", getPowViaIteration(x, n));
  printf("%lf\n", getPowViaRecursion(x, n));
  printf("%lf\n", getPowViaTailRecursion(x, n, 1));
  return 0;
}

/*
Time: O(logn)
Space: O(1)
*/
double getPowViaIteration(double x, int n) {

  double pow = 1;

  while(n != 0) {

    if((n & 1) == 1) { // if((n & 1) == 1) is equivalent to if((n % 2) == 1)
      pow *= x;
    }

    x *= x;
    n >>= 1; // n >>= 1 is equivalent to n /= 2
  }

  return pow;
}

/*
Time: O(logn)
Space: O(logn)
*/
double getPowViaRecursion(double x, int n) {

  if(n == 0) {
    return 1;
  }

  if((n & 1) == 1) { // if((n & 1) == 1) is equivalent to if((n % 2) == 1)
    return x * getPowViaRecursion(x * x, n >> 1); // n >> 1 is equivalent to n / 2
  }

  return getPowViaRecursion(x * x, n >> 1);
}

/*
Time: O(logn)
Space: O(1)
*/
double getPowViaTailRecursion(double x, int n, double pow) {

  if(n == 0) {
    return pow;
  }

  if((n & 1) == 1) { // if((n & 1) == 1) is equivalent to if((n % 2) == 1)
    return getPowViaTailRecursion(x * x, n >> 1, pow * x); // n >> 1 is equivalent to n / 2
  }

  return getPowViaTailRecursion(x * x, n >> 1, pow);
}

Minimum Element In Array

#include<stdio.h>

int getMinVal(int[], int);
int getMinValUsingTailRecursion(int[], int, int);

int main(){
  int num;
  printf("Enter the number of elements you want to enter\n");
  scanf("%d", &num);
  int arr[num];
  int i;
  for(i = 0; i < num; ++i) {
    scanf("%d", &arr[i]);
  }

  printf("Minimum element in the array is %d\n", getMinVal(arr, num - 1));
  printf("Minimum element in the array using Tail Recursion is %d\n", getMinValUsingTailRecursion(arr, num, arr[0]));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int getMinVal(int arr[], int size) {

  if(size == 0) {
    return arr[0];
  }

  int min = getMinVal(arr, size - 1);
  if(arr[size] < min) {
    return arr[size];
  }

  return min;
}

/*
Time: O(n)
Space: O(1)
*/
int getMinValUsingTailRecursion(int arr[], int size, int min) {

  if(size == 1) {
    return min;
  }

  if(arr[size - 1] < min) {
    return getMinValUsingTailRecursion(arr, size - 1, arr[size - 1]);
  }

  return getMinValUsingTailRecursion(arr, size - 1, min);
}

Perfect Number

/*
A number is said to be perfect if the sum of its positive divisor, excluding the number itself, is equal to the number
eg:
6 is a perfect number because(1 + 2 + 3 == 6)
28 is a perfect number because(1 + 2 + 4 + 7 + 14 == 28)
*/

#include<stdio.h>

int getSumOfDivisors(int, int);
int getSumOfDivisorsViaTailRecursion(int, int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  int sumOfDivisors = getSumOfDivisors(num, num / 2);
  if(sumOfDivisors == num) {
    printf("%d is a perfect number\n", num);
  } else {
    printf("%d is not a perfect number\n", num);
  }

  // one liner using ternary operator
  printf("%d is %s number\n", num, sumOfDivisors == num ? "a perfect" : "not a perfect");

  sumOfDivisors = getSumOfDivisorsViaTailRecursion(num, num / 2, 0);
  if(sumOfDivisors == num) {
    printf("%d is a perfect number\n", num);
  } else {
    printf("%d is not a perfect number\n", num);
  }
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int getSumOfDivisors(int num, int divisor) {

  if(divisor == 1) {
    return 1;
  }

  if(num % divisor == 0) {
    return divisor + getSumOfDivisors(num, divisor - 1);
  }

  return getSumOfDivisors(num, divisor - 1);
}

/*
Time: O(n)
Space: O(1)
NOTE: In each invocation of the function, only one recursive call will be executed and that recursive call
will be the last one to be executed inside the function. So, both the recursive calls are tail recursive.
i.e. getSumOfDivisorsViaTailRecursion(num, divisor - 1, sum + divisor);
and getSumOfDivisorsViaTailRecursion(num, divisor - 1, sum);
both are tail recursive.
*/
int getSumOfDivisorsViaTailRecursion(int num, int divisor, int sum) {

  if(divisor == 1) {
    return sum + 1;
  }

  if(num % divisor == 0) {
    return getSumOfDivisorsViaTailRecursion(num, divisor - 1, sum + divisor);
  }

  return getSumOfDivisorsViaTailRecursion(num, divisor - 1, sum);
}

Sum Of First N Natural Numbers

/*
Return the sum of First N Natural Numbers
eg:
num = 5,
1 + 2 + 3 + 4 + 5 --> 15 (here, 15 is the sum of first 5 natural numbers)
*/
#include<stdio.h>

int sumOfFirstNnumbers(int);
int sumOfFirstNnumbersViaTailRecursion(int, int);

int main(){
  int num;
  printf("Enter number\n");
  scanf("%d", &num);
  printf("Sum of first N natural numbers is %d\n", sumOfFirstNnumbers(num));
  printf("Sum of first N natural numbers via Tail Recursion is %d\n", sumOfFirstNnumbersViaTailRecursion(num, 0));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int sumOfFirstNnumbers(int num) {

  if(num == 1) {
    return 1;
  }

  return num + sumOfFirstNnumbers(num - 1);
}

/*
Time: O(n)
Space: O(1)
*/
int sumOfFirstNnumbersViaTailRecursion(int num, int sum) {

  if(num == 0) {
    return sum;
  }

  return sumOfFirstNnumbersViaTailRecursion(num - 1, sum + num);
}

Number Of Times Digits Encountered

/* Return the number of times the digit encountered in a number
eg: num = 598799419, digit = 9, o/p -> 4 (4 because digit 9 occurred 4 times)
*/
#include<stdio.h>

int getCountOfDigits(int, int);
int getCountOfDigitsViaTailRecursion(int, int, int);

int main(){
  int num, digit;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("Enter the digit you want to count\n");
  scanf("%d", &digit);
  printf("Number of %d's in %d are %d\n", digit, num, getCountOfDigits(num, digit));
  printf("Number of %d's in %d via Tail Recursion are %d\n", digit, num, getCountOfDigitsViaTailRecursion(num, digit, 0));
  return 0;
}

/*
Time: O(log n)
Space: O(log n)
*/
int getCountOfDigits(int num, int digit) {

  if(num == 0) {
    return 0;
  }

  if((num % 10) == digit) {
    return 1 + getCountOfDigits(num / 10, digit);
  }

  return getCountOfDigits(num / 10, digit);
}

/*
Time: O(log n)
Space: O(1)
*/
int getCountOfDigitsViaTailRecursion(int num, int digit, int count) {

  if(num == 0) {
    return count;
  }

  if((num % 10) == digit) {
    return getCountOfDigitsViaTailRecursion(num / 10, digit, count + 1);
  }

  return getCountOfDigitsViaTailRecursion(num / 10, digit, count);
}

Palindrome Number

/*
Palindrome number is the one which remains the same when it's digits are reversed
eg:
12321 - palindrome number
12323 - not a palindrome number
*/

#include<stdio.h>

int isPalindrome(int, int);

int main(){

  int num;
  printf("Enter a number\n");
  scanf("%d", &num);

  if(isPalindrome(num, 0)) {
    printf("%d is a palindrome number\n", num);
  } else {
    printf("%d is not a palindrome number\n", num);
  }

  // one liner using ternary/conditional operator
  // printf("%d is %s palindrome number\n", num, isPalindrome(num, 0) ? "a" : "not a");
  return 0;
}

/*
Time: O(logn)
Space: O(1)
*/
int isPalindrome(int num, int rev) {

  if(num <= rev) {
    return (rev == num) || (rev / 10 == num);
  }

  return isPalindrome(num / 10, (rev * 10) + (num % 10));
}
/*
(rev / 10 == num) is for odd number of digits.
eg: num = 45654, now the recursive call will terminate when num < rev
i.e. num = 45 and rev = 456, so to truncate the 6 of rev, we use rev / 10 == num.
But this is not required in the case of even number of digits.
Suppose number is 456654, here the recursive call will terminate when num == rev
i.e. x = 456 and rev = 456, so no need to truncate anything here & we can use (rev == num) directly.
*/

Sum Of Proper Divisor

/*
Return the sum of proper divisor.
Proper Divisor of a number is a positive divisor of num which is different from num.
eg:
20 -> 1, 2, 4, 5, 10, but not 20, return their sum(1 + 2 + 4 + 5 + 10 = 22)
55 -> 1, 5, 11, but not 55, return their sum(1 + 5 + 11 = 17)
*/

#include<stdio.h>

int getSumOfProperDiv(int, int);
int getSumOfProperDivViaTailRecursion(int, int, int);

int main(){
  int num;
  printf("Enter a number\n");
  scanf("%d", &num);
  printf("%d\n", getSumOfProperDiv(num, num / 2));
  printf("%d\n", getSumOfProperDivViaTailRecursion(num, num / 2, 0));
  return 0;
}

/*
Time: O(n)
Space: O(n)
*/
int getSumOfProperDiv(int num, int divisor) {

  if(divisor == 1) {
    return 1;
  }

  if(num % divisor == 0) {
    return divisor + getSumOfProperDiv(num, divisor - 1);
  }

  return getSumOfProperDiv(num, divisor - 1);
}

/*
Time: O(n)
Space: O(1)
NOTE: In each invocation of the function, only one recursive call will be executed and that recursive call
will be the last one to be executed inside the function. So, both the recursive calls are tail recursive.
i.e. getSumOfProperDivViaTailRecursion(num, divisor - 1, sum + divisor);
and getSumOfProperDivViaTailRecursion(num, divisor - 1, sum);
both are tail recursive.
*/

int getSumOfProperDivViaTailRecursion(int num, int divisor, int sum) {

  if(divisor == 1) {
    return sum + 1;
  }

  if(num % divisor == 0) {
    return getSumOfProperDivViaTailRecursion(num, divisor - 1, sum + divisor);
  }

  return getSumOfProperDivViaTailRecursion(num, divisor - 1, sum);
}

Greatest Common Divisor(GCD)

/*
GCD using Euclid's Algorithm.
It is an efficient way to find GCD of 2 integers.
It works by continuously computing remainders until 0(zero) is reached. The last non-zero
remainder will be the answer
eg: for 12 and 8, the GCD will be 4
*/

#include<stdio.h>

int gcd(int, int);
int gcdViaTailRecursion(int, int);

int main() {
  int num1, num2;
  printf("Enter the first number\n");
  scanf("%d", &num1);
  printf("Enter the second number\n");
  scanf("%d", &num2);
  printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
  printf("GCD of %d and %d via Tail Recursion is %d\n", num1, num2, gcdViaTailRecursion(num1, num2));
  return 0;
}

/*
Time: O(log(min(m, n)))
Space: O(1)
*/
int gcd(int num1, int num2) {

  while(num2 != 0) {
    int rem = num1 % num2;
    num1 = num2;
    num2 = rem;
  }

  return num1;
}

/*
Time: O(log(min(m, n)))
Space: O(1)
*/
int gcdViaTailRecursion(int num1, int num2) {

  if(num2 == 0) {
    return num1;
  }

  return gcdViaTailRecursion(num2, num1 % num2);
}

Comments (6)