Contar quantas ocorrências de um número há em outro, de forma recursiva

Apenas para constar, recursão não é a forma mais eficiente de resolver este problema. Dito isso, vamos à solução.

---

Um dos problemas da sua função é que eu posso chamá-la assim: verifica(num, -190, aux) e pronto, já baguncei a contagem, pois o contador começará em -190. Se o contador deve sempre começar em zero, ele não deveria ser um parâmetro.

A ideia básica do algoritmo é:

• comparo os 2 últimos algarismos do número n, se forem iguais a k, incremento o contador
• divido n por 10 (eliminando assim o último dígito) e continuo a contagem
• se n chegar a zero, fim do algoritmo

Assumindo que o número k sempre tem 2 dígitos (já que isso não é verificado), ficaria assim:

def verifica(n, k):
    if n == 0:
        return 0

    if n % 100 == k:
        c = 1
    else:
        c = 0
    return c + verifica(n // 10, k)

n, k = 2135219877, 21
print(f'O número {k} ocorre {verifica(n, k)} vezes no número {n}')

Como um return retorna o valor e encerra a execução da função, o bloco else no primeiro if é desnecessário. Também tirei o print de dentro da função, pois ela só deveria retornar o valor, e quem a chama que faça o que quiser com ele (inclusive imprimir, se for o caso). Sem contar que, por ser recursiva, são feitas várias chamadas (uma para cada dígito de n) e aí seriam impressas várias mensagens, desnecessariamente.

Para obter os 2 últimos dígitos de n, basta pegar o resto da divisão por 100, usando o operador %. Depois eu vejo se é igual a k, e somo 1 se for o caso.

Depois, esse valor é somado com o resultado da contagem no restante do número (o resultado da divisão de n por 10).

Vale lembrar que verifica(111, 11) retorna 2, pois os 2 últimos dígitos de 111 são 11, e depois eu divido 111 por 10, resultando em 11, o que contabiliza outra ocorrência de 11.

---

Como já dito, o algoritmo funciona apenas se k tiver exatamente 2 dígitos (ou se for menor que 10, por exemplo, se n for 10303 e k for 3, a contagem contabiliza 2).

Mas se a ideia é deixar o algoritmo mais "genérico", você pode verificar a quantidade de dígitos de k e usar esse valor no cálculo - de forma geral, se k tiver x dígitos, basta pegar o resto da divisão por 10^x.

Outro detalhe é que não precisa ir até n ser igual a zero. Se n for menor que k, já posso parar a verificação, pois a partir daí não terá mais nenhuma ocorrência:

import math

def qtd_digitos(numero):
    numero = abs(int(numero))
    return (1 if numero == 0 else math.floor(math.log10(numero)) + 1)

def verifica(n, k):
    if n < k:
        return 0
    if n % (10 ** qtd_digitos(k)) == k:
        c = 1
    else:
        c = 0
    return c + verifica(n // 10, k)

---

Lembrando que a solução recursiva não é a ideal para este caso. Isso porque muitas chamadas recursivas podem causar um estouro de pilha se a quantidade de chamadas for suficientemente grande.

Nesse caso, um loop simples já resolve. Além disso, falta verificar alguns corner cases, quando ambos os valores são zero, ou quando somente k é zero:

import math

def qtd_digitos(numero):
    numero = abs(int(numero))
    return (1 if numero == 0 else math.floor(math.log10(numero)) + 1)

def verifica(n, k):
    if n == 0 and k == 0:
        return 1
    c = 0
    qtd = qtd_digitos(k)
    while (k == 0 and n > k) or (k != 0 and n >= k):
        if n % (10 ** qtd) == k:
            c += 1
        n //=10
    return c

print(verifica(0, 0)) # 1
print(verifica(100, 0)) # 2