Find number of ways paint a fence with n posts and k colors

Find out the number of ways of painting a fence with n posts and k colors so that not more than two consecutive posts have the same color.

Hint

Considers two possibilities for the last post:

Different color: Number of ways = (k - 1 choices of color for the last post) * (ways to paint remaining n-1 posts)
Same color as the previous post: Number of ways = (k - 1 choices of color for the last two posts) * (ways to paint remaining n-2 posts)

Combine these two possibilities, we get the total number of ways to paint 'n' posts.

Python
Javascript

# Python implementation

def count(n, k):
  if n == 1:
    return k

  if n == 2:
    return k * k

  return (k - 1) * (count(n - 1, k) + count(n - 2, k))

n = 3
k = 2

print(count(n, k))

// Javascript implementation

function count(n, k) {
  if (n == 1) {
    return k;
  }

  if (n === 2) {
    return k * k;
  }

  return (k - 1) * (count(n - 1, k) + count(n - 2, k));
}

const n = 3;
const k = 2;

console.log(count(n, k));