"Given a string of both letters and special characters/numbers, use recursion to concatenate the letters into a single string and return it."

My code is below, I'm still learning recursion and am stuck in trying to trace it. I tried a bunch of different lines in this code but idk how to fix what I do have so far:

def decoder(encryptedStr):
    if len(encryptedStr) != 0:
        if encryptedStr[0].isalpha() == True:
            decoded = encryptedStr[0]
            decoded.join(decoder(encryptedStr[1:]))
            print(decoded)
        else:
            decoder(encryptedStr[1:])

I haven't had it return anything yet because I'm struggling with the part where I have to join the new letters to the output string. Instead of .join I also tried:

decoded  = decoder(encryptedStr[1:])

but it doesn't work bc Nonetype??

CodePudding user response：

Your main issue is that you didnt return, but there are some issues with your approach that make this more complex than need-be.

Think tail-first when doing recursion- What is your end condition, and how do you decide to continue. Typically with this kind of method you do something like, 1) process a single value in the list, 2) let the recursive method handle the rest of it, 3) combine the results.

An easy indicator of the tail-first return here would be to return nothing if the string is empty:

def decoder(encryptedStr):
    if len(encryptedStr) == 0:
        return ""
    ...

Now in each run we want to operate on one letter and pass the rest to a recursive call. Ignoring the special character requirement, you'd get something like this:

def decoder(encryptedStr):
    if len(encryptedStr) == 0:
        return ""

    first = encryptedStr[0]
    rest = decoder(encryptedStr[1:])

    return first   rest

Now we can handle the special case where we want to omit letters.

def decoder(encryptedStr):
    if len(encryptedStr) == 0:
        return ""

    first = encryptedStr[0]
    rest = decoder(encryptedStr[1:])

    if not first.isalpha():
        first = ""

    return first   rest

And that's all there is to it!

Bonus for some refactoring:

def clean(letter):
    return letter if letter.isalpha() else ""

def decoder(encrypted):
    if len(encrypted) == 0:
        return ""

    return clean(encrypted[0])   decoder(encrypted[1:])

CodePudding user response：

There's a bunch of problems here:

• I don't think join does what you want it to do in that case. If you want to add some strings together simply use =. join would insert decoded character between whatever decoder(encryptedStr[1:]) returns.
• You don't have a case for len(encryptedStr) == 0, so it returns default value of None. That's why you cannot append it's results to decoded.

CodePudding user response：

Return immediately if there is nothing to do. Otherwise take the first letter if it matches the condition and add the result of the recursive call (where the parameter is the current encrypted string without the first character).

def decoder(encrypted):
    if not encrypted:
        return ''
    decrypted = encrypted[0] if encrypted[0].isalpha() else ''
    return decrypted   decoder(encrypted[1:])

print(decoder('Abc123rtZ5'))

The result is AbcrtZ.

Bonus info (as @JonSG mentioned in the comments):

Run this with print(decoder('A' * 1000)) and you'll see why recursion is a bad idea for this task.

CodePudding user response：

Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely. To recursively concatenate ONLY the letters of an input string into a single output string:

some_string = "I2L4o2v3e P;y|t!o#n"


def decoder(encryptedStr, decoded = ""):
    if len(encryptedStr) == 0:  # Base condition
        return decoded
    if encryptedStr[0].isalpha():
        decoded  = encryptedStr[0]
        return decoder(encryptedStr[1:], decoded)
    # If the char in the index [0] is not a letter it will be sliced out.
    return decoder(encryptedStr[1:], decoded)


print(decoder(some_string))

Output:

ILovePython