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.