这里的catalan()函数是如何工作的？

Question

我无意中发现了这个函数来计算加泰罗尼亚数字：

def catalan(n):
    if n == 0:
        return 1
    else:
        sum = 0
        for i in range (n):
            sum +=(catalan(i))*(catalan(n-1-i))
    return sum

我的问题是sum如何获得值，例如，当n=2

sum = (catalan(0))*(catalan(2-1-0)) + (catalan(1))*(catalan(2-1-1) + (catalan(2))*(catalan(2-1-2))

如果我们只为catalan(2-1-0)定义值，那么catalan(2-1-0)或0以外的任何参数如何获得它的值？

Answer 1

笔与纸张评价

加泰罗尼亚(0)

# 1

加泰罗尼亚人(1)

#  = 0 + catalan (0) * catalan (1-1-0)
#  = 0 + 1 * catalan (0)
#  = 0 + 1 * 1
#  = 0 + 1

加泰罗尼亚(2)

#  = 0
#  + catalan (0) * catalan (2-1-0)
#  + catalan (1) * catalan (2-1-1)

#  = 0 
#  + 1 * catalan (1) 
#  + 1 * catalan (0)

#  = 0
#  + 1 * 1
#  + 1 * 1

#  = 1
#  + 1

#  = 2

加泰罗尼亚人(3)

#  = 0
#  + catalan (0) * catalan (3-1-0)
#  + catalan (1) * catalan (3-1-1)
#  + catalan (2) * catalan (3-1-2)

#  = 0
#  + 1 * catalan (2) 
#  + 1 * catalan (1)
#  + 2 * catalan (0)

#  = 0
#  + 1 * 2
#  + 1 * 1
#  + 2 * 1

#  = 0
#  + 2
#  + 1
#  + 2

#  = 5

废品循环

让我们来看看一个天真的斐波纳契过程-

def fib (n):
  if n < 2:
    return n
  else:
    return fib (n-1) + fib (n-2)

这个过程作为一个原型树递归是有指导意义的，但是它是计算Fibonacci数的糟糕方法，因为它做了大量的冗余计算。请注意，fib(3)的整个计算(几乎一半的工作量)都是重复的。事实上，不难证明该过程计算fib(1)或fib(0)的次数(通常是上述树中的叶数)正是fib(n + 1)。为了了解这种情况有多糟糕，人们可以看到fib(n)的值随n-http://www.sicpdistilled.com/section/1.2.2/而呈指数增长。

​

​

一个类似的问题正在发生在您的catalan程序，但更糟糕的程度。调用catalan(3)将产生6个额外的catalan调用

# catalan (3)
#  = 0
#  + catalan (0) * catalan (3-1-0)
#  + catalan (1) * catalan (3-1-1)
#  + catalan (2) * catalan (3-1-2)
#  ...
#  = 5

可以使用多种技术来避免这个问题。请按照上面的引文来获得更多关于这个主题的帮助。