Implementation detail matters

Take a look at the following fibonacci method implemented via recursion.

def fibonacci(n)
  return 1 if n == 1
  return 1 if n == 2
  
  fibonacci(n-1) + fibonacci(n-2)
end

n = gets.chomp.to_i
puts fibonacci(n)

Assuming that about one billion operations can be handled in one second, the above algorithm will take more than a second once n goes over 30. This is because the time complexity for this algorithm is O(2^N).

Here’s the same method but implemented with a tail recursion.

def fibonacci(n, a, b)
  return b if n == 1
  
  temp = a
  a = b
  b += temp
  
  fibonacci(n-1, a, b)
end

n = gets.chomp.to_i
puts fibonacci(n, 0, 1)

Surprisingly, this code can handle n > 1000 less than a second, because the time complexity is O(N), a linear.

n = 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

Theoretically, you can set n = 1 billion and this method will produce the result in about a second (although in reality, you’ll get a stack overflow error due to too much of recursive depths).