Como contar ocorrências de uma substring em uma string sem API da classe String em Java

Não consigo fazer esse programa. Me ajudem por favor. Obrigada. :

Faça um programa que leia uma frase e conta a quantidade de ocorrências da SubString também informada pelo usuário. A quantidade deve ser calculada por um método estático recursivo. Faça um versão iterativa desse método também. Não use a API da classe String.

Exemplo:
Entrada - frase: “Comprei um presente para você.” / substring: “pre”
Saida: 2