Может быть просто начинать с обратного?
Брать N идти от него к нулю, нашли первое попавшееся число которое сумма чисел которого равна 9 и все.
Или сумма числе может быть двузначной и трехзначной и рекурсивное сложение чисел не следует делать?