Рекурсивная треугольная строка Паскаля, большая стоимость O

Я готовлюсь к собеседованию по CS и решил попробовать придумать собственную проблему и решить ее рекурсивно.

Вопрос, который я пытаюсь решить, заключается в следующем: я хочу иметь возможность написать рекурсивную функцию, которая находит n-ю строку треугольника Паскаля.

Ex pascals(1) -> 1
   pascals(2) -> 1,1
   pascals(3) -> 1,2,1

Я считаю, что решил эту функцию. Чтобы начать работу с базовым случаем, нужна вспомогательная функция.

function int[] nthPascal(int[] a, int n){
  // in the case that the row has been reached return the completed array
  if(n==1){
    return a;
  }
  // each new row of pascal's triangle is 1 element larger. Ex 1, 11, 121,1331 etc. 
  int[] newA = new int[a.length()+1];

  //set the ends. Technically this will always be 1.
  // I thought it looked cleaner to do it this way. 
  newA[0]=a[0];

  newA[newA.length-1]=a[a.length-1];

  //so I loop through the new array and add the elements to find the value.
  //ex 1,1 -> -,2,- The ends of the array are already filled above
  for(int i=1; i<a.length; i++){

    // ex 1+1 = 2 for 1,1 -> 1,2,1
    newA[i]=a[i-1]+a[i]
  }
  //call the recursive function if we are not at the desired level
  return nthPascal(newA,n-1);
}

/**
*The helper function
*/
public int[] helperPascal(int n){
  return nthPascal(int[] {1},n);
}

У меня вопрос: как мне узнать стоимость bigO?

Я знаком с общими затратами алгоритмов и с тем, как их найти. Рекурсия в этом сбивает меня с толку.

Я знаю, что это явно непостоянно, n, nlogn и т. Д. Я думал, что это 3 ^ n?

Я поискал пример и нашел: Последовательность треугольных строк Паскаля и Какова продолжительность выполнения этого алгоритма? (Рекурсивный треугольник Паскаля). Но я считаю, что они пытаются найти конкретный элемент в данном месте. Я не смог найти никого, кто реализовывал бы треугольник Паскаля таким образом и говорил бы о стоимости bigO.

Это потому, что есть лучший способ написать рекурсивную строку, находящую функцию паскаля? Если да, поделитесь пожалуйста :)