  This paper introduces the recursive sweeping preconditioner for the numerical
solution of the Helmholtz equation in 3D. This is based on the earlier work of
the sweeping preconditioner with the moving perfectly matched layers (PMLs).
The key idea is to apply the sweeping preconditioner recursively to the
quasi-2D auxiliary problems introduced in the 3D sweeping preconditioner.
Compared to the non-recursive 3D sweeping preconditioner, the setup cost of
this new approach drops from $O(N^{4/3})$ to $O(N)$, the application cost per
iteration drops from $O(N\log N)$ to $O(N)$, and the iteration count only
increases mildly when combined with the standard GMRES solver. Several
numerical examples are tested and the results are compared with the
non-recursive sweeping preconditioner to demonstrate the efficiency of the new
approach.
