2024-03-28 22:41:59 发布
网友
我想确认我是否理解如何在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),因为我认为只有在运行程序时才能计算它
您没有添加基本情况,这将是递归的基础
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
rr(2)
rr(1)
rr(1).. rr(0).. rr(-1)..etc
您的代码将执行纯堆栈溢出,因为您尚未定义停止条件,即F(1)和F(2)的起始值。根据n的值在函数中添加测试以处理这些情况
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的地方
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
您没有添加基本情况,这将是递归的基础
其运行方式如下:
如您所见,如果没有基本情况,您的函数将无限运行,因为
rr(2)
和rr(1)
永远不会解析;相反,它们一直调用相同的递归路径rr(1).. rr(0).. rr(-1)..etc
您的代码将执行纯堆栈溢出,因为您尚未定义停止条件,即F(1)和F(2)的起始值。根据
n
的值在函数中添加测试以处理这些情况你错过了基本案例
考虑:
另外,您的递归事例与递归关系不匹配。它有一个
2
出现在7
的地方相关问题 更多 >
编程相关推荐