Recall that a function is harmonic if its Laplacian is zero. Let $\mathrm{Harm}(n,k)$ denote the vector space of $n$-variate harmonic polynomials that are homogeneous with degree $k$. When working with spherical harmonics, we endow this vector space with the inner product $\langle\cdot,\cdot\rangle$ defined in terms of the uniform probability measure over the unit sphere $\mathbb{S}^{n-1}$. Many computations involving spherical harmonics pass to an implicit orthogonal basis for this inner product space, but for computations, it is sometimes helpful to have an explicit basis.

Question: Is there a "nice" choice of orthogonal basis for $(\mathrm{Harm}(n,k),\langle\cdot,\cdot\rangle)$? In particular, is there a choice for which there exists a fast algorithm to compute an arbitrary decomposition in the basis (à la FFT)?