// solving problems with recursion: divide & conquer
// - if you know the answer, return!
// - if not, solve a smaller (but similar)
//   version of the problem recursively;
//   return the combination of this result
//   with some aspect of the current
//   problem























// 2^4 = 2 * 2 * 2 * 2
// 



























// 2^4 = 2 * 2^3 = 2 * 8 = 16
// 2^3 = 2 * 2^2 = 2 * 4 = 8
// 2^2 = 2 * 2^1 = 2 * 2 = 4
// 2^1 = 2 * 2^0 = 2 * 1 = 2
// 2^0 = 1




























// // computes base^power
// // (assumes power >= 0)
fun kthPowerOf(base: Int, power: Int): Int {
    return when (power == 0) {
        true -> 1
        false -> base * kthPowerOf(base, power-1)
    }
}

println(kthPowerOf(2, 0)) // should be 1
println(kthPowerOf(2, 1)) // should be 2
println(kthPowerOf(2, 4)) // should be 16
println(kthPowerOf(5, 2)) // should be 25

// questions...
// 1. will it always terminate?
// 2. is it correct?
// 3. how efficient is it?