### Introduction

Use what you have learnt about recursion so far to tackle two classic problems that can leverage recursion: Fibonacci and Merge Sort.

#### Fibonacci

The Fibonacci Sequence, is a numerical sequence where each number is the sum of the two numbers before it. Eg. 0, 1, 1, 2, 3, 5, 8, 13 are the first eight digits in the sequence.

You should already be thinking that perhaps this can be solved iteratively rather than recursively, and you would be correct. Nevertheless generating the sequence recursively is an excellent way to better understand recursion.

To understand how recursion works with Fibonacci watch this step-through video from Khan Academy.

#### Merge sort

A significant part of computer science is dedicated to sorting data. An algorithm which uses the ‘divide and conquer’ approach of recursion is able to reduce a sorting problem to smaller and smaller sub-problems.

Merge sort is one such sorting algorithm, and can be much faster than other algorithms such as bubble sort on the right data sets. Essentially merge sort recurses through an array of unsorted data until it reaches its smallest sub-set, a single item. Of course an array with a single item is considered sorted. Merge sort then merges the single items back together in sorted order. Pretty clever!

To understand what the merge sort algorithm is doing check out these resources:

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

### Assignment

First up create a file and tackle the fibonacci sequence:

- 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 function should return the array`[0, 1, 1, 2, 3, 5, 8, 13]`

. - Now write another method
`#fibs_rec`

which solves the same problem recursively. - Test both versions of your methods by passing in various lengths as arguments.

Hopefully you were able to solve the problem with recursion! If you need some help understanding what’s going on with this function, there are some additional resources linked at the end of this page.

Once you have a firm grasp on solving Fibonacci with recursion, create a new file and work on a merge sort:

- 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]`

.

Tips:

- 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!).
- 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.

- An extensive written JavaScript solution for recursive Fibonacci
- Another look at merge sort
- Visualize and understand the memory allocation for recursive functions
- For more attempts at recursion try the first 5 problems in Project Euler