algorithm - 递归关系 : Writing a recurrence relation

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，但逻辑上是相同的。

这是 Catalan numbers 的递归关系(尽管通常不会明确列出 C(1) 情况)并且链接的维基百科页面还包括递归关系的封闭形式解决方案及其正确性证明。