Intro to Recursion

As a boot camp graduate looking for my first programming job, I have been spending a lot of time self-teaching CS concepts that come up in coding interviews. The term recursion continuously came up while I was researching how to prepare for technical interviews. A quick lookup of the word online defines recursion as:

"a computer programming technique involving the use of a procedure, subroutine, function, or algorithm that calls itself one or more times until a specified condition is met at which time the rest of each repetition is processed from the last one called to the first"

Despite having been an English major, reading this definition left me still confused. From the definition, I know that a recursive algorithm calls itself until a given condition is met. However, I still couldn't visualize what a recursive solution would actually look like. So I decided the best way for me to learn a new programming term is to code. I looked up what problems are best solved through recursion and found one dealing with strings.

The problem

Print out all permutations of a given string.

In order to start thinking of an algorithm solution, I mapped out the solution manually.

I found what I was doing taking a given letter and tacking on different options until all options were exhausted. In this case, I take the word train and pin the letter t to the beginning and focus on rearranging "rain". In order to do so, I pin 'r' in place. Then 'a'. Then 'i'. Finally 'n'. Once I've exhausted all options, I backtrack to 'r' and choose 'i' first instead of 'a' this time. I continue to repeat this backtracking process until all possibilities beginning with the letter 't' are exhausted moving on to 'rtain'.

Turning the manual solution into an algorithm

In order to automate this process, I used my explanation of the manual process to work it into variables and functions. Here is my code as I began working through the problem:

function permutate(string){
    // I'm thinking I'm going to need to iterate over my characters and pin them to the beginning of a string
    for (let i = 0; i < string.length; i++) {
        // pin at beginning string[i]
        let prefix = string.charAt(i)

        let suffix = string.substring(0, i) + string.substring(i + 1, string.length)
        // now I need to find all permutations of the suffix and print them with the prefix tacked on
        for (let i = 0; i < suffix.length; i++) {
            // pin on a new character to prefix and then continue finding permutations of the suffix until it is empty and the prefix contains 5 characters
        }
    }
}

I realized I wanted to separate out the beginning of the word from the end which is why I used the terms prefix and suffix. The prefix holds the letters chosen while the suffix holds the remaining possibilities. Looking back at my diagram, it was clear that the process I was performing manually had a lot of repetition. I used the same logic to rearrange letters at each step of my pyramid. I continually tacked on a new character until none were left, then backtracked to when a new possibility existed.

With that logic in mind, I thought about how I could generalize a function so that I could reuse it to continuously tack on options until none remain. One the suffix is empty, the prefix should contain 5 characters which will be one of the permutations. Then, I would need to backtrack to the last time there was more than one option.

// to start, I would need an empty 'prefix'
let prefix = ""
let suffix = "train"

// I'll also begin storing my results in an array
let results = []

// As I use my function, I expect each call to add one character to the prefix while removing that character from the suffix
permutate("", "train", [])
//=>
prefix = "t"
suffix = "rain"
results = []

permutate("t", "rain", [])
//=>
prefix = "tr"
suffix = "ain"
results = []

permutate("tr", "ain", [])
//=>
prefix = "tra"
suffix = "in"
results = []

permutate("tra", "in", [])
//=>
prefix = "trai"
suffix = "n"
results = []

permutate("trai", "n", [])
//=>
prefix = "train"
suffix = ""
results = ["train"]

// then I would need to backtrack

permutate("tra", "in", ["train"])
//=>
prefix = "tran"
suffix = "i"
results = ["train"]

permutate("tran", "i", ["train"])
//=>
prefix = "trani"
suffix = ""
results = ["train", "trani"]

// and so on...

In order to implement this recursive function, I'm using a results array that I can continuously pass to the function as well as the prefix and suffix parameters. The first item my recursive function will need to check is whether a permutation has been found or not - i.e. whether the suffix no longer contains any characters.

function recursivelyPermutate(prefix, suffix, results){
    if (suffix.length === 0) {
        results.push(prefix)
    }
}

If the suffix still contains characters, I want to iterate over those characters tack each one onto the prefix while removing it from the suffix.

function recursivelyPermutate(prefix, suffix, results){
    if (suffix.length === 0) {
        results.push(prefix)
    } else {
        for (let i = 0; i < suffix.length; i++){
            prefix = prefix + suffix.charAt(i)
            suffix = suffix.slice(0, i) + suffix.slice(i + 1, suffix.length)
        }
    }
}

Now that the prefix and suffix have changed to include each option in the suffix, I can call recursivelyPermutate again with the updated substrings. The function will automatically stop calling once all options have been used thanks to the conditional.

function recursivelyPermutate(prefix, suffix, results){
    if (suffix.length === 0) {
        results.push(prefix)
    } else {
        for (let i = 0; i < suffix.length; i++){
            recursivelyPermutate(prefix + suffix.charAt(i), suffix.slice(0, i) + suffix.slice(i + 1, suffix.length), results)
        }
    }
}

Now I have a function that accepts three parameters and changes the results array passed in to store all the possible permutations. However, what I really want is to be able to call permutate("train") and have all the permutations printed to the console. To do so, I just need to add one more function that calls the recursive function the first time.

function recursivelyPermutate(prefix, suffix, results){
    if (suffix.length === 0) {
        results.push(prefix)
    } else {
        for (let i = 0; i < suffix.length; i++){
            recursivelyPermutate(prefix + suffix.charAt(i), suffix.slice(0, i) + suffix.slice(i + 1, suffix.length), results)
        }
    }
}

function permutate(string){
    results = []
    recursivelyPermutate("", string, results)
    results.forEach(permutation => {
        console.log(permutation)
      })
}

Finally, since I don't really need access to the recursive function outside of the scope of my permutate function, I'm going to place that function inside my permutate function. That way I don't have to pass the results in as a parameter since the variable will be within scope.

function permutate(string){
    results = []

    function recursivelyPermutate(prefix, suffix){
        if (suffix.length === 0) {
            results.push(prefix)
        } else {
            for (let i = 0; i < suffix.length; i++){
                recursivelyPermutate(prefix + suffix.charAt(i), suffix.slice(0, i) + suffix.slice(i + 1, suffix.length))
            }
        }
    }

    recursivelyPermutate("", string)
    results.forEach(permutation => {
        console.log(permutation)
    })
}

permutate('train')

And at last, I have finally written my first recursive solution to a problem.

Discuss

I hope this helped begin to explain what a recursive solution is, what it looks like, and how to approach a code challenge that could make use of recursion.

In the comments below, I'd love to know:

1. Have you used recursion in a project or interview? If yes, how so?
2. What do you like/dislike about recursion?
3. What methods for solving code challenges do you enjoy the most?