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.

[Jan]

Omit the command: y=y(1:end); , because it is completely useless.

[Süleyman citir]

Oh, thanks.

Answer 1

[Jan]

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.

See: https://www.mathworks.com/help/matlab/matlab_prog/techniques-for-improving-performance.html

[Süleyman citir]

Thanks a lot.