Como calcula resto de divisão inteira recursivamente

Sim, é possível.

Uma divisão pode ser entendida como uma série de subtrações:

11 / 2 =
11 - 2 = 9
9 - 2 = 7
7 - 2 = 5
5 - 2 = 3
3 - 2 = 1

Como 1 é < 2, então 1 é o resto da divisão de 11 por 2.
Como tivemos 5 subtrações, então 11 divididos por 2 é 5.

Para números negativos o processo é o mesmo, só que com somas no lugar de subtrações.

Muito obrigado pela orientação.