Computer Science Canada

Reversing a string (recursion)
Author:  gitoxa [ Wed May 21, 2008 5:25 pm ]
Post subject:  Reversing a string (recursion)
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))
Author:  rizzix [ Wed May 21, 2008 5:29 pm ]
Post subject:  RE:Reversing a string (recursion)
Depends. Is there an O(1) solution in finding out if you've reached the end of the string.
Author:  Sean [ Wed May 21, 2008 5:37 pm ]
Post subject:  RE:Reversing a string (recursion)
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
Author:  gitoxa [ Wed May 21, 2008 5:39 pm ]
Post subject:  RE:Reversing a string (recursion)
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.
Author:  Saad [ Wed May 21, 2008 5:40 pm ]
Post subject:  Re: RE:Reversing a string (recursion)
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.
Author:  gitoxa [ Wed May 21, 2008 5:43 pm ]
Post subject:  RE:Reversing a string (recursion)
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.)
Author:  Saad [ Wed May 21, 2008 5:50 pm ]
Post subject:  Re: Reversing a string (recursion)
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.
Author:  Tony [ Wed May 21, 2008 6:02 pm ]
Post subject:  RE:Reversing a string (recursion)
I think Sean has simply missed the point of it being done by recursion. The iterative approach can trivially be put into a function.
Author:  rizzix [ Wed May 21, 2008 6:05 pm ]
Post subject:  Re: RE:Reversing a string (recursion)
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.
Author:  Sean [ Wed May 21, 2008 6:22 pm ]
Post subject:  Re: RE:Reversing a string (recursion)
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.
Author:  rizzix [ Wed May 21, 2008 6:33 pm ]
Post subject:  Re: RE:Reversing a string (recursion)
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
Author:  gitoxa [ Wed May 21, 2008 7:28 pm ]
Post subject:  RE:Reversing a string (recursion)
The reason I was asking, is because this is ugly. Smile
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.
Author:  Tony [ Wed May 21, 2008 7:46 pm ]
Post subject:  RE:Reversing a string (recursion)
length(Clean_Word (CoolWord, length (CoolWord)))

This is horrible. You are doing the same calculation twice just to get a copy of the result.
Author:  rizzix [ Wed May 21, 2008 7:48 pm ]
Post subject:  RE:Reversing a string (recursion)
Even then, using length is probably an O(n) solution, thus the overall algorithm would be dramatically slower.
Author:  Tony [ Wed May 21, 2008 8:01 pm ]
Post subject:  RE:Reversing a string (recursion)
@gitoxa -- sounds like it's time to also catch up on some dynamic programming as well and cache the results of those functions Wink
Author:  gitoxa [ Wed May 21, 2008 8:02 pm ]
Post subject:  Re: RE:Reversing a string (recursion)
Tony @ Wed May 21, 2008 7:46 pm wrote:
length(Clean_Word (CoolWord, length (CoolWord)))

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


Hence the reason I said it was ugly.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy