How can I write “EvenWord” Recursive in Python [closed]

We tried to solve the following problem with friends but we couldn’t come to a conclusion. How can we approach this question?

The full question is:

Even Words Problem: An even word is a word that contains an even number of copies of every letter. For example, the word “tattletale” is an even word, since there are four copies of ‘t’ and two copies of ‘a,’ ‘e,’ and ‘l.’ Similarly, “appeases” and arraigning” are even words. However, “banana” is not an even word, because there is just one ‘b’ and three copies of ‘a.’

Write a function def isEvenWord(word) that accepts as input a string representing a single word and returns whether or not that word is an even word.

Your solution should be recursive and must not use any loops (e.g. while, for). As a hint, this problem has a beautiful recursive decomposition:

• The empty string is an even word, since it has 0 copies of every letter.

• Otherwise, a word is an even word if there are at least two copies of the first letter and the word formed by removing two copies of the first letter is itself an even word.

For example, we can see that the word “appeases” is an even word using the following logic:

“appeases” is an even word, because “ppeses” is an even word, because “eses” is an even word, because “ss” is an even word, because “” is an even word.

Screenshot of the problem description

Answer

I assume the tricky part is not using loop since this the solution must be recursive.

In this problem, you want to find whether the count of each letter can be divided by two.

Here are the steps you can follow:

1) Define your base condition

In this problem, the base condition is when there are no more letters in the word to check; in other words, your word is an empty string ''. If the base condition is reached, it means that you have checked the count of all the letters in the word and the count was always even. So you can stop there. You’ve checked all the letters in the word and their count and they are even –> you return True and you are done.

2) Define what you do if the base condition is not reached:

In this problem, you need to check that the count of each letter in the word is even. You can store the letter in a variable and check its count in the word. You must check the last letter each time, create a new word that doesn’t contain the letter already checked, and run the isEvenWord(word) function again on the new word.

If when you check the count of the letter, it is not even, then you are done, you know that the word is not even since at least one letter in the word is not even so you return False.

If the count of the letter you are checking is even then you continue the check the next letter by calling your function again on the new word made of the remaining letters that you haven’t checked yet.

Here is the code version of the explanation above:

def isEvenWord(word):
    if word == '':  # base condition
        return True
    else:
        last_letter = word[-1]
        if word.count(last_letter)  % 2 != 0:
            return False
        else:
            next_word = word[0:-1] #create the next word you want to test (ie the word except the last letter)
            next_word = word.replace(last_letter, '') # in the new word, replace the variable last_letter (the letter you just counted) by an empty string '' which is like removing it
            return isEvenWord(next_word)

Very nice little puzzle, thanks for sharing.

I hope this helps.