

-----------------------------------

gitoxa

Wed May 21, 2008 5:25 pm


Reversing a string (recursion)

-----------------------------------

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

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

Wed May 21, 2008 5:29 pm


RE:Reversing a string (recursion)

-----------------------------------

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


-----------------------------------

Sean

Wed May 21, 2008 5:37 pm


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:


var word : string

get word : *

for decreasing foo : length (word) .. 1
    cls
    put word (foo) ..
end for



-----------------------------------

gitoxa

Wed May 21, 2008 5:39 pm


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.


-----------------------------------

Saad

Wed May 21, 2008 5:40 pm


Re: 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:


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

Wed May 21, 2008 5:43 pm


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.)


-----------------------------------

Saad

Wed May 21, 2008 5:50 pm


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.


-----------------------------------

Tony

Wed May 21, 2008 6:02 pm


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.


-----------------------------------

rizzix

Wed May 21, 2008 6:05 pm


Re: RE:Reversing a string (recursion)

-----------------------------------

@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

Wed May 21, 2008 6:22 pm


Re: 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.

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

Wed May 21, 2008 6:33 pm


Re: RE:Reversing a string (recursion)

-----------------------------------

 ...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

Wed May 21, 2008 7:28 pm


RE:Reversing a string (recursion)

-----------------------------------

The reason I was asking, is because this is ugly. :)
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

Wed May 21, 2008 7:46 pm


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.


-----------------------------------

rizzix

Wed May 21, 2008 7:48 pm


RE:Reversing a string (recursion)

-----------------------------------

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


-----------------------------------

Tony

Wed May 21, 2008 8:01 pm


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 ;)


-----------------------------------

gitoxa

Wed May 21, 2008 8:02 pm


Re: 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.

Hence the reason I said it was ugly.

