[Non-Roblox Question] Lua Fibonacci Sequence Problem Off By 2

Help and Feedback Scripting Support
#25

This is true if you do the summation of values outside of the tail-recursive function. However if your function looked like this:

function f(a, b, maxValue, acc)
    local c = a + b
    if c >= maxValue then
        return acc
    elseif c % 2 == 0 then
        acc = acc + c
    end
    return f(b, c, maxValue, acc)
end

then you can run f(0, 1, 4000000, 0) and get the correct value of 4613732 without ever calculating the same term twice, and without storing a term in memory longer than it used

1 Like
#26

You don’t need recursion or loops to solve a Fibonacci sequence. It can be done in O(1) (aka constant) time. No need for a cache either. This function uses the “golden ratio” phi:

local sqrt5 = 2.2360679775 -- avoid recalculating it every time

local function fibonacci(n)
    return math.round(1.618033988749895 ^ n / sqrt5)
end

Note: math.round() is new in Luau

#27

The problem isn’t calculating the nth term, it’s summing terms on a conditional basis. Because of this, a tail-recursive solution means that you’re never re-calculating fibonacci(n) with the same value twice, and in my implementation you are using a computationally cheaper method to calculate terms

1 Like