MATLAB Answers

Performance difference between loop and recursion in fibonacci sequence

조회 수: 10(최근 30일)
Süleyman citir
Süleyman citir 2021년 9월 18일 18:39
댓글: Süleyman citir 2021년 9월 18일 19:18
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.

채택된 답변

Jan
Jan 2021년 9월 18일 18:59
편집: Jan 2021년 9월 18일 19:00
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.

추가 답변(0개)

제품


릴리스

R2021a

Community Treasure Hunt

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

Start Hunting!

Translated by