Задача (рекурсивная)

[Witaliy]

Здравствуйте.
У меня возник вопрос с задачей: не могу никак сделать рекурсивной функции.

Вот самая задача:
Для украшения елки Петрик имеет в своем распоряжении гирлянду из N ламп и K разных красок для их раскрашивания. Сколькими способами он может это сделать, если никакие 2 одинаковых цвета не должны быть рядом?

Технические условия. Входные данные:
Количество ламп N та количество разных красок K.
(1 <= K,n <= 15).
Входные данные:
Количество способов раскрашивания. Если Петрик не может раскрасить гирлянду за описанными требованиями, вывести -1.

Пример:
Ввод
6 2
Вывод
2

Нужно хоть кусочек кода, или самое описание алгоритма.
Очень прошу помочь, никогда не получаются такие задачи....

Спасибо!

[Min]

здесь походу не рекурсия, а динамика

[Min]

колличество= k*((k-1)^(n-1))
все)))
и если получился 0, то выводить -1