Socorro com Recursividade?

Cara é mais ou menos isso sim. Eu já fiz algo do tipo.

Verifica os filhos de P1 se tem P5, se os os filhos de P1 tem P5 e assim sucessivamente.

Eu fiz algo do tipo, mas no meu caso eu não procurava se tinha as ocorrências e sim todos os filhos de um pai.

Era algo do tipo:

//ids é o vetor com ids
int[] metodo(int[] ids) {

/*aqui eu percorria cada item do vetor pesquisando no banco, e armazenava em outro vetor os filhos. */

/enquanto tinha filhos eu continuava a chamar esse mesmo método passando os ids que havia encontrado como parâmetro/
metodo(vetorFilhos);

/Se não tinha mais filhos eu retornava a lista com todos os ids/
}

Complementando essa solução que foi dada, vou falar um pouco da sua preocupação de que o programa entre em loop infinito.

Se a árvore não tiver “voltas” para niveis superiores, como essa aqui, então não precisa se preocupar pois não vai entrar em loop, ele vai pesquisar até o final e o máximo que acontece é não encontrar.

|----> B |---> E | | A----|----> C ----|---> F | |----> D

Agora se ela for desse jeito, em que um item pode ser filho de outro que vem mais abaixo (eu entendi que isso pode acontecer no seu caso, se P1 for filho de P5)

|----> B |---> E | | A----|----> C ----|---> F ---> G | | |----> D | | volta p/ A <------------|
Para essa situação, uma possível solução é: Cada vez que analisar um item, por exemplo, (A), adicione-o em uma lista de itens já processados. Quando chegar no item (F), o programa vê que o item A já foi explorado e o ignora, continuando a busca pelo (G).