Flipping the elements of a vector

I wrote 2 different codes for flipiing the elements of a vector.

One of them: halving the vector every recursive case

Other one: changing the positions of outer elements

The first one is much slower than the other one, that is, I tried the vector [1:1e4]. For larger vectors [1:1e6] the second one gives "Out of memory. The likely cause is an infinite recursion within the program." error though it is much faster. I could not understand the problem. Can you explain why it happens?

% First one

function flipped = reversal_revisited(v)

n = length(v);

if n <= 1

flipped = v;

else

half = floor(n/2);

left = reversal_revisited(v(1:half));

right = reversal_revisited(v(half+1:end));

flipped = [right, left];

end

end

% Second one

function v = reversal_revisited(v)

v = reversal_recursive(v, 1, length(v));

end

function v = reversal_recursive(v, l, r)

if l < r

temp = v(l);

v(l) = v(r);

v(r) = temp;

v = reversal_recursive(v, l + 1, r - 1);

else

return;

end

end

For the vector: [1:1e4]

The first one:

The second one:

For the vector: [1:1e6]

The first one:

The second one:

[Yelaman Baidol]

The strange thing is that I checked with "profile" that for the first one recursive funciton called almost the same as the vector size; however; for the second one function called half the size of the vector.

Answer 1

[Matt J]

First of all, I hope it is clear that you would never really flip a vector using either of the functions you've created. You would just use flip.

The difference you see is because the first algorithm requires O(log(N)) recursions and therefore consumes O(Nlog(N)) memory. The second version, however, requires O(N) recursions and therefore consumes O(N^2) memory, which will be a problem for N=1e6. I don't really see why you would use recursion in the second case. A simple for-loop is easy enough:

reversal_SecondOne(1:7)

ans = 1×7

7 6 5 4 3 2 1

function v=reversal_SecondOne(v)

 for i=1:floor(numel(v)/2)
    
     [v(i),v(end+1-i)]=deal(v(end+1-i), v(i));
     
 end

end

Answer 2

[Bruno Luong]

"For larger vectors [1:1e6] the second one gives "Out of memory. The likely cause is an infinite recursion within the program." error though it is much faster. I could not understand the problem. Can you explain why it happens? "

Yes, the first one you split the array in 2 half, each have half size. So the maximum depth of the recursion is about

log2(1e6)

ans = 19.9316

The depth is 20.

In the second case, you reduces the length by 2, so there is

1e6/2

ans = 500000

recusrive calls is the stack, just you get error you see.

I can't remember the default stack size MATLAB allows, but in practice I wouldn't do any recursion beyond 100 of depth.