17.9 Recursive Functions

Stan supports recursive function definitions, which can be useful for some applications. For instance, consider the matrix power operation, \(A^n\), which is defined for a square matrix \(A\) and positive integer \(n\) by \[ A^n = \begin{cases} \ \mbox{I} & \mbox{if } n = 0, \mbox{ and} \\[3pt] \ A \, A^{n-1} & \mbox{if } n > 0. \end{cases} \]

where \(\mbox{I}\) is the identity matrix. This definition can be directly translated to a recursive function definition.

  matrix matrix_pow(matrix a, int n);

  matrix matrix_pow(matrix a, int n) {
    if (n == 0)
      return diag_matrix(rep_vector(1, rows(a)));
    else
      return a *  matrix_pow(a, n - 1);
  }

The forward declaration of the function signature before it is defined is necessary so that the embedded use of matrix_pow is well-defined when it is encountered. It would be more efficient to not allow the recursion to go all the way to the base case, adding the following conditional clause.

    else if (n == 1)
      return a;