Hola.
Aparte de la solución (cortesia de Phicar) considera que un número (no como ente matematico) es una cadena de bytes, es decir, si te lo dan almacenado como variable puedes representarlo como cadena (array de bytes o caracteres) y si ya te lo dan así, por ejemplo de la entrada estándar, más fácil aun, no tienes que hacer ese proceso. En definitiva la función recursiva solo tendria que recorrer dicho array mediante indices o puntero y buscar la coincidencia. Porsupuesto esto es valido si el enunciado no lo restringe.
Un saludo.