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))

如果我们只为 n=1 定义值，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)

这个过程作为原型树递归很有启发性，但它是计算斐波那契数的糟糕方法，因为它进行了太多冗余计算。请注意下面 fib(3) 的整个计算，几乎一半的工作是重复的。事实上，不难证明程序计算 fib(1) 或 fib(0) 的次数（通常是上述树中的叶子数）恰好是 fib(n + 1)。要了解这有多糟糕，可以证明 fib(n) 的值随 n 呈指数增长 - SICP - Tree Recursion

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

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

有多种方法可以避免这个问题。按照上面的引用获取有关该主题的更多帮助。

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

How does the catalan() function works here?

python

recursion

catalan