adamscott adamscott - 1 month ago 15
Ruby Question

Ruby Fibonacci Example

class Fibonacci
def calc(n)
return n if n < 2
return calc(n - 1) + calc(n - 2)
end
end

puts Fibonacci.new.calc(40)
>> 102334155


I am trying to make sense of this program. I understand it is recursively calling the calc method twice if it is not 0 or 1, but I don't understand how it is working to get the correct number for the sequence.

I know this is my inexperience showing, but can someone explain to me how this is calculating the fib sequence correctly? It's just not clicking for me.

Answer

When you are having trouble understanding what code is doing, you may have to resort to salting it with puts statements. For recursions it's also helpful to vary indentation to show when a method calls itself and when a method returns. Here is one way you might do that for your code.

INDENT = 4
@tabs = 0

def calc(n)
  pr_indent
  puts "entered calc(#{n})"
  if n < 2
    pr_indent
    puts "returning n=#{n}"
    @tabs -= 1
    return n
  end
  pr_indent
  puts "calling calc(#{n-1})"
  @tabs += 1
  m1 = calc(n-1)
  pr_indent
  puts "calc(#{n-1}) returned m1=#{m1} to calc(#{n})"
  pr_indent
  puts "calling calc(#{n-2})"
  @tabs += 1
  m2 = calc(n-2)
  pr_indent
  puts "calc(#{n-2}) returned m2=#{m2} to calc(#{n-1})"
  pr_indent
  puts "returning m1+m2=#{m1+m2}"
  @tabs -= 1
  m1+m2
end

def pr_indent
  print "#{' '*(@tabs*INDENT)}"
end

Now execute

calc(4)

causing the following to be printed. I will not provide running comments at it should be self-explanatory when you read what is printed as you step through the code.

entered calc(4)
calling calc(3)
    entered calc(3)
    calling calc(2)
        entered calc(2)
        calling calc(1)
            entered calc(1)
            returning n=1
        calc(1) returned m1=1 to calc(2)
        calling calc(0)
            entered calc(0)
            returning n=0
        calc(0) returned m2=0 to calc(1)
        returning m1+m2=1
    calc(2) returned m1=1 to calc(3)
    calling calc(1)
        entered calc(1)
        returning n=1
    calc(1) returned m2=1 to calc(2)
    returning m1+m2=2
calc(3) returned m1=2 to calc(4)
calling calc(2)
    entered calc(2)
    calling calc(1)
        entered calc(1)
        returning n=1
    calc(1) returned m1=1 to calc(2)
    calling calc(0)
        entered calc(0)
        returning n=0
    calc(0) returned m2=0 to calc(1)
    returning m1+m2=1
calc(2) returned m2=1 to calc(3)
returning m1+m2=3

and calc(4) returns 3.

Comments