How to split a vector into smaller vectors to run a recursive function more efficiently

I would like to split a vector of numbers v = 1:1e6 into smaller subvectors, say 20 elements each, and then be able to do a recursive function of reversing the elements in each of those smaller subvectors. Please help!

Answer 1

[Ameer Hamza]

Try this

v = 1:1e6;
n = 20;
v_parts = mat2cell(v, 1, n*ones(1,numel(v)/n));
v_parts_reversed = cellfun(@fliplr, v_parts, 'UniformOutput', 0);

[Gin]

This looks great. But how can I extract each part and run a recursive function on each one? I need to use recursion in my solution.

The idea is to divide the vector into manageable parts that can be run recursively to reverse them separately, and then join them back together. The final answer should be the entire vector reversed. Thank you for your help!

My recursive function:

function out = reversal(in)

if length(in) <= 1

out = in;

else

out = [ reversal(in(2:end)) in(1) ];

end

end

[Ameer Hamza]

If you want to use this function then change the code like this

v = 1:1e6;
n = 20;
v_parts = mat2cell(v, 1, n*ones(1,numel(v)/n));
v_parts_reversed = cellfun(@reversal, v_parts, 'UniformOutput', 0)

function out = reversal(in)
    if length(in) <= 1
        out = in;
    else
        out = [ reversal(in(2:end)) in(1) ];
    end
end

However, it will just reverse each part.

[Gin]

Thank you, sir. You are very kind. I will try this.

Answer 2

[John D'Errico]

Be serious. Why would you want to do this if it were not homework?

Problems like this are just things assigned to students to teach them to write code they should never write in the first place. Sorry, but true. Yes, there are cases where recursion is the perfect solution. However, IMHO, you should never just tell someone to use a tool, unless you also teach them when it is appropriate to use that tool, and when use of that tool is just a bad idea.

For example, were I to hand you a weapon, I would be absolutely sure that you had training to use that weapon safely, and that you have the judgment to use it wisely, and hopefully to never use it at all.

But even if it WERE homework, why would you split it into many vectors of a medium size? Instead, you want to break the vector into TWO smaller vectors. Reverse each of them, then combine the result, but in a reverse order. Do you see this is just a variation of a bisection scheme? Is it a good way to write the code? Are you crazy? For such a simple problem, this would be an insanely poor solution, since many variations of good solutions trivially exist.

Essentially, you can show this scheme will be O(log2(N)), where N is the number of elements in the vector. The problem is, each recursive call itself takes time, function call overhead, etc. Splitting the vector up requires the equivalent of implicit internal loops anyway. And since you can solve the entire problem with ONE such implicit loop, using recursion here is a bad idea. That is:

reversal = @(V) V(end:-1:1);

I don't even need to write an m-file for it, an anonymous function suffices. Does it work? Of course.

reversal(primes(20))

ans = 1×8

19 17 13 11 7 5 3 2

●

But, since this is homework, you can't use such a solution, and it would be wholly inappropriiate for me to do what is obviously homework for you, with no effort shown on your part. But I'll give you a start:

A = V(1:mid);B = V(mid+1:end);

Suppose you now (recursively) reversed each of A and B? Could you them combine them back into one whole vector?

A viable solution would worry about what happens when the vector has length 1, as this is the end case. Good code would probably know how to handle the problem directly for vectors of length 2 also. (Special case the easy problems to avoid deeper levels of recursion when they would be unnecessary.) It would worry about how to handle vectors with an odd number of elements.

[Gin]

Thank you for elaborating on this problem. I have been having a hard time with it. I guess I just need more experience with coding -- recursion and algorithmic complexity in particular. Will get there eventually!

[John D'Errico]

The point I was trying to make was two-fold:

1. Use a simple scheme where you split the vector in half at every level. This is efficient, and trivial to write.
2. Much of of the time, recursion is not an efficient way to write code in MATLAB. You end up with a great deal of overhead, when it will often be simple to write a loop that does the same thing.

Since you have now accepted an answer, I would write the code as:

function Vrev = reversal(V)
   n = numel(V);
   if n <= 1
       Vrev = V;
   elseif n == 2
       % not really necessary, but this will avoid
       % a level of recursion at the end
       Vrev = V([2 1]);
   else
       % n must be at least 3
       mid = floor(n/2);
       Vrev = [reversal(V(mid + 1:end)),reversal(V(1:mid))];
   end
end

reversal(primes(25))
ans =
    23    19    17    13    11     7     5     3     2

Yes, there are cases where recursion is the perfect solution. But I would point out that the common student examples where you are asked to use recursion are things like a factorial (literal insanity to write recursively) Fibonacci numbers (extremely inefficient to write recursively), finding the maximum element in a vector (again, insane, when a loop is totally reasonable.)

What your teacher needs to do is to teach recursion, but also to explain the problems in a recursive scheme. For example, why is the commonly written recursive Fibonacci code so inefficient? Why would you not want to use recursion to compute a factorial, since a loop is perfectly reasonable? What are the costs of recursion? And finally, I would then show my students an interesting problem that can be solved using recursion. I would hopefully teach my students the concept of memoization.

The problem is it is too easy to teach students about recursion, but not give them the judgment based information to know when to use it effectively, and when to avoid it.

[Gin]

Thank you, sir. I am learning so much more from you on this topic. Truly grateful.