The Fibonacci Sequence, which sums each number with the one before it, is a great example of a problem that can be solved recursively.
#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]
.#fibs_rec
which solves the same problem recursively. This can be done in just 3 lines (or 1 if you’re crazy, but don’t consider either of these lengths a requirement… just get it done).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!
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 first step is to actually understand what the merge sort algorithm is doing:
#merge_sort
that takes in an array and returns a sorted array, using a recursive merge sort methodology.This section contains helpful links to other content. It isn’t required, so consider it supplemental.
5-6 months
Job Guarantee
1-on-1 Mentorship