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

# What is Depth First Search?

**Depth First Search** is a way to traverse and search all nodes in a graph. This traversal algorithm works in such a way that it starts from the **root node** and then traverses all the way down that **branch** until it reaches the **leaf**, i.e., the last node with no other children, and then **backtracks**. This follows until all nodes are traversed. The illustration below shows a better understanding of `DFS`. 

# Implementing the Code

The code below shows how to do this with recursion. First, let’s see the code, then we can go on to its explanation.

Change the `edges`, the number of nodes `n` to create your own graphs, `g`, and run `DFS` on them for a better understanding.

#include <iostream>
#include <vector>
using namespace std;

class edge{//This class is to create an edge between two nodes
  public:
  int src, dst;
  
  edge(){};
  edge(int s,int d){ // Constructor
    src=s;
    dst=d;
  }
  edge(const edge &e2){//Copy constructor for the edge class
    src = e2.src;
    dst = e2.dst;
  }
};

class graph{ //The graph class which creates the graph

private:
  int nodes;
  vector<edge> edges;
public:
  //Copy constructor for the graph
  graph(int n,vector<edge> e){ 
    nodes=n;
    for(int i=0;i<e.size();i++){
      edges.push_back(e[i]);
    }   
    
  }
  //The Depth First Search function
  void DFS(int v, vector<int>&visited)
  {
    
    if (visited[v]==1){return;}

    else
    {
      cout<<"current node: "<<v<<endl;
      visited[v]=2;
      for(int i=0;i<edges.size();i++)
      {
        if(edges[i].src==v)
        { int dest=edges[i].dst;
          if(visited[dest]==0)
         {
           DFS(dest,visited);
         }
        }
       }
    visited[v]=1;
    }
  }


};


int main() {
  edge one(0,1);
  edge two(0,2);
  edge three(1,3);
  edge four(1,4);
  edge five(2,5);
  
  vector<edge> e;
  e.push_back(one);
  e.push_back(two);
  e.push_back(three);
  e.push_back(four);
  e.push_back(five);
  
  int n=5;
  graph g(n,e);
  vector<int> visit={0,0,0,0,0};
  
  for(int i=0;i<n;i++){
    g.DFS(i,visit);
  }
}

The code above runs a **Depth First Search** on the graph created. The illustration below shows the graph that we use for the code snippet above and the result that the search **should** give. 

The recursive code can be broken down into two parts. The first is the recursive function and the second is the main where the function is called.
Before we dive into the actual `DFS` function let's just quickly go over the two classes `edge` and `graph`. 

* The `edge` class from **lines 5 to 14** simply has two variables; `src` and `dst` that holds the **source** and the **destination** for each edge. The **constructor** simply takes in two `int` variables and assigns their value to its own defined variables; `src` and `dst`. 

* The `graph` class from **lines 16 to 55** simply has two variables; `nodes` which store the total number of vertices in the graph and a vector that contains elements of type **edge**, called `edges`. The *copy constructor* from **line 23 to 29**  creates the graph by copying the parameters passed into the graphs own variables. This class also has the `DFS` function which will run the Depth First Search on the graph. 

Now let's look at the two divisions of code.

## Driver Function

First, let's look at the driver function which calls the recursive code. 

* In the `main` function, **lines 59 to 63**, multiple elements of type `edge` are created.

* On **line 65** a vector `e`, of type `edge`, is created and until **line 70** all the edges are pushed into the vector.

* On **line 72** the `n` variable is created. This is set to 5 which is the number of nodes the graph `g` contains. On line **73** the graph `g` is created. 

* On line **74** a new vector of **ints**, `visit`, is created with all values set to **0** because currently no node has been traversed. This vector is meant to track the nodes visited. 

* The for loop from **lines 76 to 78** simply traverses each node of the graph `g` and calls the `DFS` method on it. 

## Recursive Function

Now that we know how the recursive code is called, let's look at `DFS` in detail. This is the code segment from **lines 31 to 52** in the snippet above. The function takes in two arguments; the vertex `v` which needs to be traversed and a vector of **ints**,   `visited`, which stores whether a node has been traversed or not. 

### Base Case

* The first if condition, on line **34** checks if the vertex `v` being passed to the function has already been visited, i.e., the value at index `v` of the `visited` vector is equal to **1**. If yes, then it simply `returns`. 

### Recursive Case 

* The else condition, from **lines 36 to 52**, contains the recursive code.

* On **line 38** the node that is currently being traversed is displayed, this is done for the user to understand which node is being traversed and that the order of the search is correct.

* On **line 39**, the value at index `v` in `visited` is set to **2**. This implies that while the node is not yet **completely visited**, i.e. **1**, we also cannot set it to **unvisited** which is **0**, hence we set it to a temporary value of **2**. 

* From **lines 40 to 49** is the `for` loop which traverses the `edges` vector in the graph. 
  * The *if condition* on **line 42** states that if the `src` is equal to the vertex `v`, and the `dst` for that edge is **unvisited**, then call the `DFS` method with new parameters; vertex now becomes `dest` which is the `dst` for the edge that satisfied the **first** if condition. 
  * If the condition is not met, then the loop simply continues until the end of `edges` is reached. 

* On **line 50**, once the entire traversal is done, the index `v` of `visited` is set to **1**, which indicates that this node has been traversed.

This lesson will teach you how to write a recursive code for depth first search in graphs.

Recursion Fundamentals

Recursion with Numbers

Recursion With Strings

Recursion With Arrays

Recursion with Data Structures

Depth First Search in Graphs

What is Depth First Search?