Yesterday was a day of looking back and remember those programs that made you feel like a developer. Poor child….. Note for a future me: If anytime you can go back in time please find me in my college years and beat me to death.
But there’s always “light” in the darkness and I found a little experiment which compares the performance of a recursive function with a dynamic function (using a simple for). I want to try Lua so I decided to rewrite that simple program.
Again I chose Fibonacci to perform this comparison and Lua as the language. A recursive function vs a iterative function.
The plugin that I use for highlight the syntax does not accept Lua, so It’ll look ugly but who cares…. It’ll execute anyway
function fibRecursive(n)
if(n <= 1) then
return n;
else
return fibRecursive(n-1) + fibRecursive(n-2)
end
end
I’ve executed this function trying to return the 40th number of the sequence, and It does in 16.9s. A pretty high time for such a simple task, but It was expected.
The iterative version uses an array of 3 positions, to execute the algorithm, here’s the code.
function fibDynamic(n)
fib = {} --new array
fib[0] = 0; fib[1] = 1;
for i = 2, n do --from i = 2, increasing by 1 (i++)
fib[2] = fib[0] + fib[1]
fib[0] = fib[1]
fib[1] = fib[2]
end
return fib[2]
end
I’ve executed this function trying to return the 500th number and It finishes in 0.1s
And that’s all folks!! A simple comparison between a recursive function and a iterative function. The difference is quite big and the memory usage much better in the iterative version. It takes more time to think the iterative solution, but the performance pays the price.
