Advanced Recursion Techniques

Welcome to this most intriguing, yet somewhat confusing, approach in the world of algorithms — recursion. Today, we will be diving deep into advanced recursion techniques. These techniques will not only broaden your understanding of the concept but also equip you with the ability to tackle complex problems comfortably.

Recursion, simply put, is a method where the solution to a problem depends on smaller instances of the same problem. Advanced recursion techniques allow us to solve problems involving deep tree structures and backtracking, which are quite common in algorithmic challenges and technical interviews. The time complexity of these algorithms typically depends on the branching factor and the recursion depth, often following an $O(b^d)$ pattern.

To give you a small taste of what is in store, let's take a look at a recursive function that generates all permutations of a list of numbers. The strategy here is to use a method known as backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to computational problems by incrementally building candidates and abandoning a candidate as soon as it determines that the candidate cannot possibly be completed as a valid solution.

In our example, we use a MutableList to store the numbers so that we can modify them in place. At each recursion level, we choose which number should go at position first by swapping nums[first] with each element from first to the end. We then move one level deeper into the recursion to fix the next position and finally swap the elements back to reset the state for the next iteration. Once we reach the end of the list, we create a copy of the current state of the list and add it to our results.

fun permute(nums: MutableList<Int>): List<List<Int>> {
    val result = mutableListOf<List<Int>>()

    // Define a local function for backtracking
    fun backtrack(first: Int) {
        // If we've reached the end of the list, we found a complete permutation
        if (first == nums.size) {
            result.add(nums.toList()) // Add a copy of the current list state
            return
        }

        for (i in first until nums.size) {
            // Swap numbers to explore a new permutation
            val temp = nums[first]
            nums[first] = nums[i]
            nums[i] = temp

            // Move one level deeper in the recursion, fixing the next position
            backtrack(first + 1)

            // Backtrack: Swap them back to reset the state for the next iteration
            val tempBack = nums[first]
            nums[first] = nums[i]
            nums[i] = tempBack
        }
    }

    backtrack(0)
    return result
}

fun main() {
    val numbers = mutableListOf(1, 2, 3)
    val permutations = permute(numbers)
    println(permutations) 
    // Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
}