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++

The key to transforming iterative code to recursive code is to find the specific lines of code that get transformed between the two implementations. The code below shows the two types of code followed by an explanation. 

# Print all Distinct Letters

Given a string, the code must print all the distinct letters, in the order that they appear. The two implementations of the same code are shown below. First, look through the two codes and spot the differences and then read the explanation to better understand the transformation process.

#include <iostream>
#include <string>

using namespace std;

int main(){
  
  string name="Hello Worldd";
  //The first for loop which iterates over every character
  for(int i=0; i<name.length(); i++){
    int duplicate=0;
    char current = name[i];
    // The second for loop which removes all other duplicate occurences
    for(int j=i+1; j<name.length(); j++){
    
      if(current==name[j]){
      //Removing the duplicate occurence
        duplicate = 1;
        name= name.substr(0,j) + name.substr(j+1,name.length()-1);
      }
    }
    if(duplicate==0){
    cout<<current<<endl;
    }
  }

}

Iterative

#include <iostream>
#include <string>

using namespace std;
//This function replaces the need for two loops
void print(string name, int index){
//Base Case
  if(index==name.length()){return;}
// The second for loop is written as it is
int duplicate =0;
  for(int i=index+1;i<name.length();i++){
    if(name[index]==name[i]){
        name= name.substr(0,i) + name.substr(i+1,name.length()-1);
        duplicate = 1;
      }
  }
  // The index variable removes the need for an outer for loop
  if(duplicate==0){
  cout<<name[index]<<endl;}
  print(name,index+1); // Recursive Case
  
}

int main(){

  string name="Hello Worldd";
  print(name,0);

}

Recursive

* The first step is to identify the **loop** in the iterative code. This loop has *two* features;
  * It will **modify** a variable
  * At the end it will give you an output

In this code, look at **lines 10 to 24**. This encompasses the **two** loops in our case, and the `cout` statement, which is our output. Note that the **modification** happens in the loop from **lines 14 to 21**, so **this** is the loop that we deal with.
* The loop that contains the modification is then transferred into a **function** outside the main body, and becomes the function body, as shown in **lines 11 to 15** in the *recursive code*. 

* The second step is that the **condition** in this loop then becomes the **base case** of the function defined.

Look at **line 14** in the *iterative* code; it sets `j` to a value of 1 greater than the `index` and then continues until it reaches the **length** of `name`. This is the same way the base case on **line 8** checks if the `index` passed is equal to the **length** of `name` and terminates if it is. 

* The third step is to pass the **local** variables as input parameters to the function for modification.

Here, note that not just the *string* `name` is passed to the function when it is declared on **line 6**, but also an *integer* `index` is passed. This is meant to help replace the outer for loop in the iterative code and make the implementation recursive. 

* The `index` is passed to the function `print`, and the function can now *recursively* call upon itself. It does this by simply incrementing the `index` by **1** in each call, as it does on **line 20**. Once the string reaches a point where the base case is met, it will terminate. This eliminates the need for the outer for loop.

* The last step, is that before the recursive call you must print the letter at the `index`. This is done **before** the recursive call, because the recursive call simulates the outer for loop in the iterative code, and in this case the `cout` is written before the next "iteration" or now, the next call. 

> **Note:** Had this function returned a variable or a value, that would have been written **after or within** the recursive call, as a return statement shows the end of the function. This you will see in the following chapters!

This lesson will teach you how to convert iterative code to recursive.

Recursion Fundamentals

Recursion with Numbers

Recursion With Strings

Recursion With Arrays

Recursion with Data Structures

Changing Iterative Code to Recursive

Print all Distinct Letters

Transforming the Code