adamscott - 1 month ago 15

Ruby Question

`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`

.

Source (Stackoverflow)

Comments