Performance difference between loop and recursion in fibonacci sequence
显示 更早的评论
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.
2 个评论
Jan
2021-9-18
Omit the command: y=y(1:end); , because it is completely useless.
Süleyman citir
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 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
