复发关系：写一个复发关系

Question

我想为这个算法写一个递归关系。但是我对“根”变量感到困惑。任何人都可以帮助我或者建议我一个更好的递归算法来计算有n个节点的可能二叉树的数量？

Algorithm countTrees(n) { 
    if(n<=1) then return 1 
    else { 
     sum = 0 
     for root=1 to root<= n do { 
      left = countTrees(root-1) 
      right = countTrees(n-root) 
      sum = sum+(left*right) 
     } 
     return sum 
    } 
} 

我已经写了这个到目前为止，但我不知道如何处理根来解决这个问题。

T（N）= N [T（根-1）+ T（N-根）]

Answer 1

您的代码是已经为二叉树的数目，只是表示为算法的递归关系。我想你被卡住了，因为你总结了一个循环。这是从1..1改为循环值标准的数学notation--至0到n-1是更标准：

C(0) = C(1) = 1 
C(n) = sum(C(i) * C(n-i-1) for i = 0...n-1) 

手工编写它（或乳胶），你会使用总和符号而不是sum，但它在逻辑上是相同的。

这是Catalan numbers递推关系（尽管通常的情况下C(1)将不明确列出），并且还连接Wikipedia页面包括用于它的正确性的递推关系和证明的封闭形式解。