给我一个字符串,如果有一个或多个无效字符,则必须返回False,否则返回True。需要注意的是,我只能内置函数和str操作(例如:in,+,indexing,len)和递归。到目前为止,我没有用:
def is_valid_sequence(dna): """ (str) -> bool Return True if and only if the DNA sequence is valid (A, T, C, and G) :param dna: string sequence :return: true or false >>> is_valid_sequence('ATTAC') True >>> is_valid_sequence('FBSSS') False """ valid_seq = 0 if len(dna) == 1 and dna in ['A', 'T', 'C', 'G']: valid_seq += 1 else: return is_valid_sequence(dna[1:])
显然,由于递归,该代码无法正常工作,并且valid_seq在下一次递归迭代之后才将变量加1 。
valid_seq
对于小尺寸(约一千个字符)的DNA序列,这是一个实际的实现
def is_valid_sequence (dna): # base case if len (dna) == 0: return True # check if first character is valid elif dna [0] not in ['A', 'T', 'C', 'G']: return False # otherwise, recurse on the rest of the characters else: return is_valid_sequence (dna [1:]) print (is_valid_sequence ('AATGCGA')) # True print (is_valid_sequence ('AATXGCGA')) # False
注意事项
在python中使用递归要小心-长dna字符串会导致堆栈溢出。尝试验证甚至这个“大”序列都将失败
dna
GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGAC
您可以通过is_valid_sequence使用Clojure样式loop/recur机制进行恒定空间递归来轻松避免这种情况
is_valid_sequence
loop
recur
def recur (*values): return (recur, values) def loop (f): acc = f () while type (acc) is tuple and acc [0] is recur: acc = f (*acc [1]) return acc def is_valid_sequence (dna): # stack-safe loop/recur implementation # initialize loop state variable `s` to value of `dna` return loop (lambda s = dna: # base case True if len (s) == 0 else # check if first character valid False if s [0] not in ['A', 'T', 'C', 'G'] else # else recurse on the rest of the characters recur (s [1:])) # does not overflow stack print (is_valid_sequence ('GATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACAGATTACA')) # True
持续改进
该loop/recur执行暴露给调了更多的机会,我们的函数的性能。按照我们的方式对字符串进行切片,dna[0]并在内存中dna[1:]创建 新的 字符串;这仅是必需的,因为在我们编写的第一个函数中使用了递归API
dna[0]
dna[1:]
该loop/recur接口允许我们使用任何数据类型是适合我们的计算输出- 在这种情况下,一个简单的整数索引就行了。词法作用域处理剩下的dna事情–在我们的lambda中可以访问,并且不需要进行dna[1:]切片,这将为大量输入节省大量时间/空间
def is_valid_sequence (dna): # only create this array once valid_chars = ['A', 'T', 'C', 'G'] # initialize loop state variable `i` with 0 return loop (lambda i = 0: True if len (dna) == i else False if dna [i] not in valid_chars else recur (i + 1))
Python和不羁的Lambda
请注意,我们是如何被迫在lambda内使用纯表达式而不是传统的if/elif/else语句语法–这对于简单的程序来说不是问题,但是更复杂的程序可能很难在python中以这种方式表达。
if/elif/else
这与上面的程序相同,但是使用普通的旧函数而不是lambda
def is_valid_sequence (dna): valid_chars = ['A', 'T', 'C', 'G'] # plain old function; replaces lambda def myloop (i = 0): if len (dna) == 0: return True elif dna [i] not in valid_chars: return False else: return recur (i + 1) # use plain old function instead of lambda return loop (myloop)