Python递归查询

Question

我想确认我是否理解如何在 python 中以递归形式重写这个函数。其功能是:

# Recurrence Relation
# F(n) = 7 * F(n-1) + 2 * F(n-2)
# F(1) = 1; F(2) = 1
# print (rr(4))

我的递归代码是:

def rr(n):
  return (2 * rr(n-1) + 2 * rr(n-2))

这是正确的吗？另外，我如何“打印”rr(4)，因为我认为它只能在运行程序时进行评估。

Answer 1

您缺少基本案例。

# F(1) = 1; F(2) = 1

考虑:

def rr(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return 7 * rr(n-1) + 2 * rr(n-2)

此外，您的递归案例与递归关系不匹配。它有一个 2，其中出现了一个 7。

>>> def rr(n):
...     if n == 1:
...         return 1
...     elif n == 2:
...         return 1
...     else:
...         return 7 * rr(n-1) + 2 * rr(n-2)
... 
>>> print rr(4)
65