# Inception All Over Again: Recursion, Factorials, And Fibonacci In Ruby

You know in the movie Inception when the characters have a dream inside a dream inside a dream inside a dream ? Well, that’s recursion for you.

In Ruby or any other other programming language, recursion happens when a method calls on itself inside itself. If that’s confusing to you, I have some examples that helped me understand this stuff.

## Solving Factorials Recursively

A factorial is a non-negative integer, which is the product of all the positive integers less than or equal to itself. So, for example, the factorial of 5 is 120 (5 * 4 * 3 * 2 * 1). The factorial of 0 is always 1.

Without using recursion, we would calculate the factorial as follows in Ruby:

```def factorial(n)
(1..n).inject {|product, n| product * n }
end

puts factorial(5) # =&gt; 120
```

Now, here is the factorial method using recursion:

```def factorial(n)
if n == 0
1
else
n * factorial(n-1)
end
end

puts factorial(5) # =&gt; 120
```

So how does the recursive method work? I found it useful to draw it out…

## Solving Fibonacci Recursively

Now, let’s take a look at a bit more complex Fibonacci sequence. The first two numbers in the Fibonacci sequence are 0 and 1, and each of the next numbers is the sum of the previous two. So the sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …. The Fibonacci of 6, for example, is 8, since 8 is the 6th number in the sequence.

Without using recursion, we would calculate the fibonacci number as follows in Ruby (this is only one of many solutions).

```def fibonacci(n)
sequence = []
(0..n).each do |n|
if n &lt; 2
sequence &lt;&lt; n
else
sequence &lt;&lt; sequence[-1] + sequence[-2]
end
end
sequence.last
end

puts fibonacci(6) # =&gt; 8
```

Now, here is how you would do the Fibonacci sequence doing recursion:

```def fibonacci(n)
if n &lt; 2
n
else
fibonacci(n-1) + fibonacci(n-2)
end
end

puts fibonacci(6) # =&gt; 8
```

Here is a diagram of how the fibonacci sequence was calculated using recursion:

Note that it is more efficient to solve the fibonacci sequence non-recursively, since the program has to go through two different recursive branches using the recursive fibonacci solution.

Enjoy the article? Join over 20,000+ Swift developers and enthusiasts who get my weekly updates.

• Yes!

• kevin

I mean I guess, but to be honest I found this whole thing to be rather poignant. Good luck though, seriously.

• Your diagram helped me a lot. I tried to make it a little clearer here http://daniel-sullivan.com/blog/2014/08/19/fibonacci-and-recurrsion/. Thanks again.

• Jberczel

nice article. for the iterative factorial solution, how about using another variable name inside the inject block? it seems little confusing using `n` since it’s also the function argument.

• yellowfour

not sure about ruby, but some languages like lua let you save closures for past parameters. so you don’t have to recalculate each time. for instance, once it has called fibonacci(4), it saves the answer so it doesn’t have to do recursion again.

• Thrynn

This diagram helped me a lot. Thank you!

• Polymath

Thanks for the diagram, now i finally get it!!! Thanks once again.