Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in C++

Solution Review 2: Check for Prime Number

Explore how to implement a recursive function in C++ to check for prime numbers. Understand the role of base cases and recursive calls while iterating through factors, improving your skills in recursion with numbers.

We'll cover the following...
C++
#include <iostream>
using namespace std;
bool isPrime(int n, int i)
{
  // first base case
  if (n<2)
  {
    return 0;
  }
  // second base case
  if(i==1)
  {
    return 1;
  }
  // third base case
  if (n%i==0)
  {
    return 0;
  }
  // recursive case
  else
  {
    isPrime(n,i-1);
  }
}
int main() {
  int input= 13;
  bool result= isPrime(input,input/2);
  // prints if number is prime
  if (result==1)
  {
    cout<<input<<" is a prime number.";
  }
  //prints if number is not prime
  else
  {
    cout<<input<<" is a not a prime number.";
  }
}

Understanding the Code

In the code above, the function isPrime is a recursive function as it makes a recursive call in the function body. Below is an explanation of the above code:

Driver Function

  • In the main() code, we have defined an integer variable, named input, and boolean variable, named result.

  • result stores the output of the isPrime function.

  • The first parameter in the isPrime function is the number to be tested, named input, and the second parameter, input/2, is half of the number to be tested.

  • lines 31-34 and lines 36-39 prints the type, prime or not prime, of the number based on the value of result.

Recursive Function

  • The return type of this function is bool since we want to check if the number is prime or not and it takes the two integers, n and i, as input parameters.

  • n is the number to be tested and i is the iterator and has the initial value of n/2 when the function is called in the main code.

  • i has the initial value of ...