Mikk Poles Mikk Poles - 3 months ago 22
Ruby Question

Fibonacci - Recursion - Ruby

There is a program here about fiboannaci, that each time the code branches off again you are calling the fibonacci function from within itself two times.

def fibonacci(number)
if number < 2
number
else
fibonacci(number - 1) + fibonacci(number - 2)
end
end

puts fibonacci(6)


the only thing I understand with fibonacci it's that it adds the number from the previous number. This program was taken from my assignment. And it says "If you take all of those ones and zeros and add them together, you'll get the same answer you get when you run the code."

enter image description here

I really tried my best to understand how this code works but I failed. Can anyone out there who is so kind and explain to me in layman's term or in a way a dummy would understand what's happening on this code? I would really appreciate it so much. Please.

Sorry Newbie here.

Answer

This is just the direct 1:1 translation (with a simple twist) of the standard mathematical definition of the Fibonacci Function:

Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-2) + Fib(n-1)

Translated to Ruby, this becomes:

def fib(n)
  return 0 if n.zero?
  return 1 if n == 1
  fib(n-2) + fib(n-1)
end

It's easy to see that the first two cases can be combined: if n is 0, the result is 0, if n is 1, the result is 1. That's the same as saying if n is 0 or 1, the result is the same as n. And "n is 0 or 1" is the same as "n is less than 2":

def fib(n)
  return n if n < 2
  fib(n-2) + fib(n-1)
end

There's nothing special about this, it's the exact translation of the recursive definition of the mathematical Fibonacci function.