Recursive function in python does not call itself out

The problem is formulated as follows:

Write a recursive function that, given a string, checks if the string
is formed by two halves equal to each other (i.e. s = s1 + s2, with s1
= s2), imposing the constraint that the equality operator == can only be applied to strings of length ≤1. If the length of the string is
odd, return an error.

I wrote this code in Python 2.7 that is correct (it gives me the right answer every time) but does not enter that recursive loop at all. So can I omit that call here?

def recursiveHalfString(s):

#@param s: string

#@return bool



 if (len(s))%2==0:     #verify if the rest of the division by 2 = 0 (even number)



  if len(s)<=1:        # case in which I can use the == operator

   if s[0]==s[1]:

    return True

   else:

    return False



  if len(s)>1:                           

   if s[0:len(s)/2] != s[len(s)/2:len(s)]:     # here I used != instead of ==

    if s!=0:

     return False

    else:

     return recursiveHalfString(s[0:(len(s)/2)-1]+s[(len(s)/2)+1:len(s)])    # broken call    

   return True



 else:

   return "Error: odd string"

The expected results are True if the string is like "abbaabba"
or False when it's like anything else not similat to the pattern ("wordword")

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

1

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==.

– Tomothy32
Jan 2 at 21:01

1

Using the != operator on strings longer than one character is pretty obviously against the spirit of the task - you could just do not (x != y) instead of x == y anywhere you want to use ==.

– user2357112
Jan 2 at 21:07

1

if s!=0: is always true since s is a string. So you can never end up in the else part.

– schwobaseggl
Jan 2 at 21:07

Also, s is a string. It'll never equal 0. 0 isn't a string.

– user2357112
Jan 2 at 21:07

Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical?

– schwobaseggl
Jan 2 at 21:09

|
show 7 more comments

The problem is formulated as follows:

Write a recursive function that, given a string, checks if the string
is formed by two halves equal to each other (i.e. s = s1 + s2, with s1
= s2), imposing the constraint that the equality operator == can only be applied to strings of length ≤1. If the length of the string is
odd, return an error.

I wrote this code in Python 2.7 that is correct (it gives me the right answer every time) but does not enter that recursive loop at all. So can I omit that call here?

def recursiveHalfString(s):

#@param s: string

#@return bool



 if (len(s))%2==0:     #verify if the rest of the division by 2 = 0 (even number)



  if len(s)<=1:        # case in which I can use the == operator

   if s[0]==s[1]:

    return True

   else:

    return False



  if len(s)>1:                           

   if s[0:len(s)/2] != s[len(s)/2:len(s)]:     # here I used != instead of ==

    if s!=0:

     return False

    else:

     return recursiveHalfString(s[0:(len(s)/2)-1]+s[(len(s)/2)+1:len(s)])    # broken call    

   return True



 else:

   return "Error: odd string"

The expected results are True if the string is like "abbaabba"
or False when it's like anything else not similat to the pattern ("wordword")

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

1

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==.

– Tomothy32
Jan 2 at 21:01

1

Using the != operator on strings longer than one character is pretty obviously against the spirit of the task - you could just do not (x != y) instead of x == y anywhere you want to use ==.

– user2357112
Jan 2 at 21:07

1

if s!=0: is always true since s is a string. So you can never end up in the else part.

– schwobaseggl
Jan 2 at 21:07

Also, s is a string. It'll never equal 0. 0 isn't a string.

– user2357112
Jan 2 at 21:07

Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical?

– schwobaseggl
Jan 2 at 21:09

|
show 7 more comments

The problem is formulated as follows:

Write a recursive function that, given a string, checks if the string
is formed by two halves equal to each other (i.e. s = s1 + s2, with s1
= s2), imposing the constraint that the equality operator == can only be applied to strings of length ≤1. If the length of the string is
odd, return an error.

I wrote this code in Python 2.7 that is correct (it gives me the right answer every time) but does not enter that recursive loop at all. So can I omit that call here?

def recursiveHalfString(s):

#@param s: string

