Home > Software design >  How do I convert this iterative function to a recursive one?
How do I convert this iterative function to a recursive one?

Time:09-17

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.

CodePudding user response:

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)

CodePudding user response:

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