Recursion Revisited - My Code:

My code for the assigment of Recursion Revisited is not working for large vectors. Can you please explain me why it is not working although I have attempted to reduce the number of recursive function calls.

function w = reversal(v)
    if length(v) <= 1
        w = v;
    else
        f = v(1);
        l = v(end);
        vv = v(2:end-1);
        w = [l reversal(vv) f];
    end
end

Answer 1

[John D'Errico]

Your code IS working acceptably. Of course, if you call it with a vector of length 1e6, or something like that, you can be getting millions of recursive calls. And that would blow your memory away. So why would you be surprised? Your code uses essentially N/2 recursive calls for a vector of length N. (Depends on if N is odd or even of course.)

Recursive solutions to problems are often nice, in the sense they are easy to write, and they just look neat. Hey, great. But that does not mean all recursive solutions to problems are efficient to implement. In fact, you often end up trading away a lot of memory required for that elegance in the way they look.

[Bibek Tiwari]

Thank you very much for the explanation.

But, I would like to ask you about a thing running in my mind regarding the solution for this assignment. I hope you will help me make my confusions clear.

I got that the following solution for this assignment is working fine for larger vector.

function v = reversal(v)
if length(v) > 1
    i = ceil(length(v)/2);
    v = [reversal(v(i+1:end)) reversal(v(1:i))];
end

But, Isn't it that for the same length of vector v, the number of recursive calls for this code is higher than that for my code up there?.

Is it because although the number of recursive calls is higher, the length of vector for each successive recursive call is reducing faster? Is this the reason that is making difference or is there anything else?

Thank you in advance.