The ultimate guide to recursion interviews. Developed by FAANG engineers, practice with real-world C++ problems, interactive code playgrounds, and get interview-ready in just a few hours.

If you’ve ever struggled with solving coding problems using recursion, or if you’ve just got an interview coming up and want to brush up on your knowledge, you’ll definitely find this course helpful.
 
You’ll start with the basics of what recursion is and why it’s important before diving into what it looks like in practice. You’ll see how recursion can help you solve a variety of different math, string, and data structure problems, using interactive code playgrounds you can execute directly in your browser. You’ll have access to detailed explanations and visualizations for each problem to help you along the way.  
 
By the time you’re done, you’ll be able to use what you’ve learned to solve complex real-world problems, and even advance more easily through your interviews at top tech companies.

Recursion for Coding Interviews in 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 `n/2` because all the factors of a number are less than equal to the half of that number. So, we iterate through all the numbers less than equal to `i` to check whether `n` has a factor or not. We use the `%` operator to check for factors of `n`.
    

### Base Case
* We have defined the base cases for the function in the `if` conditions.

  1. In the first `if` condition, *line 6-9*, when `n` is less than equal to $2$, the function returns `n` since $0$ and $1$ are not prime numbers.
 
  2. In the second `if` condition, *lines 11-14*, when `i` is equal to $1$, the function returns $1$. We will need to understand the recursive part of the function to understand this base case. 

  3. In the third `if` condition, *lines 16-19*, if the number has a divisor other than $1$, the function returns $0$. To check for this condition, we use the `%` operator to compute modulo of `n` with the iterator, `i`.

### Recursive Case
* When the `if` condition for one of the base cases does not evaluate to be true,  the function enters the `else` block, *lines 21-24*, where it makes a recursive call.

* In the recursive call, the `isPrime` function is called with the first parameter being `n` and the second parameter being `i-1`. 

* In this case, the recursive calls will be as follows:

  1. The first recursive call will be  `isPrime(13,5)`.

  2.  The second recursive call will be `isPrime(13,4)`. 

  3. The third recursive call will be `isPrime(13,3)`.

  4. The fourth recursive call will be `isPrime(13,2)`.

  5. The fifth recursive call will be `isPrime(13,1)` which is when the second base case condition will be reached since `i==1`. 

* The function will return `1` since `n` is completely divisible by $1$ only.  

  

This lesson provides a detailed review of the solution to the challenge in the previous lesson

Recursion Fundamentals

Recursion with Numbers

Recursion With Strings

Recursion With Arrays

Recursion with Data Structures

Solution Review 2: Check for Prime Number

Understanding the Code

Driver Function