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.

Enjoy the article? Join over 17,500+ 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.