时间戳

首页 > 解决方案 > 我试图用python为斐波那契序列创建一个递归函数

python-3.x - 我试图用python为斐波那契序列创建一个递归函数

问题描述

该函数应该返回斐波那契数列的前 n 个数字的列表，但它什么也没返回，我想知道为什么


def fibonacci(n, sequence=[0, 1], originalN=0):
    print(n, sequence[:-2])

    if n <= 0:
        print(n)
        return(sequence[:-2])

    nextValue = sequence[-1] + sequence[-2]
    sequence.append(nextValue)

    

    fibonacci(n-1, sequence, originalN)

print(fibonacci(10))

main 函数中的一些打印函数被留下用于调试目的

标签： python-3.x

解决方案

你错过了一个return声明。递归调用不会返回递归堆栈中的切片。您的斐波那契数列甚至使用前面的代码构建的唯一原因是它们都共享同一个列表对象。

def fibonacci(n, sequence=[0, 1], originalN=0):
    if n <= 0:
        return (sequence[:-2])

    nextValue = sequence[-1] + sequence[-2]
    sequence.append(nextValue)

    return fibonacci(n-1, sequence, originalN)

print(fibonacci(10))

输出：

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

编辑：为了澄清，return您之前的语句只返回了来自最深调用的序列（递归树上的叶子到其父级（当 n 为 1 时），但return递归调用也需要该语句来传递这个值递归树。

您可以避免使用递归堆栈并进行更有效的斐波那契序列计算，如下所示：

def fibonacci(n):
    sequence = [0, 1]
    for i in range(2, n):
        sequence.append(sequence[-1] + sequence[-2])
    return sequence

编辑 2：正如@Clockwork-Muse 推荐的那样，一种更 Python 的方式是使用无限生成器而不是返回列表。您还可以根据需要生成任意长的序列。这是我对这种方法的看法：

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

sequence = fib()

演示（n 可以是任何东西，就像fib生成器对象一样，并将继续生成序列中的下一个数字）：

n = 10
for i in range(n):
    print(next(sequence), end=", ")

输出：0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

推荐阅读