In JavaScript recursion is a function that calls itself. It creates a loop and with every loop you need a break or end from it. For recursions this is called “base case”. Another essential part of a recursion function is to give it a different input each time it loops. For the following example we are going to go over a simplified coding challenge.
If given 5 digits. How many different numbers can be made? In other words how many permutations. (Now I am going to simplify, not going to go over edge cases or anything)
Input: [1,2,3,4,5] Output: 120
We basically want to know how many different ways the list of numbers can be ordered.
For example: For 3 digits it would be the following.
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]Now maybe by now if you are a good at math you know of a simple way to solve this. Called factorial. The factorial of 3 would equal 6. (I personally learned this while digging deep into recursions)
3! = 6
AKA
3 * 2 * 1 = 6
Now we are going to solve it with code.
1.totalPermutations = (inputArr) => {
2. let result = []
3. permute = (arr, a = []) => {
4. if (arr.length === 0) {
5. return result.push(a)
6. } else {
7. for (let i = 0; i < arr.length; i++) {
8. let curr = arr.slice();
9. let next = curr.splice(i, 1);
10. permute(curr.slice(), a.concat(next))
11. }
12. }
13. }
14. permute(inputArr)
15. return result.length
16.}Here we have one way to write a recursion. This one is with a helper method.
Line 2: We set our empty array (who at the end will hold all the permutations)
Line 3: We are declaring our helper method function. This is taking in the array, and setting a default value of an empty array as arguments.
Line 4–5: This is our base case. This is what will stop the loop. If the array is empty then return the result.
Line 6–10: If the array is not empty then we want to iterate over it.
— Line 8: Here we are returning a new array object with .slice(). Since we are
not passing in any arguments then () acts like (0).
— Line 9: Here we are splicing the new array object. .splice(i, 1) i = index and
1= how many numbers to be removed. .splice() will return the removed item.
— Line 10: We are going to invoke the helper method that was declared before. This is where we are going to pass in a new array object of the array. and going to merge the two arrays by using a.concat(next). a = [] next =[removed number]
Line 14: Invoke the permute method passing it in the inputArray
Line 15: We finally return the result.length giving us the total number of permutations. (If we wanted a list of all the permutations then we can remove .length and see the results inside a nested array.
As you can see from above out Recursion had the base case and it would also call it self with a different input each time. I hope this walk through was a little helpful to help you tackle your next recursion coding challenge specially for a permutation.
