I'm going to say one word: Recursion. What is your initial reaction? Fear? Excitement? Back in my CS days at uni, they made sure to take caution introducing this subject: "It's so unintuitive!"
In all honesty, though, recursion is just another way to solve iterative problems. We got our
for loops, for 10 times do X. But in recursion, X is to call the same method again. And instead of calling it 10 times, we call it until the conditions are met. What are the conditions? That's for us to determine. Let's look at this sample interview question.
# A diving board must be built to a certain length, # made up only of the given pieces of wood # Given a list of numbers (the lengths of wood) # and a number k, return whether any two numbers # from the list add up to k. # For example, given [10, 15, 3, 7] and k of 17, return # True, since 10 + 7 is 17.
First, let's take a step back and think how we might solve this iteratively. A "brute force" solution, if you will. We'll simply create a nested
for loop where we check every single number against every other number in the list to see if they add to
Start with a method
add_to_k() that takes in two parameters, our
numbers list, and the sum
def add_to_k(numbers, k): pass
for loop will run up through the end of the list minus 1, since by the time we get to the last element, there's nothing behind it to compare it with.
def add_to_k(numbers, k): for i in range(len(numbers) - 1): ...
We'll keep track of the first number we find and call it
current. Next, we want to look at all the numbers in the list behind it. This can be achieved with the nested
for loop as shown.
def add_to_k(numbers, k): for i in range(len(numbers) - 1): current = numbers[i] for j in range(i + 1, len(numbers)): ...
Finally, if the sum of the two numbers is equal to
k, we return True. If we loop through the entire list without finding a match, we return False. Altogether:
def add_to_k(numbers, k): for i in range(len(numbers) - 1): current = numbers[i] for j in range(i + 1, len(numbers)): # print("checking", current, "+", numbers[j]) if current + numbers[j] == k: return True return False
Let's try running the solution.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k(num_list, k)) # -> True
Great. This solution does the trick, but how would we go about solving it recursively?
The method will start the same, taking in the same
k parameters as before.
def add_to_k_recursive(numbers, k): pass
Now, we need to determine our base case(s). With recursion, the best thing to ask is, "What is the simplest case?" Put on your lazy engineer hat; if you had to solve this problem looking at a bunch of different lists, which one would you want to solve? Perhaps a list that only has one item, in which case, the answer must always be false. This is our primary base case. I'm making the length less than 2, since an empty list would also fall into this category.
def add_to_k_recursive(numbers, k): if (len(numbers) < 2): return False
What's next? We have one more base case to write. If a list must be at least 2 long, the easiest case would be...if the list were only 2 long! Then we would simply add the two numbers and see if they equal
k. In the case that we don't know the length of the list, let's default to checking the first and last number.
def add_to_k_recursive(numbers, k): if (len(numbers) < 2): return False elif numbers + numbers[-1] == k: return True
Now all we have to do is make our recursive case, i.e., the one where we call our method again.
Let's think about it. Our list is
[10, 15, 3, 7], and we're looking for numbers that sum to 10. Obviously, the length is longer than 2, so we skip the first
if statement. In the
elif, we see that the first and last numbers, 10 and 7, add to 17, which is not 10. So now what?
We'll have to call
add_to_k_recursive() on a smaller list so that the first and last numbers are different. There are two lists we can check:
- Everything but the first value.
- Everything but the last value.
These are, in python:
So, we'll call our method twice, once for each of the two smaller lists. What do we return? Remember that in Python,
or will return the first True value. So, we return one method call or the other.
def add_to_k_recursive(numbers, k): if (len(numbers) < 2): return False elif numbers + numbers[-1] == k: return True else: return add_to_k_recursive(numbers[:-1], k) or add_to_k_recursive(numbers[1:], k)
Running the same code as before should give us the same output of True.
num_list = [10, 15, 3, 7] k = 10 print(add_to_k_recursive(num_list, k))
However, let's look at what's going on under the hood.
We start with the list
[10, 15, 3, 7]. As stated before, the first and last numbers don't add to 10. So, we call the function again on the smaller lists,
[10, 15, 3] and
[15, 3, 7].
Each of those lists will get broken down again, so the second list will get split into
[15, 3] and
[3, 7], the last one returning True. So, True gets returned up the chain of command through the initial instance of our method.
I hope this helped clear up your understanding of recursion. We didn't make the run time any better, since we still have to look at every number about two times, or O(N2) complexity. However, you might look at this solution and find it more elegant. Regardless, recursion is a good trick to have in your bag, especially if you see the words "check all possible combinations" looming in an interview question.
Erik Heikkila is a Teaching Assistant at General Assembly. This blog is not associated with GA.