Recursive function in python does not call itself out

Question

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

If == is off limits for string length >1, I would assume != is also not allowed. It's essentially not ==. — iz_
– iz_, Commented Jan 2, 2019 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
– user2357112, Commented Jan 2, 2019 at 21:07
if s!=0: is always true since s is a string. So you can never end up in the else part. — user2390182
– user2390182, Commented Jan 2, 2019 at 21:07
Also, s is a string. It'll never equal 0. 0 isn't a string. — user2357112
– user2357112, Commented Jan 2, 2019 at 21:07
Is 'abcabc' symmetrical by the constraints or do all the nested half strings themselves have to be symmetrical? — user2390182
– user2390182, Commented Jan 2, 2019 at 21:09

user2390182 · Accepted Answer · 2019-01-02 21:25:46Z

6

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, 2019 at 21:25

answered Jan 2, 2019 at 21:18

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kevin Welch · Accepted Answer · 2019-01-02 21:51:45Z

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.

Albert · Accepted Answer · 2019-01-02 22:01:35Z

1

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, 2019 at 22:01

answered Jan 2, 2019 at 21:50

Albert

2211 silver badge6 bronze badges

Collectives™ on Stack Overflow

Recursive function in python does not call itself out

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related