Python中单个列表的递归广义连分数

Question

我需要写一个recursive function，它接受一个表示广义连分数的列表L（奇数长度），并返回相应的有理数

列表L总是奇数的原因是需要用连分数创建有理数

L[0] + L[1]/(L[2] + L[3]/L[....]))

我把它看作两个列表a，b。基本上在这种情况下，a是L[偶数]，b是L[奇数]

我的基本情况是在最后3分钟

if n == 3: #base case
    return L[0] + (L[1] / L[2])

我不知道如何推进递归中的分子和分母。 我一直在尝试（GCF2R是函数）（L是列表）（n=len（L））

if n > 3:
    return L[0] + (L[n-2] / GCF2R(L[0:n]))

但是由于递归只发生在分母中，分子不会随着每次递归而改变

我知道我错过了一些基本步骤。非常感谢您对我的帮助

Answer 1

如果你看广义连分数的形式，你可以看到子结构：

                  L[1]
L[0] +              
                         L[3]
         L[2] +           -
                               L[5]
                   L[4] +         -
                                ...

基本上，GCF要么是整数，要么是形式为a + b/c的表达式，其中a和b是整数，c本身就是GCF

由此，递归自然如下：

def GCF2R(L):
    if len(L) == 1:
        return L[0]
    else:  # Assume len(L) > 2
        return L[0] + L[1]/GCF2R(L[2:])

删除前两个元素，然后在其余元素上递归

Answer 2

我想你应该把这些从末端剥掉，而不是从前面剥掉：

def GCF2R(L):
    if len(L) == 1:
        return L[0]
    else:
        return L[-2]/L[-1] + GCF2R(L[:-2])

我想如果你通过了长度，你就不需要每次都剪一个新的列表：

def GCF2R(L,N):
    if N == 1:
        return L[0]
    else:
        return L[N-2]/L[N-1] + GCF2R(L,N-2)