#@return bool



 if (len(s))%2==0:     #verify if the rest of the division by 2 = 0 (even number)



  if len(s)<=1:        # case in which I can use the == operator

   if s[0]==s[1]:

    return True

   else:

    return False



  if len(s)>1:                           

   if s[0:len(s)/2] != s[len(s)/2:len(s)]:     # here I used != instead of ==

    if s!=0:

     return False

    else:

     return recursiveHalfString(s[0:(len(s)/2)-1]+s[(len(s)/2)+1:len(s)])    # broken call    

   return True



 else:

   return "Error: odd string"

The expected results are True if the string is like "abbaabba"
or False when it's like anything else not similat to the pattern ("wordword")

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

The problem is formulated as follows:

Write a recursive function that, given a string, checks if the string
is formed by two halves equal to each other (i.e. s = s1 + s2, with s1
= s2), imposing the constraint that the equality operator == can only be applied to strings of length ≤1. If the length of the string is
odd, return an error.

I wrote this code in Python 2.7 that is correct (it gives me the right answer every time) but does not enter that recursive loop at all. So can I omit that call here?

def recursiveHalfString(s):

#@param s: string

#@return bool



 if (len(s))%2==0:     #verify if the rest of the division by 2 = 0 (even number)



  if len(s)<=1:        # case in which I can use the == operator

   if s[0]==s[1]:

    return True

   else:

    return False



  if len(s)>1:                           

   if s[0:len(s)/2] != s[len(s)/2:len(s)]:     # here I used != instead of ==

    if s!=0:

     return False

    else:

     return recursiveHalfString(s[0:(len(s)/2)-1]+s[(len(s)/2)+1:len(s)])    # broken call    

   return True



 else:

   return "Error: odd string"

The expected results are True if the string is like "abbaabba"
or False when it's like anything else not similat to the pattern ("wordword")

python python-2.7

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

edited Jan 2 at 21:32

asked Jan 2 at 20:58

Marcus S.

205

asked Jan 2 at 20:58

Marcus S.

205

asked Jan 2 at 20:58

Marcus S.

205

1

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==.

– Tomothy32
Jan 2 at 21:01

1

Using the != operator on strings longer than one character is pretty obviously against the spirit of the task - you could just do not (x != y) instead of x == y anywhere you want to use ==.

– user2357112
Jan 2 at 21:07

1

if s!=0: is always true since s is a string. So you can never end up in the else part.

– schwobaseggl
Jan 2 at 21:07

Also, s is a string. It'll never equal 0. 0 isn't a string.

– user2357112
Jan 2 at 21:07

Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical?

– schwobaseggl
Jan 2 at 21:09

|
show 7 more comments

1

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==.

– Tomothy32
Jan 2 at 21:01

1

Using the != operator on strings longer than one character is pretty obviously against the spirit of the task - you could just do not (x != y) instead of x == y anywhere you want to use ==.

– user2357112
Jan 2 at 21:07

1

if s!=0: is always true since s is a string. So you can never end up in the else part.

– schwobaseggl
Jan 2 at 21:07

Also, s is a string. It'll never equal 0. 0 isn't a string.

– user2357112
Jan 2 at 21:07

Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical?

– schwobaseggl
Jan 2 at 21:09

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==.

– Tomothy32
Jan 2 at 21:01

Using the != operator on strings longer than one character is pretty obviously against the spirit of the task - you could just do not (x != y) instead of x == y anywhere you want to use ==.

– user2357112
Jan 2 at 21:07

if s!=0: is always true since s is a string. So you can never end up in the else part.

– schwobaseggl
Jan 2 at 21:07

Also, s is a string. It'll never equal 0. 0 isn't a string.

– user2357112
Jan 2 at 21:07

Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical?

– schwobaseggl
Jan 2 at 21:09

|
show 7 more comments

3 Answers
3

active

oldest

votes

Here is another recursive solution. A good rule of thumb when taking a recursive approach is to first think about your base case.

def recursiveHalfString(s):

    # base case, if string is empty

    if s == '':

        return True



    if (len(s))%2==0:

        if s[0] != s[(len(s)/2)]:

            return False

        else:

            left = s[1:len(s)/2]  # the left half of the string without first char

            right = s[(len(s)/2)+1: len(s)] # the right half without first char

            return recursiveHalfString(left + right)

    else:

        return "Error: odd string"



print(recursiveHalfString('abbaabba'))   # True

print(recursiveHalfString('fail'))       # False

print(recursiveHalfString('oddstring'))  # Error: odd string

