algorithm - 递归关系：编写递归关系

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(root-1)+T(n-root)]

Answer 1

您的代码已经是二叉树数量的递归关系，只是表示为一种算法。我猜你被卡住了，因为你有一个循环求和。这是标准数学符号——循环值从 1..n 更改为 0..n-1 以更标准：

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

手写（或使用 LaTeX）你会使用求和符号而不是sum，但它在逻辑上是相同的。

这是加泰罗尼亚数字的递归关系（尽管通常C(1)情况下不会明确列出），链接的维基百科页面还包括递归关系的封闭形式解决方案及其正确性证明。