How can I write "EvenWord" Recursive in Python

Question

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

What part of the logic *in the problem statement* eludes you? — Scott Hunter, May 07 '20 at 18:30
Does this answer your question? [Reverse a string in Python](https://stackoverflow.com/questions/931092/reverse-a-string-in-python) — buran, May 07 '20 at 18:31
I thought like I need to check the letters of a word one by one and maybe defining a counter for each yet this doesn't also seem good. Im new in Python. Thus I wanted to ask but it seems people didn't like it :D -2 points have been given already :D — Mystheman, May 07 '20 at 18:31
The problem pretty clearly suggests the way of solving it: **count** the copies of the first letter, **remove** all of them and recurse for the remaining string. Are you familiar with `str.count` and `str.replace` methods? — Błotosmętek, May 07 '20 at 18:33
Take a look at the [String documentation](https://docs.python.org/3/library/stdtypes.html#string-methods) — Kexus, May 07 '20 at 18:45
I can count them, but now when I replace the letter with something else it doesn't work recursively — Mystheman, May 07 '20 at 18:55

noemiemich · Accepted Answer · 2020-05-08T09:21:11.143

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.

Thank you so much! Yet I want to ask a few questions still make me think. Now when we get a letter from the string, let's say our word is "egeg", we keep g letter. Now for the if statements, we are free to move, when we come to other part, how do we remove both g letters? This is what I cannot understand actually. — Mystheman, May 07 '20 at 21:11
No problem, those things are tricky. In the code above, when you run the function on the word "egeg", the first letter you will check is "g", the last one. So the variable last_letter will be g (last_letter = word[-1]); later on in the code you remove that letter from the word by doing next_word = word.replace(last_letter, '') which means replace all the last_letter (in your case g) by an empty string '', which is the same as just removing the letter. — noemiemich, May 08 '20 at 09:15
So wow, now it makes sense, also in the above with next word, we just get next word zero to last one and when we replace the next word will be the word which doesn't have g letters and return that to beginning. Really imperessive. Thank you so much again! — Mystheman, May 08 '20 at 10:08
Great, glad I could help. Please mark the answer as accepted if it solved your problem. Enjoy your new Python journey! — noemiemich, May 08 '20 at 11:00

How can I write "EvenWord" Recursive in Python

1 Answers1