为什么递归在某些情况下与动态规划不同？

Question

我正在研究动态规划，我遇到了一个问题，即在mxn网格中，如何找到从点“a”到点“b”的唯一路径。你只能向右或向下移动。我的问题是，为什么下面的递归方法比后面描述的动态方法慢得多？你知道吗

---

递归：

def upaths(m,n):
    count = [0]
    upathsR(m,n, count)
    return count[0]

def upathsR(m,n,c):
    # Increase count when you reach a unique path
    # When you reach 1 there is only one way to get to an end (optimization)
    if m==1 or n==1:
        c[0]+=1
        return

    if m > 1:
        upathsR(m-1,n,c)
    if n > 1:
        upathsR(m,n-1,c)

动态：

def upaths(m, n):
    count = [[1 for x in range(n)] for x in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            count[i][j] = count[i][j-1] + count[i-1][j]
    return count[-1][-1]

通常递归有可以记忆的重复调用，但在这种情况下，我看到了唯一的调用，即使这样递归也慢得多。有人能解释为什么。。你知道吗

---

根据答案的建议，它运行得更快。电话也不是唯一的。你知道吗

新的递归方法： 定义路径（m，n）： d=dict（） 返回上游（m，n，d）

def upathsR(m,n,d):
    if (m,n) in d:
        return d[(m,n)]

  if m==1 or n==1:
      return 1

  d[(m,n)] = upathsR(m-1,n,d)+upathsR(m,n-1,d) 
  return d[(m,n)]