Python递归查询

2024-03-28 22:41:59 发布

您现在位置:Python中文网/ 问答频道 /正文

我想确认我是否理解如何在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),因为我认为只有在运行程序时才能计算它


Tags: 函数代码程序功能returndefrr形式
3条回答

您没有添加基本情况,这将是递归的基础

def rr(n):
    if n < 1:
        raise "Invalid input"
    if n <= 2:
        return 1
    return 7 * rr(n-1) + 2 * rr(n-2)

其运行方式如下:

rr(4) = 7 * rr(4-1) + 2 * rr(4-2)
      = 7 * rr(3) + 2 * rr(2)
      = 7 * (7 * rr(3-1) + 2 * rr(3-2)) + 2 * 1
      = 7 * (7 * r(2) + 2 * r(1)) + 2
      = 7 * (7 * 1 + 2 * 1) + 2
      = 7 * 9 + 2
      = 65

如您所见,如果没有基本情况,您的函数将无限运行,因为rr(2)rr(1)永远不会解析;相反,它们一直调用相同的递归路径rr(1).. rr(0).. rr(-1)..etc

您的代码将执行纯堆栈溢出,因为您尚未定义停止条件,即F(1)和F(2)的起始值。根据n的值在函数中添加测试以处理这些情况

你错过了基本案例

# 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

相关问题 更多 >