Project: Recursion

Ruby Course

Warmup: Fibonacci

The Fibonacci Sequence, which sums each number with the one before it, is a great example of a problem that can be solved recursively.

Assignment 1

  1. Using iteration, write a method #fibs which takes a number and returns an array containing that many numbers from the Fibonacci sequence. Using an example input of 8, this method should return the array [0, 1, 1, 2, 3, 5, 8, 13].
  2. Now write another method #fibs_rec which solves the same problem recursively.

Understanding recursive Fibonacci

Did you figure it out? Congratulations! But do you really understand what is taking place? If you need some help understanding what’s going on with this method, give Khan Academy’s Stepping Through Recursive Fibonacci Function video a watch. If you prefer to read, Recursive Fibonnaci Explained is also very helpful!

Project: merge sort

We spent some time early on dealing with sorting (e.g. bubble sort). Now it’s time to take another look at sorting with Merge Sort, a type of sort that lends itself well to recursion and can be much faster than bubble sort on the right data sets. You’ll build a method which sorts a given array but uses a “merge sort” method for doing so.

It can be a bit strange to wrap your head around, but just remember you’re “dividing and conquering” the problem.

The Wikipedia article above uses merge sort examples written in C-like code. This code will likely look quite different from what you’re used to. Don’t waste time trying to understand the specifics of the language, and just focus on the idea it is trying to get across.

Background viewing

The first step is to actually understand what the merge sort algorithm is doing:

  1. Check out this introductory video from Harvard’s CS50x course.
  2. Check out this more detailed video explanation by David J. Malan (watch only until 1:58:33).
  3. Merge Sort – How it Works part 1 and Merge Sort – How it Works part II on YouTube give you a more formal look at this problem if you’re still unclear.
  4. (Optional) Play with this Merge Sort Visualizer to get a better feel for exactly what is happening during a Merge Sort.

Assignment 2

  1. Build a method #merge_sort that takes in an array and returns a sorted array, using a recursive merge sort methodology. An input of [3, 2, 1, 13, 8, 5, 0, 1] should return [0, 1, 1, 2, 3, 5, 8, 13], and an input of [105, 79, 100, 110] should return [79, 100, 105, 110].
  2. Tips:
    1. Think about what the base case is and what behavior is happening again and again and can actually be delegated to someone else (e.g. that same method!).
    2. It may be helpful to check out the background videos again if you don’t quite understand what should be going on.

Additional resources

This section contains helpful links to related content. It isn’t required, so consider it supplemental.

Support us!

The Odin Project is funded by the community. Join us in empowering learners around the globe by supporting The Odin Project!