Reversing a string (recursion)

[gitoxa]

I've got it working, but was just wondering, is the second parameter required? It feels unecessary to me.

code:

function Reverse_Word (Word : string(*), Length : nat1) : string     if Length > 2 then         result Word(Length) + Reverse_Word(Word, Length-1)     else         result Word(Length) + Word(Length-1)     end if end Reverse_Word var CoolWord : string get CoolWord put Reverse_Word(CoolWord, length(CoolWord))

[rizzix]

Depends. Is there an O(1) solution in finding out if you've reached the end of the string.

[Sean]

I like how you are trying to make your own function for it, however, you can simply do it with a basic for loop and the length function like so:

Turing:

var word : string get word : * for decreasing foo : length (word) .. 1     cls     put word (foo) .. end for

[gitoxa]

You can easily make that a function too. Point is, I'm trying to do recursion. Gotta start somewhere, right?

@rizzix: not that I know of.

[Saad]

Sean @ Wed May 21, 2008 5:37 pm wrote:

I like how you are trying to make your own function for it, however, you can simply do it with a basic for loop and the length function like so:

Turing:

var word : string get word : * for decreasing foo : length (word) .. 1     cls     put word (foo) .. end for

The problem is that it only outputs it reverse, while the function by gitoxa returns a new string which can be used later on.

[gitoxa]

Saad, just take what he has and store it to a new variable rather than outputting it. It's basically the same thing, just a different way to go about it. (probably better, but that doesn't matter at the moment.)

[Saad]

The point I want to emphasize is that the method is valid and works, but what happens when you want to reverse more then once? Code gets repeated that could be used as a function.

[Tony]

I think Sean has simply missed the point of it being done by recursion. The iterative approach can trivially be put into a function.

[rizzix]

gitoxa @ Wed May 21, 2008 5:39 pm wrote:

@rizzix: not that I know of.

Then what you have is the best way of doing it. However, its pretty bad memory-wise, but this is a problem of the way imperative languages work, not so much with your algo.

[Sean]

Tony @ Wed May 21, 2008 6:02 pm wrote:

I think Sean has simply missed the point of it being done by recursion. The iterative approach can trivially be put into a function.

That I did. However, I still believe that the second part of your function is needed. Unless, someone can tell us why it isn't needed, or has any knowledge around the question.

[rizzix]

Sean @ Wed May 21, 2008 6:22 pm wrote:

...I still believe that the second part of your function is needed. Unless, someone can tell us why it isn't needed, or has any knowledge around the question.

He said second parameter, which in this case is Length

[gitoxa]

The reason I was asking, is because this is ugly.

code:

Reverse_Word(Clean_Word (CoolWord, length (CoolWord)), length(Clean_Word (CoolWord, length (CoolWord))))

Of course I won't leave it like that though... heh.

[Tony]

length(Clean_Word (CoolWord, length (CoolWord)))

This is horrible. You are doing the same calculation twice just to get a copy of the result.

[rizzix]

Even then, using length is probably an O(n) solution, thus the overall algorithm would be dramatically slower.

[Tony]

@gitoxa -- sounds like it's time to also catch up on some dynamic programming as well and cache the results of those functions