1

I would like to check if a letter is in a string using recursion. The way I solved this was using a set, and subset, to get the output I want, but that's not recursive. How would I go about writing a recursive method? Here's what I've done so far: 

import sys


userInput = str(sys.argv[1])
letters = ["e", "f"]

if set(letters).issubset(userInput):
    print(userInput +" exist in these 2 letters!)
else:
    print(userInput + " does not exist in these 2 letters!")

Given string example: wife

cdlane
  • 40,441
  • 5
  • 32
  • 81
kraljevocs
  • 115
  • 1
  • 2
  • 12
  • 2
    Is this an assignment that requires to have a recursive function? Otherwise, there is no reason to use it here in that scenario. I just want to be sure to understand. – Jonathan Gagne Feb 08 '19 at 13:13
  • No it's not an assignment, I know there a other ways to do this, I just want to know how do I do it using recursive method, I'm new to Python and I know what I did above fulfills what I want, I just would like to know more – kraljevocs Feb 08 '19 at 13:20

2 Answers2

3

I think your solution is fine, but if you really want a recursive function, then the format of the function below is typical for functional programming:

def check_letters(compare_to, lst):
    if len(lst) == 0:
        return True
    else:
        if lst[0] in compare_to:
            return check_letters(compare_to, lst[1:]) # recursive step
        else:
            return False

if check_letters(userInput, letters):
    ...

So the idea is to check the "head" of the list (0th element) and if it meets your predicate, you continue the recursion with the "tail" of the list.

So each recursive step checks the first element in the list and then forwards the rest of the list "down" the recursion. Here I use slicing:

l = [1,2,3]
print(l[1:]) # create a new list from index 1
# Outputs: [2,3]

Since python is zero-indexed, 1 means the second element.

To support repeated letters as pointed out by @cdlane, the recursion can pass along the input with the occurence replaced:

return check_letters(compare_to.replace(lst[0], "", 1), lst[1:]) # recursive step
Jeppe
  • 1,830
  • 3
  • 24
  • 33
  • Thank you so much! It works! I learnt something new today thanks to you – kraljevocs Feb 08 '19 at 13:24
  • 1
    Or simpler: `return lst[0] in compare_to and check_letters(compare_to, lst[1:])` or even `return len(lst) == 0 or lst[0] in compare_to and check_letters(compare_to, lst[1:])` which does it all in one line. – Alfe Feb 08 '19 at 13:32
  • 1
    @Alfe yeah - perhaps less readable though. You could one-line the whole thing as `return len(lst) == 0 or lst[0] in compare_to and check_letters(compare_to, lst[1:])` I guess. EDIT: Ah, you beat me to it! :-P – Jeppe Feb 08 '19 at 13:35
  • @Jeppe Just to clarify things, lst[1:] checks the second element for the letters list? – kraljevocs Feb 08 '19 at 13:39
  • 1
    @kraljevocs No, `lst[1:]` returns a new list with index 1 and till the end. So practically the same list, except the first element. So for each recursive step, the list grows 1 smaller. [Examples of python slicing](https://stackoverflow.com/questions/509211/understanding-slice-notation) – Jeppe Feb 08 '19 at 13:41
  • @Jeppe Wait, why do we not check the first element? I'm quite confused – kraljevocs Feb 08 '19 at 13:55
  • @kraljevocs `if lst[0] in compare_to:` checks if the first element is in the other list. When `lst[1:]` is used, it means "we have checked the 0th element (the first), we now do the recursion to check the rest of the list. – Jeppe Feb 08 '19 at 13:57
  • 1
    @Jeppe OHHH right right, I get it now, thank Jeppe! You've helped me a lot – kraljevocs Feb 08 '19 at 13:58
2

Moving away from your set-based solution is an opportunity to address its gray area: how to deal with repeated letters. I.e. letters = ["f", "f"] vs "wife" and "giraffe". A set-based solution returns True for both. But we can do otherwise:

def check_letters(string, array):
    if not array:
        return True

    head, *tail = array

    index = string.find(head)

    if index == -1:
        return False

    return check_letters(string[:index] + string[1 + index:], tail)

letters = ["f", "f", "s"]

userInput = "false"

print(check_letters(userInput, letters))

userInput = "falsify"

print(check_letters(userInput, letters))

OUTPUT

> python3 test.py
False
True
>
cdlane
  • 40,441
  • 5
  • 32
  • 81
  • Thank you for your effort in helping! I'll take note of this! – kraljevocs Feb 10 '19 at 05:16
  • Repeated letters or even substrings may as well be used directly: `letters = ["e", "ff"]`. Your solution does not work for many cases though, since you remove the parts of the string you searched for a given key. E.g for `letters = ["a", "b"]` it fails on input `ba`, since you searched beyond the `b` when looking for `a`. – Jeppe Feb 16 '19 at 21:17
  • @Jeppe, the `letters = ["f", "f"]` case applies to `false` vs. `falsify` and was not about double letters. The `ba` issue is a problem that I've fixed -- thanks! – cdlane Feb 16 '19 at 21:21
  • @cdlane Ah, my bad. I've updated my answer with one way of doing it by replacing a letter once it has been matched. Good contribution. :-) – Jeppe Feb 16 '19 at 21:32