This function will split the string into two halves, compare the first characters and recursively call itself with the two halves concatenated together without the leading characters.

However like stated in another answer, recursion is not necessarily an efficient solution in this case. This approach creates a lot of new strings and is in no way an optimal way to do this. It is for demonstration purposes only.

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

add a comment |

This is a much simplified recursive version that actually uses the single char comparison to reduce the problem size:

def rhs(s):

    half, rest = divmod(len(s), 2)

    if rest:  # odd length

        raise ValueError  # return 'error'

    if half == 0:  # simplest base case: empty string

        return True

    return s[0] == s[half] and rhs(s[1:half] + s[half+1:])

It has to be said though that, algorithmically, this problem does not lend itself well to a recursive approach, given the constraints.

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

add a comment |

Another recursive solution that doesn't involve creating a bunch of new strings might look like:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    if not s or offset > half:

        return True

    if s[offset] != s[half + offset]:

        return False

    return recursiveHalfString(s, offset + 1)

However, as @schwobaseggl suggested, a recursive approach here is a bit clunkier than a simple iterative approach:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    for offset in range(half):

        if s[offset] != s[half + offset]:

            return False

    return True

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

add a comment |

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54013093%2frecursive-function-in-python-does-not-call-itself-out%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

Here is another recursive solution. A good rule of thumb when taking a recursive approach is to first think about your base case.

def recursiveHalfString(s):

    # base case, if string is empty

    if s == '':

        return True



    if (len(s))%2==0:

        if s[0] != s[(len(s)/2)]:

            return False

        else:

            left = s[1:len(s)/2]  # the left half of the string without first char

            right = s[(len(s)/2)+1: len(s)] # the right half without first char

            return recursiveHalfString(left + right)

    else:

        return "Error: odd string"



print(recursiveHalfString('abbaabba'))   # True

print(recursiveHalfString('fail'))       # False

print(recursiveHalfString('oddstring'))  # Error: odd string

This function will split the string into two halves, compare the first characters and recursively call itself with the two halves concatenated together without the leading characters.

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

add a comment |

Here is another recursive solution. A good rule of thumb when taking a recursive approach is to first think about your base case.

def recursiveHalfString(s):

    # base case, if string is empty

    if s == '':

        return True



    if (len(s))%2==0:

        if s[0] != s[(len(s)/2)]:

            return False

        else:

            left = s[1:len(s)/2]  # the left half of the string without first char

            right = s[(len(s)/2)+1: len(s)] # the right half without first char

            return recursiveHalfString(left + right)

    else:

        return "Error: odd string"



print(recursiveHalfString('abbaabba'))   # True

print(recursiveHalfString('fail'))       # False

print(recursiveHalfString('oddstring'))  # Error: odd string

This function will split the string into two halves, compare the first characters and recursively call itself with the two halves concatenated together without the leading characters.

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

add a comment |

Here is another recursive solution. A good rule of thumb when taking a recursive approach is to first think about your base case.

def recursiveHalfString(s):

    # base case, if string is empty

    if s == '':

        return True



    if (len(s))%2==0:

        if s[0] != s[(len(s)/2)]:

            return False

        else:

            left = s[1:len(s)/2]  # the left half of the string without first char

            right = s[(len(s)/2)+1: len(s)] # the right half without first char

            return recursiveHalfString(left + right)

    else:

        return "Error: odd string"



print(recursiveHalfString('abbaabba'))   # True

print(recursiveHalfString('fail'))       # False

print(recursiveHalfString('oddstring'))  # Error: odd string

This function will split the string into two halves, compare the first characters and recursively call itself with the two halves concatenated together without the leading characters.

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

Here is another recursive solution. A good rule of thumb when taking a recursive approach is to first think about your base case.

def recursiveHalfString(s):

    # base case, if string is empty

    if s == '':

        return True



    if (len(s))%2==0:

        if s[0] != s[(len(s)/2)]:

            return False

        else:

            left = s[1:len(s)/2]  # the left half of the string without first char

            right = s[(len(s)/2)+1: len(s)] # the right half without first char

            return recursiveHalfString(left + right)

    else:

        return "Error: odd string"



print(recursiveHalfString('abbaabba'))   # True

print(recursiveHalfString('fail'))       # False

print(recursiveHalfString('oddstring'))  # Error: odd string

