在Python中迭代SternBrocot树的某些部分

Question

我的目标是迭代[a，b]a互质到b和a+b<；=n。例如，如果n=8，我想迭代[1，2]，[2，3]，[3，4]，[3，5]，[1，3]，[2，5]，[1，4]，[1，5]，[1，6]，[1，7]。
我的第一个想法是使用Stern Brocot树的递归函数：

def Stern_Brocot(n,a=0,b=1,c=1,d=1):
if(a+b+c+d>n):
    return 0
x=Stern_Brocot(n,a+c,b+d,c,d)
y=Stern_Brocot(n,a,b,a+c,b+d)
if(x==0):
    if(y==0):
        return [a+c,b+d]
    else:
        return [a+c]+[b+d]+y
else:
    if(y==0):
        return [a+c]+[b+d]+x
    else:
        return [a+c]+[b+d]+x+y

正如预期的那样

^{pr2}$

对于n<；=995，它很有效。但当n>；=996时，会出现以下错误：

Traceback (most recent call last):
  File "<pyshell#17>", line 1, in <module>
    a=Stern_Brocot(996)
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
...
  File "C:\Users\Pim\Documents\C Programmeren en Numerieke Wisk\Python\PE\PE127.py", line 35, in Stern_Brocot
    y=Stern_Brocot(n,a,b,a+c,b+d)
RuntimeError: maximum recursion depth exceeded in comparison

既然n等于120000，这个方法就行不通了。 所以我的问题是：迭代Stern_Brocot树的一部分是什么好方法？（如果有另一种方法来迭代互质整数，那也不错）。在

Answer 1

这是一个非递归实现

def Stern_Brocot(n):
    states = [(0, 1, 1, 1)]
    result = []
    while len(states) != 0:
        a, b, c, d = states.pop()
        if a + b + c + d <= n:
            result.append((a+c, b+d))
            states.append((a, b, a+c, b+d))
            states.append((a+c, b+d, c, d))
    return result

Answer 2

在定义Stern_Brocot之前，添加sys.setrecursionlimit(120000)。这将把程序的递归限制设置为120000。在

所以，你可以这样做：

import sys
sys.setrecursionlimit(120000)

def Stern_Brocot(n,a=0,b=1,c=1,d=1):
    if(a+b+c+d>n):
        return 0
    x=Stern_Brocot(n,a+c,b+d,c,d)
    y=Stern_Brocot(n,a,b,a+c,b+d)
    if(x==0):
        if(y==0):
            return [a+c,b+d]
        else:
            return [a+c]+[b+d]+y
    else:
        if(y==0):
            return [a+c]+[b+d]+x
        else:
            return [a+c]+[b+d]+x+y