Recursion & Memoization Problems · Coding Interview Guide

Challenges on this page

Introduction to Recursion
Memoization
Recursion Homework Example Problems
Recursion Problem 1 - Reverse String
Recursion Problem 2 - String Permutation
Recursion Problem 3 - Fibonacci Sequence
Recursion Problem 4 - Coin Change

01Introduction to Recursion

Source notebook: Introduction to Recursion.ipynb

Introduction to Recursion

In this lecture we will go over the basics of Recursion.

What is Recursion?

There are two main instances of recursion. The first is when recursion is used as a technique in which a function makes one or more calls to itself. The second is when a data structure uses smaller instances of the exact same type of data structure when it represents itself. Both of these instances are use cases of recursion.

Recursion actually occurs in the real world, such as fractal patterns seen in plants!

Why use Recursion?

Recursion provides a powerful alternative for performing repetitions of tasks in which a loop is not ideal. Most modern programming languages support recursion and recursion serves as a great tool for building out particular data structures.

We'll start this introduction with an example of recursion- a factorial function.

Factorial Example

In this part of the lecture we will explain recursion through an example excercise of creating the factorial function. The factorial function is denoted with an exclamation point and is defined as the product of the integers from 1 to n. Formally, we can state this as:

$$ n! = n·(n-1)·(n-2)... 3·2·1 $$

Note, if n = 0, then n! = 1. This is important to take into account, because it will serve as our base case.

Take this example: $$4! = 4 · 3 · 2 · 1 = 24. $$ So how can we state this in a recursive manner? This is where the concept of base case comes in.

Base case is a key part of understanding recursion, especially when it comes to having to solve interview problems dealing with recursion. Let's rewrite the above equation of 4! so it looks like this:

$$ 4! = 4 · (3 · 2 · 1) = 24 $$

Notice that this is the same as:

$$ 4! = 4 · 3! = 24 $$

Meaning we can rewrite the formal recursion definition in terms of recursion like so:

$$ n! = n·(n−1)!$$

Note, if n = 0, then n! = 1. This means the base case occurs once n=0, the recursive cases are defined in the equation above. Whenever you are trying to develop a recursive solution it is very important to think about the base case, as your solution will need to return the base case once all the recursive cases have been worked through. Let's look at how we can create the factorial function in Python:

Python

def fact(n):
    '''
    Returns factorial of n (n!).
    Note use of recursion
    '''
    # BASE CASE!
    if n == 0:
        return 1
    
    # Recursion!
    else:
        return n * fact(n-1)

Let's see it in action!

Python

fact(5)

Output

Note how we had an if statement to check if a base case occured. Without it this function would not have successfully completed running. We can visualize the recursion with the following figure:

Python

from IPython.display import Image
from IPython.core.display import HTML 
Image(url= 'http://faculty.cs.niu.edu/~freedman/241/241notes/recur.gif')

Output

<IPython.core.display.Image object>

We can follow this flow chart from the top, reaching the base case, and then working our way back up.

Conclusion

Recursion is a powerful tool, but it can be a tricky concept to implement. In the next lectures we will go over a few more example problems for recursion. Then afterwards you'll be faced with some real interview questions involving recursion!

02Memoization

Source notebook: Memoization.ipynb

Memoization

In this lecture we will discuss memoization and dynamic programming. For your homework assignment, read the Wikipedia article on Memoization, before continuing on with this lecture!

