Как здесь работает функция 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))

Как catalan(2-1-0) или для любого другого аргумента, кроме 0, получил его значение, если мы определили только значение для n=1?

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 & mdash; SICP - рекурсия дерева

Аналогичная проблема происходит с вашей catalan программой, но в еще меньшей степени. Вызов catalan(3) даст шесть (6) дополнительных catalan вызовов

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

Существует множество методов, позволяющих избежать этой проблемы. Следуйте цитате выше для получения дополнительной помощи по теме.