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) # => 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) # => 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 < 2 sequence << n else sequence << sequence[-1] + sequence[-2] end end sequence.last end puts fibonacci(6) # => 8
Now, here is how you would do the Fibonacci sequence doing recursion:
def fibonacci(n) if n < 2 n else fibonacci(n-1) + fibonacci(n-2) end end puts fibonacci(6) # => 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.