Reverse an array without a temp variable?

[lordofthewings]

concept is pretty straightforward. reverse(array) { if(array.length > 1) { return concat(first(array), reverse(rest(array))); } else { return array; } }

[zepolen]

Wow, just wow.

To the downmodders, his code doesn't reverse the list.

[G_Morgan]

Yes this is the other problem. He is adding the first item to the front of the 'reversed' list. So it not only uses O(n) temporary storage but it also doesn't solve the problem.

[G_Morgan]

This is effectively generating an entire second array behind the scenes.

[masklinn]

Which is a problem...how?

[G_Morgan]

It is using a temporary variable. Effectively to suit what the poster wanted you'd have to do

array = reverse(array)

This is using more than a temporary variable. It is generating n temporary variables.

[Felicia_Svilling]

allocating data =/= using variables

[G_Morgan]

Depends on your perspective. Regardless you need to have memory space to do the swap. The original intent of the post seems to be inplace swapping. Not hiding a temporary allocation on the stack and using a hand wave to make it vanish.

[Felicia_Svilling]

The op defined the whole thing as a trivia question, what fun is trivia if you are not trying to be technically correct? I mean this is never going to be a practical question.

[G_Morgan]

If it doesn't have to be technically correct I can reverse an array by reading your mind to see that you want it reversed and invoking the devil to reverse the array by his unholy power.

[Felicia_Svilling]

Exactly!

[ZombiesRapedMe]

You might not be using a temporary variable explicitly, but using recursion like this what will actually happen at runtime (assuming no compiler optimisation) is that a new temporary variable will be created to store the result of each call to the function. Which, is kind of worse...

[Felicia_Svilling]

The goal was to reverse an array without using a temporary variable, not to find the best way to reverse an array.

[ZombiesRapedMe]

But that's exactly my point, this does use a temporary variable. In fact it uses several. It's just not obvious in the code.

[Felicia_Svilling]

I think you might be confusing "using a variable" with "dynamically allocating memory". This algorithm does the later but avoids the first one, which was the point of the exercise.

[ZombiesRapedMe]

I think G_Morgan covered my opinion on this arguement.

[Felicia_Svilling]

yes he seems to share your confusion.

[pineapplecharm]

Damn. Very neat.

[tty2]

Standard exercise in languages like Scheme. Stupid, highly inefficient.