It takes a sizeable amount of time to prepare for a coding interview. There are so many different topics, data structures, and algorithms to go over. Recursion is one of the most important algorithm types. Because it is the basis for so many important algorithms like divide and conquers, graph algorithms, dynamic programming, some tree-based searching and sorting algorithms, and many more. It is unavoidable. So it is important to have some practice before going to a coding interview.

This article will focus on the basic questions on recursion that are very common and popular in basic coding interviews. If you search in Google, you will find most of these questions here and there out there anyway. I am just compiling some of the common patterns of interview questions here for you. You will see a few different patterns of recursive algorithms here.

This article does not guarantee that you will only see these questions. These are some common types and this should give you some good practice!

I will go from easier to harder. This is not a recursion tutorial. I am only providing some practice material here. The solutions will be provided in python as I use python most of the time.

I suggest you try to solve all the questions by yourself first and then see the solution.

Question 1

Write a recursive function that takes a number and returns the sum of all the numbers from zero to that number.

I will call this function ‘cumulative’. If I provide 10 as an input it should return the sum of all the numbers from zero to 10. That is 55.

Here is the python solution:

def cumulative(num):
    if num in [0, 1]:
        return num
    else:
        return num + cumulative(num-1)

Question 2

Write a recursive function that takes a number as an input and returns the factorial of that number.

I am sure we all learned what factorial is. I will name the function ‘factorial’.

Here is the python solution:

def factorial(n):
    assert n >=0 and int(n) == n, 'The number must be a positive integer only!'
    if n in [0,1]:
        return 1
    else:
        return n * factorial(n-1)

Question 3

Write a recursive function that takes a number ‘n’ and returns the nth number of the Fibonacci number.

As a reminder Fibonacci series is the sequence of positive integers that start with 0 and 1 and the rest of the numbers are just the sum of the previous two numbers: 0, 1, 1, 2, 3, 5, 8, 11…

Here is the python solution:

def fibonacci(n):
    if n in [0, 1]:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Question 4

Write a recursive function that takes a list of numbers as an input and returns the product of all the numbers in the list.

If you are not a python user, a list in python is like an array in Java or JavaScript, or PHP.

Here is the python solution:

def productOfArray(arr):
    if len(arr) == 0:
        return 0
    if len(arr) == 1:
        return arr[0]
    else:
        return arr[len(arr)-1] * productOfArray(arr[:len(arr)-1])

Question 5

Write a function that takes a string and returns if the string is a palindrome.

As a reminder, if a string is equal to its reverse, it is called a palindrome. Such as Madam, civic, kayak. If you reverse any of these words they stay the same.

Here is the recursive solution in python:

def isPalindrom(strng):
    if len(strng) == 0:
        return True
    if strng[0] != strng[len(strng)-1]:
        return False
    return isPalindrome(strng[1:-1])

This function returns True if the string is a palindrome and false otherwise.

Question 6

Write a recursive function that takes a string and reverse the string.

If the input is ‘amazing’, it should return ‘gnizama’.

Here is the Python solution:

def reverse(st):
    if len(st) in [0, 1]:
        return st
    else:
        return st[len(st)-1] + reverse(st[:len(st)-1])

Question 7

Write a recursive function that takes an array that may contain more arrays in it and returns an array with all values flattened.

Suppose this is the input array:

[[1], [2, 3], [4], [3, [2, 4]]]

The output should be:

[1, 2, 3, 4, 3, 2, 4]

Here is the python solution:

def flatten(arr):
    res = []
    for i in arr:
        if type(i) is list:
            res.extend(flatten(i))
        else:
            res.append(i)
    return res

Question 8

Write a recursive function that takes an array of words and returns an array that contains all the words capitalized.

If this is the input array:

['foo', 'bar', 'world', 'hello']

The output array should be:

['FOO', 'BAR', 'WORLD', 'HELLO']

Here is the python solution:

def capitalizeWords(arr):
    if len(arr) == 0:
        return []
    else:
        return [arr[0].upper()]+capitalizeWords(arr[1:])

Question 9

Write a recursive function that takes an array and a callback function and returns True if any value of that array returns True from that callback function otherwise returns False.

In this solution, I used the function ‘isEven’ as a callback function that returns True if a number is even number and returns False otherwise.

Here is the callback function:

def isEven(num):
    if num%2==0:
        return True
    else:
        return False

Our main recursive function should return True if even one element of the input array returns True from the ‘isEven’ function and False otherwise. Here is an array:

[1, 2, 3, 5]

The recursive function should return True here because this array has one element that is an even number.

Here is the python solution:

def anyEven(arr, cb):
    if len(arr) == 0:
        return False
    if cb(arr[0]):
        return True
    return anyEven(arr[1:], cb)

Question 10

Write a recursive function that will return the sum of all the positive numbers in a dictionary which may contain more dictionaries nested in it.

Here is an example:

obj = {
  "a": 2,
  "b": {"x": 2, "y": {"foo": 3, "z": {"bar": 2}}},
  "c": {"p": {"h": 2, "r": 5}, "q": 'ball', "r": 5},
  "d": 1,
  "e": {"nn": {"lil": 2}, "mm": 'car'}

This should return 10. Because this dictionary contains five 2s and no other even numbers.

Here is the python solution:

def evenSum(obj, sum=0):
    for k in obj.values():
        if type(k) == int and k%2 ==0:
            sum += k
        elif isinstance(k, dict):
            sum += evenSum(k, sum=0)
    return sum

Conclusion

It will take a lot of practice to become good at recursion. But this is a good idea to have a look at these problems before going to an interview. Nobody can guarantee the interview questions but preparing different patterns of coding questions is the key. But whatever interviews I faced till now, they never gave me any very hard problems. They typically ask questions to test the knowledge and the overall approach towards a problem.

Feel free to follow me on Twitter and like my Facebook page.