# C++ easy to understand recursive solution

• We define the function `numWays(n, k)` to return the number of ways to paint n fences with `k` colours such that the first fence is always just a `single` colour and if the `first two` fences are always a `single` colour. i.e. Suppose we have 3 colours, (red, green, blue), then we assume that the first fence will always be red, and if the first 2 fences are of the same colour, they are always red.

Suppose the first fence is always red, then we can determine the number of ways to paint the remaining `n-1` fences with colours (green, blue). This gives us `(k-1) * numWays(n-1)`.

Suppose the first 2 fences are always red, then we can determine the number of ways to paint the remaining `n-2` fences with colours (green, blue). This gives us `(k-1) * numWays(n-2)`.

Hence, the total ways to paint `n` fences with `k` colours is `k * numWays(n, k)`.

The code below probably won't pass the OJ since it's not memoized, but it's easy to memoize it.

``````int numWays(int n, int k) {
// Painting 2 fences such that either the 2nd fence alone
// is just a single colour, OR the first 2 fences are just a single
// colour is possible by painting the 2nd fence with 1 colour
// and the first fence with (k-1) colours, or both fences with
// the one colour. i.e. ((k-1) + 1) = k.
if (n == 2) return k;
if (n == 1) return 1; // Just painting 1 fence with 1 colour.
if (n < 1) return 0;
return (k-1) * (numWays(n-1, k) + numWays(n-2, k));
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.