Recursion

• Induction
• Brute force approach
• Recursion and breaking down the problem
• Other examples of using recursion
  • Quick Sort
  • Binary Search

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]; this list must be sorted
 * already (in descending order), eg: [11, 7, 5, 1].
 */
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)
}

Other examples of using recursion

Quick Sort

You can apply the steps above (simplest case, perform logic, split arguments into smaller subset of the problem) to many other examples, such as quick sort.

/** O(n * log(n)) */
fun quick_sort(list: MutableList<Int>,
               startIndex: Int = 0,
               endIndex: Int = list.size - 1) {
    if (startIndex < endIndex) {
        // Perform some logic to break down the problem
        val pivotIndex = partition(list, startIndex, endIndex)
        
        // Recurse before pivot index
        quick_sort(list, startIndex, pivotIndex - 1) 
        
        // Recurse after pivot index
        quick_sort(list, pivotIndex + 1, endIndex) 
    }
}

/**
 * This function takes last element as pivot, places the pivot
 * element at its correct position in sorted list, and places
 * all smaller (smaller than pivot) to left of pivot and all greater
 * elements to right of pivot 
 */
fun partition(list: MutableList<Int>,
              startIndex: Int = 0,
              endIndex: Int = list.size - 1): Int {
    // Element to be placed at the correct position in the list
    val pivotValue = list[endIndex]

    // Index of smaller element
    var smallerElementIndex = startIndex

    // Make a single pass through the list
    for (index in startIndex until endIndex) {
        // If current element is smaller than equal to pivotValue
        // then swap it w/ the element at smallerElementIndex
        val valueAtIndex = list[index]
        if (valueAtIndex < pivotValue) {
            list.swap(smallerElementIndex, index)
            smallerElementIndex++
        }
    }

    // Finally move the pivotValue into the right place on the list
    list.swap(smallerElementIndex, endIndex)

    // Return the index just after where the pivot value ended up
    return smallerElementIndex
}

fun MutableList<Int>.swap(index1: Int, index2: Int) {
    val tmp = this[index1] // 'this' corresponds to the list
    this[index1] = this[index2]
    this[index2] = tmp
}

Binary Search

fun binarySearch(item: String, list: List<String>): Boolean {
    // Exit conditions (base cases)
    if (list.isEmpty()) {
        return false
    }

    // Setup probe
    val size = list.size
    val probeIndex = size / 2
    val probeItem = list[probeIndex]

    // Does the probe match? If not, split and recurse
    when {
        item == probeItem -> return true
        item < probeItem -> return binarySearch(item, 
                                                list.subList(0, probeIndex), 
                                                stats)
        else -> return binarySearch(item, 
                                    list.subList(probeIndex + 1, size), 
                                    stats)
    }
}