MATLAB Answers

Performance difference between loop and recursion in fibonacci sequence

10 views (last 30 days)
Süleyman citir
Süleyman citir on 18 Sep 2021
Commented: Süleyman citir on 18 Sep 2021
Both codes give the first "n" elements of Fibonacci sequence. Question is, what exactly creates such a performance difference (I added below) between recursion and loop. Besides the answer, you can give a link and I can research.
Recursive code:
function y = fibor_upgraded(n)
if n == 1
y = 1;
elseif n == 2
y = [1 1];
else
y = fibor_upgraded(n-1); % first n-1 elements
y = [y y(end-1)+y(end)]; % store & add
end
end
Loop code:
function y=fibor_loop(n)
y = [1 1];
i=3;
while i <= n
y(i)=y(i-2)+y(i-1);
i=i+1;
end
y=y(1:end);
end
To compare them I used tic-toc and I got this result:
tic; fibor_loop(5e4); toc;
Elapsed time is 0.005314 seconds.
tic; fibor_upgraded(5e4); toc;
Elapsed time is 0.418270 seconds.

Accepted Answer

Jan
Jan on 18 Sep 2021
Edited: Jan on 18 Sep 2021
A cleaner version of your loop uses a pre-allocation of the output:
function y = fibor_loop_2(n)
y = zeros(1, n); % Pre-allocation
y(1:2) = 1;
for i = 3:n
y(i) = y(i-2) + y(i-1);
end
end
On my computer (i7, R2018b):
% Elapsed time is 0.006649 seconds. your loop
% Elapsed time is 0.920276 seconds. recursive
% Elapsed time is 0.000695 seconds. cleaned loop, 10 times faster
The iterative growing of an array consumes a lot of resources. See thius example:
x = [];
for k = 1:1e6
x(k) = rand;
end
In each iteration a new array is created with the larger size, the old elements are copied and the new element is inserted. Although the final array needs 1e6*8 Bytes = 1MB only (a double needs 8 bytes), Matlab has to allocate and to copy sum(1:1e6)*8 Bytes, which are more than 4 TB!
A pre-allocation avoids this problem:
x = rand(1, 1e6);
for k = 1:1e6
x(k) = rand;
end
This aoolcates the 8MB directly and no further memory is required.
Calling a function has a remarkable overhead. Testing n for each element, if it equal 1 or 2 are 10e4 comparisons for n=5e4. Of course this takes time also.

More Answers (0)

Products


Release

R2021a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by