Печатает число форм бинарного дерева

Question

Я пытаюсь выяснить, почему мой код не работает для возвращения shapesbinary tree может принять

public static long shapes (int n) { 
if (n == 0) return 1; 
if (n == 1) return 1; 
long result = 0; 
for (int i = 0; i < n; i++) { 
    result = result + shapes(i-1)*shapes(n-i); 
    } 
return result 
} 

это должно следовать правилам
L(0) = 1
L(1) = L(0)*L(0) = 1
L(2) = L(0)*L(1) + L(1)*L(0) = 1 + 1 = 2
L(3) = L(0)*L(2) + L(1)*L(1) + L(2)*L(0) = 2 + 1 + 2 = 5

Я думаю, что это связано с тем, что я звоню shapes(i-1), но я не уверен.

Answer 1

Вы, скорее всего, получили ошибку переполнения стека на основе shapes(n-i). n-i, когда i равно 0, будет фигурами (n). Это снова будет проходить через цикл цикла и формы вызова (n-i) или фигуры (n) в бесконечном цикле.

Примечание: После того, как п> 35 результат переполняется длинный

public static long shapes(int n) 
    { 
     if (n == 0) return 1; 
     if (n == 1) return 1; 
     long result = 0; 
     for (int i = 0; i < n; i++) 
     { 
      result = result + shapes(i) * shapes(n - i - 1); 
     } 
     return result; 
    } 

результаты:

shapes 0 = 1 
shapes 1 = 1 
shapes 2 = 2 
shapes 3 = 5 
shapes 4 = 14 
shapes 5 = 42 
shapes 6 = 132 
shapes 7 = 429 
shapes 8 = 1430 
shapes 9 = 4862 

Как Ричард Планкетт указывает решение имеет серьезные проблемы с производительностью. Одна из стратегий решения этой проблемы, когда вы повторяете тот же расчет, что и в этом случае, заключается в том, чтобы хранить предыдущие результаты, а затем искать их вместо пересчета. В приведенном ниже решении используется это повышение производительности.

private static Dictionary<int, System.Numerics.BigInteger> results = 
     new Dictionary<int, System.Numerics.BigInteger>(); 

    public static System.Numerics.BigInteger shapes(int n) 
    { 
     if (n == 0) return 1; 
     if (n == 1) return 1; 
     System.Numerics.BigInteger result = 0; 
     for (int i = 1; i <= n; i++) 
     { 
      System.Numerics.BigInteger left = 0; 
      System.Numerics.BigInteger right = 0; 
      if (!results.ContainsKey(i - 1)) 
      { 
       left = shapes(i - 1); 
       results[i - 1] = left; 
      } 
      else 
      { 
       left = results[i - 1]; 
      } 

      if (!results.ContainsKey(n - i)) 
      { 
       right = shapes(n - i); 
       results[n - i] = right; 
      } 
      else 
      { 
       right = results[n - i]; 
      } 

      result += left * right; 
     } 
     return result; 
    }