Vector reversal using recursion

Question

I'm supposed to reverse the order of an array. I was asked to break the array into two halves and run two recursive functions on each half.

When I run the function with v=[1 2 3 4 5 6 7 8] the reversal of first half is [4 2 1]. I don't know where the 3 went to.

function v = reversal(v)

N=length(v)
x=mod(N,2)

if x==0
   y=N/2
else
   y=(N+1)/2
end

 v1=v(1:y)


if length(v) > 0 
   v3 = [v1(y) reversal(v1(1:y-1))] 
   v=v3
else
%    v4 = [v(end) reversal(v(y:end-1))] 
%    v=v4

     
end

Why did the 3 drop out?

Answer 1

First off, unless something has dramatically changed in the latest version, concatenation of recursive results is very inefficient in MATLAB. What you would really do is

yrev = y(end:-1:1);

But, it's still a useful learning exercise to do recursion. Because it's a learning exercise and we don't care about performance, we are going to define more local variables than necessary. That way you can step through with the M-file debugger and see all the intermediate results.

You have all the right sort of building blocks, you just haven't combined them systematically.

Here's an annotated solution:

function v = reversal(v)
   N=length(v); % you had this correct, but put a semicolon on the end of a line to avoid spamming the command window with output

   y=ceil(N/2); % midpoint to break input into halves, no need to treat odd and even separately, just round (doesn't much matter whether up or down)
   
   if N > 1  % no need to call length(v) again since it's already stored in N
             % also, only need to recurse if we have multiple elements, since a list of 0 or 1 element is its own reverse
      rev_head = reversal(v(1:y)); % first half, reversed
      rev_tail = reversal(v((1+y):end)); % all not in first half, reversed

      v = [rev_tail rev_head]; % this is the only place that actually does reverse anything
                               % rev_head came from beginning and becomes the new tail
   end
end

If you put a breakpoint on the v = [rev_tail rev_head]; line and run your same test of reversal(1:8), you will see an input of [1 2] become [2 1], [3 4] become [4 3], [1 2 3 4] become [4 3 2 1], [5 6] become [6 5], and so on.

Answer 2

Another option is to work directly on the full vector without dividing it. The function will be more concise and easier to understand. You can still use it on each half separately if required.

function v = reversal(v)
    if length(v) > 1
        v = [v(end) reversal(v(1:end-1))];
    end
end

Testing

v = [1 2 3 4 5 6 7 8];
reversal(v)
     8     7     6     5     4     3     2     1

To work on each half separately, all you want to do is

N = ceil(length(v)/2)
[reversal(v(N+1:end)) reversal(v(1:N))]