有没有一种只调用一次这个递归函数的有效方法？

Question

这里是一个代码，它可以找到给定值 n 的递归关系给出的函数 T 的值：

def T(n):
  if n <= 0:
    return 1
  else:
    return T(n-1) + (n-1) * T(n-2)
    
print T(3)

#output
2

但是，代码调用函数 T 两次。我在第二个 return 之前添加了 print 语句来显示：

def T(n):
  if n <= 0:
    return 1
  else:
    print (T(n-1) + (n-1) * T(n-2))
    return T(n-1) + (n-1) * T(n-2)
    
print T(3)

#output
1
2
1
2

有没有一种有效的方法可以只调用函数 T 一次？我正在使用 Python 2。我想要简短的东西，不要太复杂。

Answer 1

您将调用 T 2^(n-1) 次，其中 n >1，如果不删除递归，则无法将其减少到仅一次。

如果你的意思是说你想减少重复调用，比如T(3)调用T(2)和T(1)，而T(2)也调用T(1)，那么你需要使用名为 memoization

的过程

例如，使用结果输入字典。

seen = dict() 

def T(n):
  if n <= 0:
    return 1
  else:
    if n in seen:
        return seen[n] 
    else:
        result = T(n-1) + (n-1) * T(n-2)
        seen[n] = result
        return result 

print(T(3))

Answer 2

您可以将函数从 T(n) = T(n-1) + (n-1)*T(n-2) 重新定义为 T(n+1) = T(n) + n*T(n-1)，这将允许递归向前移动而不是向后移动，前提是您给它当前的 n 和以前的值。通过只需要前一个值而不是前两个值，递归级数更容易掌握。

def T(N,n=1,Tm=1,Tn=1):  # n,Tm,Tn represent n,T(n-1),T(n)
    if n>N: return Tm    # stop at n=N+1 and return T(n-1)
    return T(N,n+1,Tn,Tn+n*Tm)

注意：当 n>N 时函数 returns a 是为了覆盖 N 为零的情况。

实际上，这也可以通过将停止条件移动到 N+2 而不是 N+1 来编写而无需转置函数：

def T(N,n=2,Tn_2=1,Tn_1=1):   # n,Tn_2,Tn_1 represent n,T(n-2),T(n-1)
    if n==N+2: return Tn_2    # stop at n=N+2 and return T(n-2)
    return T(N,n+1,Tn_1,Tn_1+(n-1)*Tn_2)

可以进一步简化为：

def T(N,n=1,a=1,b=1): return T(N-1,n+1,b,a*n+b) if N else a

有没有一种只调用一次这个递归函数的有效方法？

Is there an efficient way of invoking this recursive function only once?

python

recursion

python-2.7