Skip to content

Recursion

Nazmul Idris edited this page Jul 6, 2018 · 13 revisions

Induction

Let's use an example to illustrate induction. Let's say that you have a bunch of coins of fixed denominations. And you're tasked with figuring out the fewest coins that you would need to put together in order to arrive at some total amount. Let's say you have denominations of 1, 5, 7, 11 and you're asked to see how few coins you can select in order to get a total of 49.

Brute force approach

Using the brute force approach you could simply see how many 11 denomination coins would get you close to the total. There would be a remainder (4 x 11 denomination coins = 44). Then you could see how many 7 denomination coins fit. And so on with 5 and 1 denomination coins. You could write this up in the following code.

/**
 * Brute force version of the recursive function [numCoins] above.
 *
 * - As you can see, there's a lot more code and complexity to compensate
 *   for very simplistic logic.
 * - The coin denominations are hard coded to be 1, 5, 7, 11.
 */
fun numCoins_nonrecursive(total: Int, coins: Coins) {
    // Exit condition
    if (total == 0) return

    var currencyRemoved = 0

    // Remove all the 11 coins
    val numberOf11s = (total / 11)
    if (numberOf11s > 0) {
        coins.numberOf11s += numberOf11s
        currencyRemoved += numberOf11s * 11
    }

    // Remove all the 7 coins
    val numberOf7s = (total - currencyRemoved) / 7
    if (numberOf7s > 0) {
        coins.numberOf7s += numberOf7s
        currencyRemoved += numberOf7s * 7
    }

    // Remove all the 5 coins
    val numberOf5s = (total - currencyRemoved) / 5
    if (numberOf5s > 0) {
        coins.numberOf5s += numberOf5s
        currencyRemoved += numberOf5s * 5
    }

    // Remove all the 1 coins
    val numberOf1s = (total - currencyRemoved) / 1
    if (numberOf1s > 0) {
        coins.numberOf1s += numberOf1s
        currencyRemoved += numberOf1s * 1
    }

}

data class Coins(var numberOf1s: Int = 0,
                 var numberOf5s: Int = 0,
                 var numberOf7s: Int = 0,
                 var numberOf11s: Int = 0) {
    override fun toString() = StringBuilder().apply {
        val result = mutableListOf<String>()
        arrayOf(::numberOf1s, ::numberOf5s, ::numberOf7s, ::numberOf11s)
            .forEach {
                if (it.get() > 0)
                    result.add("#${it.name} coins = ${it.get()}")
            }
        append(result.joinToString(", ", "{", "}").brightBlue())
    }.toString()
}

Recursion and breaking down the problem

The brute force approach produced a lot of code. And the denominations of the coins that we can use are hardcoded. This isn't a good solution. Instead if we use induction and implement it with recursion, then we can do the following.

  1. Come up with the simplest case that we can solve for (that will not require recursion).
  2. Figure out a way to call the function that you're writing w/ arguments that represent a smaller subset of the problem and use the return value from the function to assemble the final result (whatever that may be).
    • This usually entails performing some logic and then generating new arguments for the same function, that break the problem down into smaller problems.
    • Calls need to be made to the function (recursively) and the result from these calls need to be combined into a final result somehow.

Using this approach this is what the code might look like for the minimum number of coins problem.

/**
 * Use the process of induction to figure the min number of coins it
 * takes to come up with the given [total]. The coin denominations
 * you can used are in [denominations].
 */
fun numCoins(total: Int,
             denominations: List<Int>,
             coinsUsedMap: MutableMap<Int, Int>): Int {
    // Show the function call stack
    println("\tnumCoins($total, $denominations)".brightYellow())

    // Stop recursing when these simple exit conditions are met
    if (total == 0) return 0
    if (denominations.isEmpty()) return 0

    // Breakdown the problem further
    val coinDenomination = denominations[0]
    var coinsUsed = total / coinDenomination

    // Remember how many coins of which denomination are used
    if (coinsUsed > 0) {
        coinsUsedMap[coinsUsed] = coinsUsedMap[coinsUsed] ?: 0
        coinsUsedMap[coinsUsed] = coinsUsedMap[coinsUsed]!! + 1
    }

    // Breakdown the problem into smaller chunk using recursion
    return coinsUsed + numCoins(total = total - coinsUsed * coinDenomination,
                                denominations = denominations.subList(1, denominations.size),
                                coinsUsedMap = coinsUsedMap)
}
Clone this wiki locally