Using recursion to concatenate ONLY the letters of an input string into a single output string

Question

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

You're missing the return in the else part, but the algorithm seems to be wrong anyway. — Matthias
– Matthias, Commented Dec 2, 2021 at 16:22
Not that I think it matters here, but without additional steps, a typical answer based on recursion one character at a time will only work on strings with 1000 or fewer characters. — JonSG
– JonSG, Commented Dec 2, 2021 at 16:29
Python is a terrible choice of language to learn recursion, for several reasons. Slicing strings repeatedly is very expensive. Even if you have an idea for a smart and efficient algorithm to solve that problem, an expression like decoder(encryptedStr[1:]) will make sure the time complexity of the algorithm cannot be better than n^2. — Stef
– Stef, Commented Dec 2, 2021 at 17:07
A simple and pythonic solution to your problem, without recursion would be def(encrypted_str): return ''.join(c for c in encrypted_str if c.isalpha()). If you really want to solve this problem using recursion, I recommend choosing any other language except python. — Stef
– Stef, Commented Dec 2, 2021 at 17:12

flakes · Accepted Answer · 2021-12-02 16:36:59Z

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:])

matszwecja · Accepted Answer · 2021-12-02 16:28:33Z

0

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.

answered Dec 2, 2021 at 16:28

matszwecja

8,2372 gold badges13 silver badges22 bronze badges

Comments

Matthias · Accepted Answer · 2021-12-02 16:42:28Z

0

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.

edited Dec 2, 2021 at 16:42

answered Dec 2, 2021 at 16:36

Matthias

13.3k6 gold badges45 silver badges50 bronze badges

Comments

Luv_Python · Accepted Answer · 2021-12-02 16:47:50Z

0

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

answered Dec 2, 2021 at 16:47

Luv_Python

2722 silver badges8 bronze badges

Collectives™ on Stack Overflow

Using recursion to concatenate ONLY the letters of an input string into a single output string

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related