Series:

1. C++ Template Metaprogramming

2. C++ Template Metaprogramming Part 2 of n

This is second in series and I would like to expand on thinking recursively in this part, before than introducing other concepts. For this post lets create a template metaprogram to check if given number is prime or not.

This a standard iterative implementation of checking whether the number is prime:

bool isPrime(int number)
{
if(number < 3)
throw std::invalid_argument("numbers less than 3 cannot be primes");
// any even number cannot be a prime
bool result = number % 2 != 0;
for(int divisor = 2; result && divisor < number/2; ++divisor)
{
result = number % divisor != 0;
}
return result;
}

All highlighted lines have one or more terminating conditions for computation. Line 4 checks for valid input, 7 filters out all even numbers. Line 9 ensures we terminate if have tried a lot of divisors (number/2 is the last thing we want to try) and 11 checks whether number is a multiple of divisor.

Given this it is implement a recursive equivalent with said terminating conditions:

bool isPrime_rimpl(int number, int divisor)
{
return number == divisor ? true :
number % divisor == 0 ? false : isPrime_rimpl(number, ++divisor);
}
bool isPrime_r(int number)
{
if(number < 3)
throw std::invalid_argument("numbers less than 3 cannot be primes");
return isPrime_rimpl(number, 2);
}

Continue reading →

#### Sharing Options: