The ultimate recursion guide! Master basics, solve real-world problems, and get interview-ready in hours with FAANG engineers’ proven strategies.

If you’ve ever struggled with solving coding problems using recursion, or if you need to brush up your recursion skills for an interview, this course is for you! We will start with the basics of recursion before we practice solving actual coding problems. You’ll have access to detailed explanations and visualizations for each problem to help you along the way.

By the time you have completed this course, you’ll be able to use all the concepts of recursion to solve complex, real-world problems. We hope that this course will help you ace all the recursion related questions during interviews at top tech companies!

Recursion for Coding Interviews in Python

def balanced(testVariable, startIndex = 0, currentIndex = 0) :
  # Base case1 and 2
  if startIndex == len(testVariable) : 
    return currentIndex == 0

  # Base case3
  if currentIndex < 0 : # A closing bracket did not find its corresponding opening bracket
    return False

  # Recursive case1
  if testVariable[startIndex] == "(" : 
    return  balanced(testVariable, startIndex + 1, currentIndex + 1)

  # Recursive case2
  elif testVariable[startIndex] == ")" : 
    return  balanced(testVariable, startIndex + 1, currentIndex - 1)

# Driver Code
testVariable = ["(", "(", ")", ")", "(", ")"]
print(balanced(testVariable))

## Explanation
Our task is to read an array of parentheses from left to right and decide whether the symbols are balanced. 

To solve this problem, notice that the most recent opening parenthesis must match the following closing parenthesis. The first opening bracket processed will be saved until the very last bracket is processed to find its corresponding closing bracket. 

> Closing brackets match opening brackets in the **reverse order** of their appearance, meaning that they match from the **inside out**. This is a clue that recursion can be used to solve this problem.

Let's investigate the code snippet above. 

The two variables `startIndex` and `currentIndex` are important to note. `startIndex` traverses the whole array. In each **recursive call**, it moves to the next element in the array. It also checks whether or not we have reached the **end** of the array.

The `currentIndex` examines if each **opening bracket** has a corresponding **closing bracket**. If we encounter a closing bracket `currentIndex` is decreased by $1$ and if we encounter an opening bracket it is increased by $1$. If the `currentIndex` does not reach $0$ at the end of the traversal, we return `False`.

### Conditions of the array:
Our array may satisfy 5 conditions: 

1. `startIndex` == `len(testVariable)` and `currentIndex == 0`
   * In this situation, the `startingIndex` has successfully traversed the whole array and the `currentIndex` has matched every starting bracket to a closing bracket. The array is, therefore, pointing at index $0$. We return `True` for this situation.

2. `startIndex` == `len(testVariable)` and `currentIndex != 0`
   * In this situation, the `startingIndex` has traversed the whole array, but the `currentIndex` has **not** found a matching **closing bracket** for a **starting bracket**. We return `False` for this situation.

3. `currentIndex < 0`
   * In this situation, we encountered no **opening bracket** for a **closing bracket** while traversing the array. Since all the closing brackets must match opening brackets in the **reverse order** of their appearance, this situation returns `False`.

 > These $3$ conditions are our **base cases**.

4. `testVariable[startIndex] == "("`
   * An opening bracket is found, so we increase both the `startIndex` and `currentIndex` and call the function `balanced(testVariable, startIndex + 1, currentIndex + 1)`

5. `testVariable[startIndex] == ")"`
   * A closing bracket is found, so we increase `startIndex` but decrease `currentIndex` and call the function `balanced(testVariable, startIndex + 1, currentIndex - 1)`

 > Conditions $4$ and $5$ are our **recursive cases**.


Let's take a look at an example:

This review provides a detailed analysis of the solution to determine whether or not an array contains balanced parenthesis.



Recursion Fundamentals

Iteration Vs. Recursion

Recursion with Numbers

Recursion with Strings

Recursion with Arrays

Recursion with Data Structures

Conclusion

Solution Review: Balance Parenthesis

Solution: Using Recursion

Explanation