This function will split the string into two halves, compare the first characters and recursively call itself with the two halves concatenated together without the leading characters.

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

edited Jan 2 at 21:51

answered Jan 2 at 21:41

Kevin Welch

650314

answered Jan 2 at 21:41

Kevin Welch

650314

answered Jan 2 at 21:41

Kevin Welch

650314

add a comment |

This is a much simplified recursive version that actually uses the single char comparison to reduce the problem size:

def rhs(s):

    half, rest = divmod(len(s), 2)

    if rest:  # odd length

        raise ValueError  # return 'error'

    if half == 0:  # simplest base case: empty string

        return True

    return s[0] == s[half] and rhs(s[1:half] + s[half+1:])

It has to be said though that, algorithmically, this problem does not lend itself well to a recursive approach, given the constraints.

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

add a comment |

This is a much simplified recursive version that actually uses the single char comparison to reduce the problem size:

def rhs(s):

    half, rest = divmod(len(s), 2)

    if rest:  # odd length

        raise ValueError  # return 'error'

    if half == 0:  # simplest base case: empty string

        return True

    return s[0] == s[half] and rhs(s[1:half] + s[half+1:])

It has to be said though that, algorithmically, this problem does not lend itself well to a recursive approach, given the constraints.

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

add a comment |

This is a much simplified recursive version that actually uses the single char comparison to reduce the problem size:

def rhs(s):

    half, rest = divmod(len(s), 2)

    if rest:  # odd length

        raise ValueError  # return 'error'

    if half == 0:  # simplest base case: empty string

        return True

    return s[0] == s[half] and rhs(s[1:half] + s[half+1:])

It has to be said though that, algorithmically, this problem does not lend itself well to a recursive approach, given the constraints.

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

This is a much simplified recursive version that actually uses the single char comparison to reduce the problem size:

def rhs(s):

    half, rest = divmod(len(s), 2)

    if rest:  # odd length

        raise ValueError  # return 'error'

    if half == 0:  # simplest base case: empty string

        return True

    return s[0] == s[half] and rhs(s[1:half] + s[half+1:])

It has to be said though that, algorithmically, this problem does not lend itself well to a recursive approach, given the constraints.

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

edited Jan 2 at 21:25

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

answered Jan 2 at 21:18

schwobaseggl

37.5k32443

add a comment |

Another recursive solution that doesn't involve creating a bunch of new strings might look like:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    if not s or offset > half:

        return True

    if s[offset] != s[half + offset]:

        return False

    return recursiveHalfString(s, offset + 1)

However, as @schwobaseggl suggested, a recursive approach here is a bit clunkier than a simple iterative approach:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    for offset in range(half):

        if s[offset] != s[half + offset]:

            return False

    return True

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

add a comment |

Another recursive solution that doesn't involve creating a bunch of new strings might look like:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    if not s or offset > half:

        return True

    if s[offset] != s[half + offset]:

        return False

    return recursiveHalfString(s, offset + 1)

However, as @schwobaseggl suggested, a recursive approach here is a bit clunkier than a simple iterative approach:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    for offset in range(half):

        if s[offset] != s[half + offset]:

            return False

    return True

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

add a comment |

Another recursive solution that doesn't involve creating a bunch of new strings might look like:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    if not s or offset > half:

        return True

    if s[offset] != s[half + offset]:

        return False

    return recursiveHalfString(s, offset + 1)

However, as @schwobaseggl suggested, a recursive approach here is a bit clunkier than a simple iterative approach:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    for offset in range(half):

        if s[offset] != s[half + offset]:

            return False

    return True

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

Another recursive solution that doesn't involve creating a bunch of new strings might look like:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    if not s or offset > half:

        return True

    if s[offset] != s[half + offset]:

        return False

    return recursiveHalfString(s, offset + 1)

However, as @schwobaseggl suggested, a recursive approach here is a bit clunkier than a simple iterative approach:

def recursiveHalfString(s, offset=0):

    half, odd = divmod(len(s), 2)

    assert(not odd)

    for offset in range(half):

        if s[offset] != s[half + offset]:

            return False

    return True

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

edited Jan 2 at 22:01

answered Jan 2 at 21:50

Albert

915

answered Jan 2 at 21:50

Albert

915

answered Jan 2 at 21:50

Albert

915

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu