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 do we mean by merging alphabetically?

Given two strings that are already in alphabetic order, we can combine them to create a string that is sorted alphabetically and is a combination of the two strings given. For a better understanding, look at the illustration below:



# 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.

Try the code by changing the values of `one` and `two` to see how it works with other strings.

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

string alphabeticMerge(string one, string two) {
     if(one[0]=='\0')
     {
       if(two[0]=='\0'){
         
         return one;
       }
       return two;
     }
  
     else if (two[0]=='\0')
       return one;
   
     else if(one[0] > two[0])
          return two[0] + alphabeticMerge(one,two.substr(1));
  
     return one[0] + alphabeticMerge(one.substr(1), two);
       
   }

int main(){

  string one="adefz";
  string two="bcfgy";
  string answer=alphabeticMerge(one,two);
  cout<<answer<<endl;
}

# Understanding the Code

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.

## Driver Function

The recursive function is called within the driver function so lets first look at what it does, from **line 25 to 31**. 

* Two string variables are declared, `one` and `two` with each having a value that is alphabetically **sorted**. 

* The main method then equates the function call to `alphabeticMerge` to another string variable called `answer`. 

* The `answer` variable is displayed to show the sorted merge of the two sorted strings.

## Recursive Function

Now let’s explain the recursive function; `alphabeticMerge`. This is the code segment from **line 5 to 23** in the snippet above.

### Base Case

* The **first** `if` condition, *on line 6* is a **nested** if which basically sees that if the value of `one` is null then it checks if `two` is also null. If both strings are null, it simply returns `one`. However, if `one` is null but `two` isn't, then it returns the non-empty string, `two`. 

* The first `else if on line 15` condition checks that given, `one` is not null, if `two` is null then simply return `one`.

* These two if conditions form the base case as they terminate the function if either of the requirements are met without any more recursive calls. 

### Recursive Case

* The function takes in **two arguments** both of type *string*. The function also **returns** a string instead of simply modifying the input argument. This time we create a new string and imbed the additional characters to it with each **recursive call**. 

* The second `else if on line 18` condition states that provided both the arguments are not empty, if the first character of `one` is greater than that of `two` then simply return the **first element** of `two` and append the recursive call to the method `alphabeticMerge` to it. This recursive call, takes `one` as it is but only takes the part of `two` that is not already appended in the **return call.**

* Lastly, if both `one` and `two` are not null, and the condition stated above is also not met, then the function makes the same return call but switches the roles of `one` and `two`. 


This lesson will teach you how to merge two already sorted strings so that the resultant string is also sorted

Recursion Fundamentals

Recursion with Numbers

Recursion With Strings

Recursion With Arrays

Recursion with Data Structures

Merging Strings in Alphabetic Order

What do we mean by merging alphabetically?

Implementing the Code

Understanding the Code