1)Использовать рекурсию здесь нежелательно. Слишком сложно будет уместить в голове происходящее.
2)На мой взгляд, считать нужно так, чтобы полученные значения не вовлекались в процесс счета.
3)Иногда стоит создать решение типа "лишь бы работало" - без ограничений задачи, а затем, как следует на него насмотревшись, построить решение по всем правилам.