Recent advances in machine-learned interatomic potentials largely benefit from the atomistic representation and locally invariant many-body descriptors. It was however recently argued that including three- (or even four-) body features is incomplete to distinguish specific local structures. Utilizing an embedded density descriptor made by linear combinations of neighboring atomic orbitals and realizing that each orbital coefficient physically depends on its own local environment, we propose a recursively embedded atom neural network model. We formally prove that this model can efficiently incorporate complete many-body correlations without explicitly computing high-order terms. This model not only successfully addresses challenges regarding local completeness and nonlocality in representative systems, but also provides an easy and general way to update local many-body descriptors to have a message-passing form without changing their basic structures.