Intro to Recursion
Tags: interview, codinginterviews, technicalinterviews, whiteboarding
Published: 2020-06-22 22:45:33

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:

<blockquote>"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"</blockquote><cite><a href="https://www.merriam-webster.com/dictionary/recursion">“recursion,” Merriam-Webster.com Dictionary, Accessed 6/22/2020.</a></cite>

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.

<h2>The problem</h2>

<p><b><em>Print out all permutations of a given string.</em></b></p>

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

![whiteboarding out the process of finding all permuations](https://dev-to-uploads.s3.amazonaws.com/i/ymkstv8jj8ezrf4p1918.jpeg)

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'.

<h2>Turning the manual solution into an algorithm</h2>

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:

```javascript
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.

```javascript
// 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.

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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.

<h2>Discuss</h2>

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.

<b>In the comments below, I'd love to know:</b>
<ol>
  <li>Have you used recursion in a project or interview? If yes, how so?</li>
  <li>What do you like/dislike about recursion?</li>
  <li>What methods for solving code challenges do you enjoy the most?</li>
</ol>