Recursion v Iteration

Posted by fakebenjay on June 12, 2017

Earlier this week, I was working on a technical challenge based around the Fibonacci sequence. In it, I was asked to write a method that takes a number, n, as an argument, and returns the number that takes up the nth place in the Fibonacci sequence. And when I say “write a method,” I actually mean “write two methods, one iterative and one recursive.”

Iterative methods are, by definition, repetitive, and in Ruby, that usually means taking a data structure, like an array or a hash, and doing something to each individual element.

In our iterative Fibonacci method, we keep adding new elements to our sequence, determining their values by adding the values of the two preceding elements, until the sequence is n elements long. At that point, we simply return the last element of the sequence and we’re done.

	def looping_fibonacci(n)
		fib_array = [1, 1]

		until fib_array.length == n
			fib_array.push(fib_array[-1] + fib_array[-2])
		end

		return fib_array[-1]
	end

Recursive methods, by definition, are methods that call themselves. For our Fibonacci sequence, recursion works well if its combined with a conditional. If n is equal to 1 or 2, the method will return 1 (because the first two elements of the sequence are 1.) Otherwise, our recursive function will add the values of the two elements preceding number n in the sequence, and it will determine the values of those elements by calling itself with n-1 and n-2 as parameters.

	def recursive_fibonacci(n)
		if n == 1 || n == 2
			return 1
		else
			return recursive_fibonacci(n-1) + recursive_fibonacci(n-2)
		end
	end

While recursion is, on its surface, more elegant looking, it’s quite a bit more expensive computationally. Our iterative Fibonacci simply adds elements to the sequence, one by one, in a fairly linear manner until a certain breakpoint is reached. However, for recursion, the complexity of the method increases exponentially as we increase the value of n. If we want to find the 500th element of the Fibonacci sequence and we call recursive_fibonacci(500), within that method, we have to call and add recursive_fibonacci(499) and recursive_fibonacci(498). And within those methods, we have to call and add recursive_fibonacci(498) and recursive_fibonacci(497), and recursive_fibonacci(497) and recursive_fibonacci(496). And within those methods we have to…………