[FIXED] How to translate DNA recursively? (No while/for loops, also no translate function) in Python

Issue

So I need to translate DNA, but I'm not allowed to use any loops, it has to be done recursively. Without any loops, I really have no clue how to go about it... Because without the loop it can only print 1 nucleotide at a time. The translate function is also not allowed.

def one_dna_to_rna(c):
"""Converts a single-character c from DNA nucleotide
   to complementary RNA nucleotide
"""
if c == 'A':
    return 'U'
if c == 'C':
    return 'G'
if c == 'G':
    return 'C'
if c == 'T':
    return 'A'
else:
    return ""

def transcribe(s):
""" Argument is a string consisting of DNA nucleotis (A, C, G, T)
    Output will be (A -> U, C -> G, G -> C, T -> A)
"""

#nucleotides = ['A', 'C', 'G', 'T', " "]

x = len(s) - 1

if s == "":
    return ""
    
if s[0:x] == 'A':
    return one_dna_to_rna(s)
if s[0:x] == 'C':
    return one_dna_to_rna(s)
if s[0:x] == 'G':
    return one_dna_to_rna(s)
if s[0:x] == 'T':
    return one_dna_to_rna(s)
return one_dna_to_rna(s) + transcribe(s[0:x])

#Tests
#assert transcribe('ACGTTGCA') == 'UGCAACGU'
#assert transcribe('ACG TGCA') == 'UGCACGU'  
#assert transcribe('GATTACA')  == 'CUAAUGU'

Solution

I guess this is some learning exercise, because you would normally use loops here for sure. However, lets try to solve this with recursion!

I started by simplifying method for character translation (similarily as @Jeson Pun did):

def translate_char(char):
    TRANSLATIONS = {
        "A": "U",
        "C": "G",
        "G": "C",
        "T": "A",
        " ": "", # let's solve spaces here
    }
    return TRANSLATIONS[char]

There are for sure multiple ways to do this, but I was curious about using yield, as I'm not very experienced with it and in the same time, it seemed like it can be used for this kind of problem (so there is no need for passing some object to keep all the data).

So, what are we doing? First, we need some method to translate one character and also call translation of the next one (creating loop with recursion):

def translate_ith_char(i, whole_string):
    # end if there are no more characters
    if i == len(whole_string):
        return

    # else
    # get translated character and yield it 
    yield translate_char(whole_string[i])
    # call this method on the next character
    # here I needed to change `yield` to `yield from` to delegate iteration (see (here)[https://stackoverflow.com/questions/52725568/how-to-yield-in-a-recursive-function-in-python])
    yield from translate_ith_char(i + 1, whole_string)

And now just finish it with method transcribe that's called from outside:

def transcribe(whole_string):
    # because we are yielding, we don't get values, but a generator
    generator = translate_ith_char(0, whole_string)
    # we get a string from generator
    transcribed_value = "".join(generator)
    return transcribed_value

Here's complete code passing tests

def transcribe(whole_string):
    generator = translate_ith_char(0, whole_string)
    transcribed_value = "".join(generator)
    return transcribed_value


def translate_ith_char(i, whole_string):
    if i == len(whole_string):
        return

    yield from translate_char(whole_string[i])
    yield from translate_ith_char(i + 1, whole_string)

def translate_char(char):
    TRANSLATIONS = {
        "A": "U",
        "C": "G",
        "G": "C",
        "T": "A",
        " ": "",
    }
    return TRANSLATIONS[char]


# Tests
assert transcribe("ACGTTGCA") == "UGCAACGU"
assert transcribe("ACG TGCA") == "UGCACGU"
assert transcribe("GATTACA") == "CUAAUGU"

Ok, that was fun, and I learned a bit about using yield and yield from!

I'm not saying this is the best solution (it is not - it's absurdly complicated for this task), but to my knowledge it is a working one, and (in my opinion) pretty clean. It might be viable solution (with some changes) if it was used on stream of dna with unknown length.

Answered By - janpeterka