1. ## Recursive algorithm

I don't know what I am suppose to write for this question...
give a recursive algorithm for finding the reversal of a bit string?
I know the recursive definition to find a reversal of a string is
something like (alex)R = x (ale) R = xe (al)R = xel (a)R = xela

but what's exactly is the recursive algorithm....btw this is for a math class

2. Originally Posted by NsK
I don't know what I am suppose to write for this question...
give a recursive algorithm for finding the reversal of a bit string?
I know the recursive definition to find a reversal of a string is
something like (alex)R = x (ale) R = xe (al)R = xel (a)R = xela

but what's exactly is the recursive algorithm....btw this is for a math class
A recursive algorithm is one which calls itself.

Consider:

Precondition forward contains the string to be reversed and backward
is the null string.

procedure Reverse( forward, backward)

.. lng = length(forward)
.. if lng == 0 //if forward is the null string return
.... return
.. else
.... backward=backward|forward(1) //tag the leading char of forward onto the end of backward
.... if lng>1 // if length of forward was greater than 1 remove the leading char
...... forward = forward(2:lng)
...... Reverse( forward, backward) //and call Reverse with the new forward and backward
.... else
...... forward="" //forward had only a single char so now is null
...... return
.... endif
.. endif

endprocedure

Postcondition forward is the null string and backward cotains a reversed
copy of the content of farward on entry

(everything on a line following "//" is a comment)

(You will need to check that this in fact does what I claim)

RonL

3. its confusing...anyone else?

4. Originally Posted by NsK
its confusing...anyone else?
The answer RonL gave is very clear.
Does your course/text/lecture notes use pseudo-code?
If not, what does the question expect?
Are you required to use a particular language such as Vbasic or some other?

5. nop...not asking any particular language...I think java would be ok...

6. Originally Posted by NsK
nop...not asking any particular language...I think java would be ok...
A recursive alogrithm is one that invokes itself, the classic is the computation
of a factorial:

factorial(0) = 1
factorial(n) = n factorial(n-1)

RonL

7. Alternative method of expressing the idea:

lng=length(string)
if lng<=1 then reverse=string
if lng>1 then reverse=reverse(string(2:lng)|string(1)

or in an alterative type of representation:

lng=length(string)
reverse=string, lng<=1
reverse=reverse(string(2:lng)|string(1), lng>1

where:

"|" is the concatenation operator (joins two strings together)
"length(a)" gives the length of the string "a"

But this is essentially the same algorithm as before.

If the input string is 1 charater long or null then the reversed version
of string is the same as string itself. Otherwise the reversed version
is obtained by taking the leading charater from string and concatenating
to the end of a reversed copy of what is left of string after the first character
is striped off.

Note that the above is a more elegant version of what went before, which can
be straemlined using the improvements to:

procedure Reverse( forward, backward)
.. lng = length(forward)
.. if lng <= 1 //if forward is the null string or one charater long return
.... reverse=forward
.... return
.. else
...... backward=backward|forward(1) //tag the leading char of forward onto the end of backward
...... forward = forward(2:lng)
...... Reverse( forward, backward) //and call Reverse with the new forward and backward..
.. endif
endprocedure

RonL

8. ok I understand the algorithm now, its basically the same I was thinking about the string of ALEX and now, I understand the way you expressed it in a algorithm...THANKS ALOT FOR THE HELP