我使用以下代码解决了 Project Euler 的问题 10，该代码通过暴力破解：
def isPrime(n):
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return False
return True
def primeList(n):
primes = []
for i in range(2,n):
if isPrime(i):
primes.append(i)
return primes
def sumPrimes(primelist):
prime_sum = sum(primelist)
return prime_sum
print (sumPrimes(primeList(2000000)))
这三个函数的工作原理如下：
-
isPrime检查一个数字是否是素数；
-
素数列表返回一个列表，其中包含具有限制“n”的特定范围内的一组素数，并且；
-
素数和对列表中所有数字的值求和。 （最后一个函数不是必需的，但我喜欢它的清晰度，特别是对于像我这样的初学者。）
然后我写了一个新函数，素数列表记录，它的作用与素数列表，帮助我更好地理解递归：
def primeListRec(i, n):
primes = []
#print i
if (i != n):
primes.extend(primeListRec(i+1,n))
if (isPrime(i)):
primes.append(i)
return primes
return primes
上面的递归函数有效，但仅适用于非常小的值，例如“500”。当我输入“1000”时，该函数导致我的程序崩溃。当我输入像“2000”这样的值时，Python 给了我这个：
运行时错误：超出最大递归深度.
我的递归函数做错了什么？或者是否有一些特定的方法来避免递归限制？
递归并不是 Python 中最惯用的做事方式，因为它没有尾递归优化因此使得使用递归代替迭代变得不切实际（即使在您的示例中该函数不是尾递归，但这也无济于事）。基本上，这意味着如果您希望输入很大，则不应将其用于复杂性大于线性的事物（仍然可以用于具有对数递归深度的事物，例如 QuickSort 等分而治之算法）。
如果你想尝试这种方法，请使用更适合函数式编程的语言，如 Lisp、Scheme、Haskell、OCaml 等；或者尝试 Stackless Python，它在堆栈使用方面有更广泛的限制，并且还具有尾递归优化:-)
顺便说一句，您的函数的尾递归等效项可能是：
def primeList(n, i=2, acc=None):
return i > n and (acc or []) or primeList(n, i+1, (acc or []) + (isPrime(i) and [i] or []))
另一个“顺便说一下”，如果你只是使用列表来累加值，那么你不应该构造一个列表......解决欧拉项目第十个问题的 Pythonic 方法是：
print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))
（好吧，也许把它分成不同的行会更Pythonic，但我喜欢单行^_^）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
