# Recursion in R

Most technical interviews with companies will ask you to whiteboard code some type of recursive function in your favorite programming language. Although Python seems to be the dominate king in data science, recursion can be a powerful tool in R.

## What is recursion?

Recursive functions call themselves. That is, they break down the problem into the smallest possible components and the function() calls itself within the original function() on each of the smaller components. Afterward, the results are put together to solve the original problem. Let’s take a look at more concrete examples.

## Quicksort

A technical interview will usually ask you to implement some type of sorting function that can be solved using a recursive algorithm. Let’s try implementing quicksort in R:

## Merge Sort

A second sorting algorithm that we can implement using recursion is the Merge Sort. Sorting algorithms are important because they differ in their speed, depending on the nature of the input data. In the case of merge sort, the worst possible outcome for the time it takes to sort the data is n * log(n), where n is the length of your list of numbers.

Like Quicksort, we’re splitting the vector into smaller sub-vectors by halving it until each vector has just one integer. We then merge the vectors back together, this time in order. Let’s tackle this algorithm in R as well.

I found that Rosetta Code already provides a good example, so below is the their public domain code with my comments added to the code for explanation.