Memoization effectively refers to remembering ("memoization" -> "memorandum" -> to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. We'll use this in some of the interview problems as improved versions of a purely recursive solution.

A simple example for computing factorials using memoization in Python would be something like this:

Python

# Create cache for known results
factorial_memo = {}

def factorial(k):
    
    if k < 2: 
        return 1
    
    if not k in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
        
    return factorial_memo[k]

Python

factorial(4)

Output

Note how we are now using a dictionary to store previous results of the factorial function! We are now able to increase the efficiency of this function by remembering old results!

Keep this in mind when working on the Coin Change Problem and the Fibonacci Sequence Problem.

We can also encapsulate the memoization process into a class:

Python

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

Then all we would have to do is:

Python

def factorial(k):
    
    if k < 2: 
        return 1
    
    return k * factorial(k - 1)

factorial = Memoize(factorial)

Try comparing the run times of the memoization versions of functions versus the normal recursive solutions!

03Recursion Homework Example Problems

Source notebook: Recursion Homework Example Problems - SOLUTIONS.ipynb

Recursion Homework Problems - Solutions

This assignment is a variety of small problems to begin you getting used to the idea of recursion. They are not full-blown interview questions, but do serve as a great start for getting your mind "in the zone" for recursion problems.

Here are the solutions with some simple explanations to the problems.

Problem 1

Write a recursive function which takes an integer and computes the cumulative sum of 0 to that integer

For example, if n=4 , return 4+3+2+1+0, which is 10.

This problem is very similar to the factorial problem presented during the introduction to recursion. Remember, always think of what the base case will look like. In this case, we have a base case of n =0 (Note, you could have also designed the cut off to be 1).

In this case, we have: n + (n-1) + (n-2) + .... + 0

Check out a sample solution:

Python

def rec_sum(n):
    
    # Base Case
    if n == 0:
        return 0
    
    # Recursion
    else:
        return n + rec_sum(n-1)

Python

rec_sum(4)

Output

Problem 2

Given an integer, create a function which returns the sum of all the individual digits in that integer. For example: if n = 4321, return 4+3+2+1

Python

def sum_func(n):
    # Base case
    if len(str(n)) == 1:
        return n
    
    # Recursion
    else:
        return n%10 + sum_func(n/10)

Python

sum_func(4321)

Output

Hints:

Python

# You'll neeed to use modulo
4321%10

Output

Python

4321 / 10

Output

We'll need to think of this function recursively by knowing that: 4502 % 10 + sum_func(4502/10)

Problem 3

Note, this is a more advanced problem than the previous two! It aso has a lot of variation possibilities and we're ignoring strict requirements here.

Create a function called word_split() which takes in a string phrase and a set list_of_words. The function will then determine if it is possible to split the string in a way in which words can be made from the list of words. You can assume the phrase will only contain words found in the dictionary if it is completely splittable.

For example:

Python

word_split('themanran',['the','ran','man'])

Output

['the', 'man', 'ran']

Python

word_split('ilovedogsJohn',['i','am','a','dogs','lover','love','John'])

Output

['i', 'love', 'dogs', 'John']

Python

word_split('themanran',['clown','ran','man'])

Output

[]

Python

def word_split(phrase,list_of_words, output = None):
    '''
    Note: This is a very "python-y" solution.
    ''' 
    
    # Checks to see if any output has been initiated.
    # If you default output=[], it would be overwritten for every recursion!
    if output is None:
        output = []
    
    # For every word in list
    for word in list_of_words:
        
        # If the current phrase begins with the word, we have a split point!
        if phrase.startswith(word):
            
            # Add the word to the output
            output.append(word)
            
            # Recursively call the split function on the remaining portion of the phrase--- phrase[len(word):]
            # Remember to pass along the output and list of words
            return word_split(phrase[len(word):],list_of_words,output)
    
    # Finally return output if no phrase.startswith(word) returns True
    return output

Conclusion

Alright, so now that we've seen a few examples, let's dive in to the interview practice problems!

04Recursion Problem 1 - Reverse String

Source notebook: Recursion Problem 1 - Reverse String - SOLUTION.ipynb

Reverse a String

This interview question requires you to reverse a string using recursion. Make sure to think of the base case here.

Again, make sure you use recursion to accomplish this. Do not slice (e.g. string[::-1]) or use iteration, there muse be a recursive call for the function.

Solution

In order to reverse a string using recursion we need to consider what a base and recursive case would look like. Here we've set a base case to be when the length of the string we are passing through the function is length less than or equal to 1.

During the recursive case we grab the first letter and add it on to the recursive call.

Python

def reverse(s):
    
    # Base Case
    if len(s) <= 1:
        return s

    # Recursion
    return reverse(s[1:]) + s[0]

Python

reverse('hello world')

Output

'dlrow olleh'

Test Your Solution

Run the cell below to test your solution against the following cases:

string = 'hello'
string = 'hello world'
string = '123456789'

Python

'''
RUN THIS CELL TO TEST YOUR FUNCTION AGAINST SOME TEST CASES
'''

from nose.tools import assert_equal

class TestReverse(object):
    
    def test_rev(self,solution):
        assert_equal(solution('hello'),'olleh')
        assert_equal(solution('hello world'),'dlrow olleh')
        assert_equal(solution('123456789'),'987654321')
        
        print 'PASSED ALL TEST CASES!'
        
# Run Tests
test = TestReverse()
test.test_rev(reverse)

Output

PASSED ALL TEST CASES!

Extra Notes

The "trick" to this question was thinking about what a base case would look like when reversing a string recursively. It takes a lot of practice to be able to begin thinking like this, so don't worry if you're struggling! However it is important to fully understand the solution!

Good Job!

05Recursion Problem 2 - String Permutation

Source notebook: Recursion Problem 2 - String Permutation- SOLUTION.ipynb

String Permutation

Problem Statement

Given a string, write a function that uses recursion to output a list of all the possible permutations of that string.

For example, given s='abc' the function should return ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Note: If a character is repeated, treat each occurence as distinct, for example an input of 'xxx' would return a list with 6 "versions" of 'xxx'

Fill Out Your Solution Below

Let's think about what the steps we need to take here are:

Iterate through the initial string – e.g., ‘abc’.

For each character in the initial string, set aside that character and get a list of all permutations of the string that’s left. So, for example, if the current iteration is on 'b', we’d want to find all the permutations of the string 'ac'.
Once you have the list from step 2, add each element from that list to the character from the initial string, and append the result to our list of final results. So if we’re on 'b' and we’ve gotten the list ['ac', 'ca'], we’d add 'b' to those, resulting in 'bac' and 'bca', each of which we’d add to our final results.
Return the list of final results.

Let's go ahead and see this implemented:

Python

def permute(s):
    out = []
    
    # Base Case
    if len(s) == 1:
        out = [s]
        
    else:
        # For every letter in string
        for i, let in enumerate(s):
            
            # For every permutation resulting from Step 2 and 3 described above
            for perm in permute(s[:i] + s[i+1:]):
                
                # Add it to output
                out += [let + perm]

    return out

Python

permute('abc')

Output

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Test Your Solution

Python

"""
RUN THIS CELL TO TEST YOUR SOLUTION.
"""

from nose.tools import assert_equal

class TestPerm(object):
    
    def test(self,solution):
        
        assert_equal(sorted(solution('abc')),sorted(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']))
        assert_equal(sorted(solution('dog')),sorted(['dog', 'dgo', 'odg', 'ogd', 'gdo', 'god']) )
        
        print 'All test cases passed.'
        


# Run Tests
t = TestPerm()
t.test(permute)

Output

All test cases passed.

Conclusion

There were two main takeaways from tackling this problem:

Every time we put a new letter in position i, we then had to find all the possible combinations at position i+1 – this was the recursive call that we made. How do we know when to save a string? When we are at a position i that is greater than the number of letters in the input string, then we know that we have found one valid permutation of the string and then we can add it to the list and return to changing letters at positions less than i. This was our base case – remember that we always must have a recursive case and a base case when using recursion!
Another big part of this problem was figuring out which letters we can put in a given position. Using our sample string “abc”, lets say that we are going through all the permutations where the first letter is "c”. Then, it should be clear that the letter in the 2nd and 3rd position can only be either “a” or “b”, because “a” is already used. As part of our algorithm, we have to know which letters can be used in a given position – because we can’t reuse the letters that were used in the earlier positions.

Good Job!

06Recursion Problem 3 - Fibonacci Sequence

Source notebook: Recursion Problem 3 - Fibonacci Sequence - SOLUTION.ipynb

Fibonnaci Sequence

Problem Statement

Implement a Fibonnaci Sequence in three different ways:

Recursively
Dynamically (Using Memoization to store results)
Iteratively

Remember that a fibonacci sequence: 0,1,1,2,3,5,8,13,21,... starts off with a base case checking to see if n = 0 or 1, then it returns 1.

Else it returns fib(n-1)+fib(n+2).

Recursively

The recursive solution is exponential time Big-O , with O(2^n). However, its a very simple and basic implementation to consider:

Python

def fib_rec(n):
    
    # Base Case
    if n == 0 or n == 1:
        return n
    
    # Recursion
    else:
        return fib_rec(n-1) + fib_rec(n-2)

Python

fib_rec(10)

Output

Dynamically

In the form it is implemented here, the cache is set beforehand and is based on the desired n number of the Fibonacci Sequence. Note how we check it the cache[n] != None, meaning we have a check to know wether or not to keep setting the cache (and more importantly keep cache of old results!)

Python

# Instantiate Cache information
n = 10
cache = [None] * (n + 1)


def fib_dyn(n):
    
    # Base Case
    if n == 0 or n == 1:
        return n
    
    # Check cache
    if cache[n] != None:
        return cache[n]
    
    # Keep setting cache
    cache[n] = fib_dyn(n-1) + fib_dyn(n-2)
    
    return cache[n]

Python

fib_dyn(10)

Output

Iteratively

In this solution we can take advantage of Python's tuple unpacking!

Python

def fib_iter(n):
    
    # Set starting point
    a = 0
    b = 1
    
    # Follow algorithm
    for i in range(n):
        
        a, b = b, a + b
        
    return a

Python

fib_iter(23)

Output

Test Your Solution

Run the cell below to test your solutions, simply uncomment the solution functions you wish to test!

Python

"""
UNCOMMENT THE CODE AT THE BOTTOM OF THIS CELL TO SELECT WHICH SOLUTIONS TO TEST.
THEN RUN THE CELL.
"""

from nose.tools import assert_equal

class TestFib(object):
    
    def test(self,solution):
        assert_equal(solution(10),55)
        assert_equal(solution(1),1)
        assert_equal(solution(23),28657)
        print 'Passed all tests.'
# UNCOMMENT FOR CORRESPONDING FUNCTION
t = TestFib()

t.test(fib_rec)
#t.test(fib_dyn) # Note, will need to reset cache size for each test!
#t.test(fib_iter)

Output

Passed all tests.

Conclusion

Hopefully this interview question served as a good excercise in exploring recursion, dynamic programming, and iterative solutions for a single problem! Its good to work through all three because in an interview a common question may just begin with requesting a recursive solution and then checking to se if you can implement the other forms!

07Recursion Problem 4 - Coin Change

Source notebook: Recursion Problem 4 - Coin Change - SOLUTION.ipynb

Coin Change Problem

Note: This problem has multiple solutions and is a classic problem in showing issues with basic recursion. There are better solutions involving memoization and simple iterative solutions.If you are having trouble with this problem (or it seems to be taking a long time to run in some cases) check out the Solution Notebook and fully read the conclusion link for a detailed description of the various ways to solve this problem!

This problem is common enough that is actually has its own Wikipedia Entry! Let's check the problem statement again:

This is a classic recursion problem: Given a target amount n and a list (array) of distinct coin values, what's the fewest coins needed to make the change amount.

For example:

If n = 10 and coins = [1,5,10]. Then there are 4 possible ways to make change:

1+1+1+1+1+1+1+1+1+1
5 + 1+1+1+1+1
5+5
10

With 1 coin being the minimum amount.

Solution

This is a classic problem to show the value of dynamic programming. We'll show a basic recursive example and show why it's actually not the best way to solve this problem.

Make sure to read the comments in the code below to fully understand the basic logic!

Python

def rec_coin(target,coins):
    '''
    INPUT: Target change amount and list of coin values
    OUTPUT: Minimum coins needed to make change
    
    Note, this solution is not optimized.
    '''
    
    # Default to target value
    min_coins = target
    
    # Check to see if we have a single coin match (BASE CASE)
    if target in coins:
        return 1
    
    else:
        
        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:
            
            # Recursive Call (add a count coin and subtract from the target) 
            num_coins = 1 + rec_coin(target-i,coins)
            
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                
                min_coins = num_coins
                
    return min_coins

Let's see it in action.

Python

rec_coin(63,[1,5,10,25])

Output

The problem with this approach is that it is very inefficient! It can take many, many recursive calls to finish this problem and its also inaccurate for non standard coin values (coin values that are not 1,5,10, etc.)

We can see the problem with this approach in the figure below:

Python

from IPython.display import Image
Image(url='http://interactivepython.org/runestone/static/pythonds/_images/callTree.png')

Output

<IPython.core.display.Image object>

Each node here corresponds to a call to the rec_coin function. The label on the node indicated the amount of change for which we are now computng the number of coins for. Note how we are recalculating values we've already solved! For instance 15 is called 3 times. It would be much better if we could keep track of function calls we've already made.

Dynamic Programming Solution

This is the key to reducing the work time for the function. The better solution is to remember past results, that way before computing a new minimum we can check to see if we already know a result.

Let's implement this:

Python

def rec_coin_dynam(target,coins,known_results):
    '''
    INPUT: This funciton takes in a target amount and a list of possible coins to use.
    It also takes a third parameter, known_results, indicating previously calculated results.
    The known_results parameter shoud be started with [0] * (target+1)
    
    OUTPUT: Minimum number of coins needed to make the target.
    '''
    
    # Default output to target
    min_coins = target
    
    # Base Case
    if target in coins:
        known_results[target] = 1
        return 1
    
    # Return a known result if it happens to be greater than 1
    elif known_results[target] > 0:
        return known_results[target]
    
    else:
        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:
            
            # Recursive call, note how we include the known results!
            num_coins = 1 + rec_coin_dynam(target-i,coins,known_results)
            
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                
                # Reset the known result
                known_results[target] = min_coins
                
    return min_coins

Let's test it!

Python

target = 74
coins = [1,5,10,25]
known_results = [0]*(target+1)

rec_coin_dynam(target,coins,known_results)

Output

Test Your Solution

Run the cell below to test your function against some test cases.

Note that the TestCoins class only test functions with two parameter inputs, the list of coins and the target

Python

"""
RUN THIS CELL TO TEST YOUR FUNCTION.
NOTE: NON-DYNAMIC FUNCTIONS WILL TAKE A LONG TIME TO TEST. IF YOU BELIEVE YOU HAVE A SOLUTION
"""

from nose.tools import assert_equal

class TestCoins(object):
    
    def check(self,solution):
        coins = [1,5,10,25]
        assert_equal(solution(45,coins),3)
        assert_equal(solution(23,coins),5)
        assert_equal(solution(74,coins),8)

        print 'Passed all tests.'
        
# Run Test

test = TestCoins()
test.check(rec_coin)

Conclusion and Extra Resources

For homework, read the link below and also implement the non-recursive solution described in the link!

For another great resource on a variation of this problem, check out this link: Dynamic Programming Coin Change Problem