如何将此迭代函数转换为递归函数？

Question

此函数将输入字符串映射到字典中的字符串，并输出结果。知道如何递归处理吗？

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'))

谢谢。

Answer 1

你可以这样做：

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

虽然这几乎肯定会更慢，但会占用更多内存，并且会达到 Python 的递归限制。几乎所有用例的推荐方法都是迭代的；修改您的代码以使用 Python 的内置字符串连接：

def dna(seq):
    hashtable = {'A': 'U', 'G': 'C', 'T': 'A', 'C': 'G'}
    ans = []
    for elem in seq:
        ans.append(hashtable[elem])
    return ''.join(ans)

Answer 2

你应该明白递归并不总是答案。

python 中有最大递归深度，您可以更改。但是你仍然会有一个限制。参见：

允许的最大递归深度：

import sys
print(sys.getrecursionlimit())

因此迭代方法更适合您的情况。

还是让我们看看递归版本会是什么样子。

对于递归函数，您必须遵循简单的规则：

创建退出条件
再次调用自己（函数）。

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

如何将此迭代函数转换为递归函数？

How do I convert this iterative function to a recursive one?

python

iteration

recursion

dictionary

hashmap