Recursively reversing large vector efficiently
7 views (last 30 days)
Show older comments
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
Answers (2)
per isakson
on 12 Aug 2021
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
tic, flip(v); toc
tic, reversal_v2(v); toc
tic, SecondCode(v); toc
tic, reversal_v3(v); toc
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
John D'Errico
on 4 Nov 2024
Edited: John D'Errico
on 4 Nov 2024
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
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.
- Swap the first and last elements of the vector, then call the recursive code on elements 2:end-1.
- 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)
SwapVecRecur1(vec)
SwapVecRecur2(vec)
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))
timeit(@() SwapVecRecur2(vec))
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)
timeit(@() SwapVecRecur3(vec))
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.
0 Comments
See Also
Categories
Find more on Tables in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!