1

This function map input strings to that in a dictionary, outputting the result. Any idea how this can be approached recursively?

def dna(seq):
    hashtable = {'A': 'U', 'G': 'C', 'T': 'A', 'C': 'G'}
    ans = ''
    for i in range(len(seq)):
        ans += hashtable[seq[i]]
    return ans


print(dna('AGCTGACGTA'))

Thanks.

flarezel
  • 81
  • 5
  • 3
    In theory, any iteration can be rewritten into recursion. In practice, Python is not very good at it, and in this case the iterative approach is preferable; there is nothing to be gained from recursion. This code could be improved (`for ch in seq`, or using comprehensions, or best of all using `str.translate`), but what you currently have is still much better than recursion. – Amadan Sep 06 '21 at 06:43

2 Answers2

4

You could do:

def dna(seq):
    if not seq:
        return ''
    return {'A': 'U', 'G': 'C', 'T': 'A', 'C': 'G'}[seq[0]] + dna(seq[1:])

Although this is almost certainly slower, uses more memory, and will hit Python's recursion limit. The recommended approach for almost all usecases would be iterative; modify your code to use Python's builtin string join:

def dna(seq):
    hashtable = {'A': 'U', 'G': 'C', 'T': 'A', 'C': 'G'}
    ans = []
    for elem in seq:
        ans.append(hashtable[elem])
    return ''.join(ans)
kcsquared
  • 5,244
  • 1
  • 11
  • 36
3

You should understand recursion is not always the answer.

There is a maximum recursion depth in python which you can change. But still you will have a limit. See: https://stackoverflow.com/a/3323013/2681662

The maximum recursion depth allowed:

import sys
print(sys.getrecursionlimit())

So iterative approach is better in your case.

Still let's see how the recursive version would look like.

For a recursive function you have to follow simple rules:

  1. Create an exit condition
  2. Call yourself (the function) again.
def dna_r(seq):
    hashy = {'A': 'U', 'G': 'C', 'T': 'A', 'C': 'G'}
    if len(seq) == 1:
        return hashy[seq]

    return dna_r(seq[0]) + dna_r(seq[1:])
Christian Sloper
  • 7,440
  • 3
  • 15
  • 28
MSH
  • 1,743
  • 2
  • 14
  • 22
  • Apologies in advance but being someone that is rlly new to recursion, may I ask why the loop doesnt just end in the first loop when dna_r(first letter) is called as it satisfies the base case? – flarezel Sep 06 '21 at 06:56
  • 2
    Actually it ends when the function calls `dna_r(first letter)` for the first letter. But we call the function again for remaining letters using `dna_r(seq[1:])`. – MSH Sep 06 '21 at 07:08