1117: K-进制数-递归求解

解题思路:
    认真看题，找规律，可以发现该题目可以通过递归求解：

n=1时，[1-9]

n=2时，9*[0-9]

n=3时，9*{n-1的}+9*{n-2的}

依次类推……

参考代码:

n = int(input())
k = int(input())


def func(n, k):
    if n == 1:
        return k-1
    elif n == 2:
        return (k-1)*k
    else:
        return (k-1)*func(n-1, k) + (k-1)*func(n-2, k)


print(func(n, k))