Reurrence 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 (корень-1)+T(n-корень)]

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) case не был бы указан в явном виде), а ссылка на страницу Википедии также включает решение в закрытой форме для рекуррентного отношения и доказательства его правильности.