Performance difference between loop and recursion in fibonacci sequence

조회 수: 5 (최근 30일)
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일
편집: Jan 2021년 9월 18일
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개)

카테고리

Help CenterFile Exchange에서 Loops and Conditional Statements에 대해 자세히 알아보기

제품


릴리스

R2021a

Community Treasure Hunt

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

Start Hunting!

Translated by