Results 1 to 8 of 8

Math Help - Recursive algorithm

  1. #1
    NsK
    NsK is offline
    Newbie
    Joined
    May 2007
    Posts
    4

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by NsK View Post
    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
    Last edited by CaptainBlack; May 19th 2007 at 10:09 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    NsK
    NsK is offline
    Newbie
    Joined
    May 2007
    Posts
    4
    its confusing...anyone else?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,790
    Thanks
    1687
    Awards
    1
    Quote Originally Posted by NsK View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    NsK
    NsK is offline
    Newbie
    Joined
    May 2007
    Posts
    4
    nop...not asking any particular language...I think java would be ok...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by NsK View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    NsK
    NsK is offline
    Newbie
    Joined
    May 2007
    Posts
    4
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 23rd 2009, 10:22 AM
  2. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 6th 2009, 01:55 AM
  3. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 10th 2008, 10:44 PM
  4. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2008, 10:56 PM
  5. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2008, 04:50 AM

Search Tags


/mathhelpforum @mathhelpforum