Para hacerla recursiva sería:

int buscar_c(char *cad, char c) {
    if(*cad=='\0')
        return 0;
    return (*cad==c)+buscar_c(cad+1,c);
 }

El else tuyo no tiene sentido.
Éste código funciona para las implementaciones que consideren 1 como resultado de un true, que son todas las que conozco.

Cómo te había explicado una operación booleana en C se evalúa a 1 si el resultado es true y 0 si el resultado es false. El código aprovecha este hecho en el trozo de código *cad==c, es decir, si el carácter actual de la cadena es igual a carácter c devolverá 1, caso contrario 0.
Este resultado se suma a lo que devuelva la siguiente llamada a buscar_c apuntando al siguiente carácter de la cadena. Y todo esto es lo que retornará la función.
Por recursividad los resultados se irán acumulando y cuando hayan retornado todas las funciones la última entregará el resultado esperado.

-------------------- Fuera del tema ---------------------------
Por otra parte es importante recalcar el cad+1 en vez de ++cad en el argumento de buscar_c. Esto es debido a que además de incrementar cad en 1 en otra parte se hace uso del valor de esa variable. Uno no sabe qué operando evaluará antes C en una operación matemática. Si hubiera sido ++cad, al evaluar *cad==c lo haría con el siguiente carácter al que nos interesa y el programa fallaría y por eso he optado por no modificar dicha variable. Pero todo esto tiene que ver con los puntos de secuencia, algo de lo que tendrás oportunidad de aprender más adelante.