# Recursion in Ruby

This article is the counterpart to one I wrote on Recursion in Elixir.

## What is recursion?

Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1: Recurrent Problems.Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

## An example in pseudocode

Let's look at an example in pseudocode and talk about what is happening. We're going to sum all of the numbers in an array.

The usual flow of a recursive function is as follows:

- Perform an operation on the first element (head) of the array.
- Call the same function (hence recursion) with the remaining elements (tail) of array.
- Have a guard clause to stop recursion from happening when we've reached the end.

def sum_arrayif the array is emptyreturn 0elsehead of array + sum_array(tail of array)endend

What happens is sort of like this:

array = [1,2,3,4,5]1 + 2 + 3 + 4 + 51 + 2 + 3 + 91 + 2 + 121 + 1415

## Recursion vs Iteration

In Ruby it is often preferable to avoid recursion and use iteration instead. Ruby (and most imperative programming languages) have very useful language constructs to aid with iterating over data.

Recursion can end up being slower and use more memory than it's iterative counterpart for a number of reasons discussed here in Stack Overflow.

Certain languages, especially functional languages which deal with immutable data (Elixir, Haskell, etc...), don't have language constructs at all to deal with iteration and all of it is performed through recursion. These languages are optimized for recursion using a technique called tail call optimization and also come with handy pattern matching to deal with the head and tail of arrays.

## Why recursion in Ruby?

Despite what I said above, I wanted to see what recursion might look like to solve a number of problems in Ruby. Because Ruby doesn't have an easy way of grabbing the head and tail of an array through pattern matching, I've added a `head_tail`

method to the `Array`

class to aid in this.

class Arraydef head_tailhead, *tail = *self[head, tail]endend

In the array [1,2,3,4,5], the head is 1 and the tail is [2,3,4,5].

## Recursion Examples

### Factorials

Factorials in math are written like `6!`

and are the result of `6 * 5 * 4 * 3 * 2 * 1`

.

def recur_fact(num)if num == 0 || num == 11elsenum * recur_fact(num - 1)endendrecur_fact(6) # 720

Let's look at the same method done in an iterative manner:

def iter_fact(num)if num == 0 || num == 11elsesum = 1num.times do |n|sum *= (n + 1)endsumendenditer_fact(6) # 720

### Fibonacci

I heard a funny definition of Fibonacci that goes like this: "Fibonacci - A problem used to teach recursion in computer science." The first 10 Fibonacci numbers go like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 - The next number is the sum of the previous 2 numbers.

def recur_fib(n)acc = [0, 1]f = ->(acc) {if acc.size == naccelsecur, last = acc.last(2)f.(acc + [cur + last])end}f.(acc)endrecur_fib(10) # 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

### Summing Array

def recur_sum(array)if array.empty?0elsehead, tail = array.head_tailhead + recur_sum(tail)endendrecur_sum([1,2,3,4,5]) # 15

Done iteratively:

def iter_sum(array)sum = 0array.each do |elem|sum += elemendsumenditer_sum([1,2,3,4,5]) # 15

### Mapping Array

def recur_map(array, f)if array.empty?[]elsehead, tail = array.head_tail[f.(head)] + recur_map(tail, f)endendrecur_map([1,2,3,4,5], ->(elem) {elem * elem}) # [1, 4, 9, 16, 25]

Done iteratively:

def iter_map(array, f)new_array = []array.each do |elem|new_array << f.(elem)endnew_arrayenditer_map([1,2,3,4,5], ->(elem) {elem * elem}) # [1, 4, 9, 16, 25]

### Reducing Array

def recur_reduce(array, acc, f)if array.empty?accelsehead, tail = array.head_tailrecur_reduce(tail, f.(acc, head), f)endend# Joinrecur_reduce(["Leigh", "Christopher", "Halliday"], "", ->(r, elem) {"#{r} #{elem}".strip}) # "Leigh Christopher Halliday"# Sumrecur_reduce([1,2,3,4,5], 0, ->(r, elem) {r + elem}) # 15# Longest Stringrecur_reduce(["Leigh", "Christopher", "Halliday"], "", ->(r, elem) {r.length > elem.length ? r : elem}) # "Christopher"# Countrecur_reduce(["Leigh", "Christopher", "Halliday"], 0, ->(r, elem) {r + 1}) # 3# Maprecur_reduce([1,2,3,4,5], [], ->(r, elem) {r + [elem * elem]}) # [1, 4, 9, 16, 25]