## DEV Community # 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"
“recursion,” Merriam-Webster.com Dictionary, Accessed 6/22/2020.

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?