Recursion is just something that is defined in terms of itself. Applied to computer science, it's a function that calls itself within the function. Then how do we prevent an infinite loop? Well, we used two different types of cases in a recursive function:
- A base case - this is a scenario that doesn't use recursion to arrive at an answer
- A rule that reduces all other cases towards the base case
Let's take a look at an example - the Fibonacci numbers: Here are the first few Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21... We can calculate a Fibonacci number n > 1, by adding the Fibonacci number n - 1 and n - 2. The Fibonacci number 0 is 0, and the Fibonacci number 1 is 1. Let's break this down into a recursive function.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
The if n == 0 and if n == 1 portions of this function are our base cases - these don't require recursion to return an answer. The return fibonacci(n-1) + fibonacci(n-2) portion of this function is our common case - this is the part of the code that uses recursion because the function is defined using the function we're creating. Notice that every time we call this function it is getting closer to the base case - this is necessary to make sure we don't create an infinite loop situation!
Many problems lend themselves to recursion - it's a fundamental part of computer science. There are a number of problems that can be solved by breaking them down into smaller parts until we reach a case where we know the answer (the base case).
Well...we may end up doing a lot of unnecessary work and recursive solutions aren't always the most efficient solution.
Every time we call a new function we add another layer to the call stack. When you call a function it is added to the call stack so that the computer knows where to return control after the completion of the function. Since we're calling fibonacci twice every time we call fibonacci (until we hit the base case) we're adding two layers to the stack each time - that can take up a lot of space.
And we may not need to call all those functions anyway - we're doing a lot of extra work. Take a look at how many times we call fibonacci(1) and fibonacci(0) just to calculate fibonacci(5):
That's a lot of calls just to calculate the base case! We're looking at nearly a O(2^n) runtime! How can we improve the runtime? What if we saved the values that we've already calculated? This technique is called memoization.
For this example we're going to use a hashmap to store the values that we've calculated before.
memo = {}
def fibonacci(n):
if n < 2:
return n
if n in memo:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo[n] = result #save the calculated result!
return result
Now let's look at the function calls we need:
This is much better - now there are only about 2n nodes in the tree, so we've brought our runtime down to O(n). We are still adding additional functions to the call stack though. Is there something we can do about this?
Did you know that every recursive function can be re-written iteratively using a loop? It's true, though the code for an iterative solution may be more complex. Let's try changing our fibonacci function to an iterative one!
When we're solving a problem bottom-up we need to start with what we know which, in this case, are our base cases if n == 1 and if n == 0. So let's start there. We know that after these base cases we'll have to use these numbers, so let's store them in variables.
def fibonacci(n):
first = 0
second = 1
if n == 0:
return first
if n == 1:
return second
Ok, that takes care of the base cases, but what about the common case? Well, we know that the Fibonacci series is the sum of the two previous Fibonacci numbers, so we can add our two base case numbers to get the 3rd in the series, and then add the 2nd to the 3rd to get the 4th, and so on. If you think about it, this is like we're using our memo solution, but when we're building from the bottom up we only need the last two numbers. Let's turn this into code!
def fibonacci(n):
first = 0
second = 1
if n == 0:
return first
if n == 1:
return second
# we're starting at the last base case and continuing until we reach our target
count = 1
while count < n:
first, second = second, first + second
count += 1
return second
And there we have it - a working solution that starts from the bottom (our base case) and runs upward until we've gotten the solution. How is it's runtime? The solution is found by running through every number until we reach the input number, so this is O(n). And since we're only calling this one function we're not adding to the stack space! Awesome!
Thinking recursively can be advantageous as we try to solve problems - many problems can be broken down into a common case and one or more base case(s). Once you can break down the problem in that way it can be relatively easy to create a recursive function to solve the problem. Recursive functions have some disadvantages though - they may need lots of repeated work, and they add to the call space. Luckily, we have some techniques to improve this - memoization can be used to reduce repeated work, and working from bottom up doesn't require extra call stack space and reduces repeated work.
Try implementing a solution to a problem using each of these methods and compare the runtimes!
Write a function that computes the nth Fibonacci number. We consider the zero'th Fibonacci number to be 0 (like many programming languages, we like to start at 0 ;D) and the first Fibonacci number to be 1. Each Fibonacci number after that is the sum of the previous two numbers. The first 10 fibonacci numbers are: 0, 1, 1, 2, 3, 5, 6, 13, 21, 34 Example: fibonacci(4) ==> 3 fibonacci(6) ==> 8
Write a function that computes the factorial of a given positive integer. The factorial of a number is the product of each number up to and including that number. The factorial of 0 is defined as 1. Example: factorialize(4) computes 1 x 2 x 3 x 4 ==> 24
Write a function to compute the binary representation of a positive decimal integer. The method should return a string. Example: dec_to_bin(6) ==> "110" Example: dec_to_bin(5) ==> "101"
Hint: Repeatedly divide the input by 2 and keep track of the remainder at each step, till the number itself becomes less than 2.
Write a function to determine whether a positive number is happy. A number is happy if it follows a sequence that ends in 1 after following the steps given below: Beginning with the number itself, replace it by the sum of the squares of its digits until either the number becomes 1 or loops endlessly in a cycle that does not include 1. For instance, 19 is a happy number. Sequence: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
Example: is_happy(19) ==> true Example: is_happy(3) ==> false
Given a string, recursively compute a new string where identical, adjacent characters get separated with a "*". Example: insert_star("cac") ==> "cac" Example: insert_star("cc") ==> "c*c"
You are climbing a stair case. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Example: ways_up(2) => 2 (you can do either: 1 step + 1 step OR 2 steps) Example: ways_up(3) => 3 (you can do: 1 step + 1 step + 1 step OR 1 step + 2 steps OR 2 steps + 1 step)
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.
Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
Example 2: coins = [2], amount = 3 return -1
You're given a 2D board which contains an m x n matrix (2D list of characters). Write a method - print_paths that prints all possible paths from the top left cell to the bottom right cell. Your method should return a list of strings, where each string represents a path with characters appended in the order of movement. You're only allowed to move down and right on the board. The order of the string insertion in the list does not matter. Example: Input Board: [[A, X], [D, E]] Output: ["ADE", "AXE"]
We are given the head node root of a binary tree, where every node's value is either a 0 or a 1. Return the same tree where every subtree not containing a 1 has been removed. (Recall that the subtree of a node X is X, plus every node that is a descendant of X.)
Example: Input: [1, null, 0, 0, 1] Output: [1, null, 0, null, 1]
Given a binary search tree, write a function to find the kth smallest element in it. You may assume that k is always valid, 1 <= k <= BST's total elements.
Gist content by Mary Troiani for presentation given at the Algorithms and Technical Interview Study Group - Feb 15, 2018 meetup
This is a part of a series of presentations for Learn Teach Code - Algorithm Study Group