Recursively reversing large vector efficiently

I am trying to write a code that will recursively compute reverse of given large vector . I have tried 2 codes one simple recursive code and other one iterative reversal code which flips 2 elements in one loop hence efficient

I want to replicate second code below in recursive way how can I approach that? Thank you for your time

% First code with simple recursion that flips end element one by one
function w=reversal_v2(v)
if length(v)==1
    w= v;
else
    w= [v(end),reversal_v2(v(1:end-1))];
end

% Second code with simple recursion that flips end element and first
% element together hence half the required time
b=1:1e4;                         %I/P vector
x=length(b);                     % To get length of vector
a=zeros(x);
for i=1:floor(length(b)/2)        %Loop uses simple for loop and temp to substitute the values
    tmp=b(i);
    a(i)=b(x+1-i);
    a(x+1-i)=tmp;
end

[Louis Bodnar]

should be a=zeros(1,x);

Answer 1

[per isakson]

Five ways to flip a row vector. The last one, reversal_v3(), answers your question. Recursion is by two order of magnitude slower than the for-loop.

v = 1:1e4;
tic,  v(end:-1:1); toc

Elapsed time is 0.000255 seconds.

tic, flip(v); toc

Elapsed time is 0.000254 seconds.

tic, reversal_v2(v); toc

Elapsed time is 0.274852 seconds.

tic, SecondCode(v); toc

Elapsed time is 0.001037 seconds.

tic, reversal_v3(v); toc

Elapsed time is 0.097940 seconds.

function w = reversal_v2(v)
    % First code with simple recursion that flips end element one by one
    if length(v)==1
        w = v;
    else
        w = [v(end),reversal_v2(v(1:end-1))];
    end
end
function a = SecondCode( b )
    % Second code with simple recursion that flips end element and first
    % element together hence half the required time
    % b=1:1e4;          % I/P vector
    x = length(b);      % To get length of vector
    a = zeros(1,x);     % Create row vector            
    % Loop uses simple for loop and temp to substitute the values
    for ii = 1:floor(length(b)/2)   
        tmp=b(ii);
        a(ii)=b(x+1-ii);
        a(x+1-ii)=tmp;
    end
end
function w = reversal_v3(v)
    % ... replicate second code below in recursive way ...
    if length(v) <= 2
        w = flip( v );
    else
        w = [ v(end), v(end-1), reversal_v3(v(1:end-2)) ];
    end
end

[Rayyan Ramrajkar]

Thank you for your elaborate codes and I got the logic need to be implemented.

Regarding for loop vs recursion, I understand that simple loop approach is far more uperior than Recursion, but Recusrsion is must have requirement

Answer 2

[John D'Errico]

An old question with an already good answer. Regardless, it explicitly asks about recursive schemes to flip a vector. And I can think of at least a few such schemes. Some schemes will be faster than others.

Of course, recursion is NEVER a good way to accomplish such a task in MATLAB. You should understand that, even though it may be your assignment, don't get the crazy idea that it is something you should regularly practice. I'd suggest that until you get to the point where you fully understand why recursion is usually a bad thing in MATLAB, you should not be writing recursive codes.

Recursion forces MATLAB build a stack of function calls, and maintain them. The worst case is a Fibonacci recurrence, where we see the basic relation:

F(n) = F(n-1) + F(n-2)

That may look nice, but if each of the lower level calls on the right then calls F as a function again, the stack of calls grows exponentially large. For example,

F(5) = F(4) + F(3)

But then we need

F(4) = F(3) + F(2)

Do you see that we have already called for the value of F(3) twice? The size of the stack should grow as O(phi^n), where phi is the golden constant,

phi = (1+sqrt(5))/2

phi = 1.6180

Anyway, in general, recursion is not an efficient way to do things in MATLAB. Other languages seem to love it. I'd say that MATLAB tolerates recursion, rather than love it.

But, given all that preamble, how would I solve this problem using recursion? There are at least two ways I might do so.

1. Swap the first and last elements of the vector, then call the recursive code on elements 2:end-1.
2. Break the vector into two segments, recursively swapping each of them.

I'm not sure if the essential scheme is clear from that, but I'll give code for each of those schemes, and that should help.

function swappedvec = SwapVecRecur1(vec)
  % uses recursion to flip the sequence of a vector
  
  % we want to make this robust to the vector orientation
  vsize = size(vec);
  
  vec = vec(:); % always assume a column vector
  n = numel(vec);
  if n < 2
    swappedvec = vec;
  elseif n == 2
    swappedvec = [vec(2);vec(1)];
  else
    swappedvec = [vec(n);SwapVecRecur1(vec(2:n-1));vec(1)];
  end
  % just in case vec was a row vector originally
  swappedvec = reshape(swappedvec,vsize);
end

You should see the main idea in this first code lies in the else clause of the if statement.

The second version I can think of uses a bisection like scheme, splitting the size of the vector in half each time.

function swappedvec = SwapVecRecur2(vec)
  % uses recursion to flip the sequence of a vector
  
  % we want to make this robust to the vector orientation
  vsize = size(vec);
  
  vec = vec(:); % always assume a column vector
  n = numel(vec);
  if n < 2
    swappedvec = vec;
  else
    % n >= 2
    nsplit = floor(n/2);
    swappedvec = [SwapVecRecur2(vec(nsplit+1:n));SwapVecRecur2(vec(1:nsplit))];
  end
  % just in case vec was a row vector originally
  swappedvec = reshape(swappedvec,vsize);
end

Again, the important part here lies in the else clause. Do they both work?

vec = primes(15)

vec = 1×6

2 3 5 7 11 13

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

SwapVecRecur1(vec)

ans = 1×6

13 11 7 5 3 2

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

SwapVecRecur2(vec)

ans = 1×6

13 11 7 5 3 2

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

As you can see, both codes work. And while I can surely make each of them better, is one of them inherantly better than the other? The simplest test is to time them both.

vec = 1:10000;
timeit(@() SwapVecRecur1(vec))

ans = 0.0436

timeit(@() SwapVecRecur2(vec))

ans = 0.0115

And here we see the broad stack found in the second code is faster. You can think of the two codes as a tree. Each call of the function to itself grows the first tree one step higher. But in the second code, each time it is called, it makes the base of the tree wider.

Can we go one step further? Perhaps. Consider a ternary splitting of the vector, where each call to the swap tool calls itself THREE times, splitting the vector into 3 parts each time.

function swappedvec = SwapVecRecur3(vec)
  % uses recursion to flip the sequence of a vector
  
  % we want to make this robust to the vector orientation
  vsize = size(vec);
  
  vec = vec(:); % always assume a column vector
  n = numel(vec);
  if n < 2
    swappedvec = vec;
  elseif n==2
    swappedvec = [vec(2);vec(1)];
  else
    % the general case, n > 2
    nsplit1 = floor(n/3);
    nsplit2 = floor(n*2/3);
    swappedvec = [SwapVecRecur3(vec(nsplit2+1:n));SwapVecRecur3(vec(nsplit1+1:nsplit2));SwapVecRecur3(vec(1:nsplit1))];
  end
  % just in case vec was a row vector originally
  swappedvec = reshape(swappedvec,vsize);
end

SwapVecRecur3(1:10)

ans = 1×10

10 9 8 7 6 5 4 3 2 1

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

timeit(@() SwapVecRecur3(vec))

ans = 0.0076

What is the recursion tree depth for each of these caes? In SwapVecRecur1, it will be approximately O(N/2). In SwapVecRecur2, it is O(log2(n)), and in the ternary recursion of SwapVecRecur3, it will be O(log3(N)). Here log3 indicates a log to the base 3.