https://img.inleo.io/DQmZYBGPwLsDo75baseRqbhKfuCAmzCN8eBmNx9R5VYrpww/recursion-programming-meme.jpg
When you look into the void: the void looks back.
Recursion is a programming principal that is loved and hated by many, often at the same time. It's one of my favorite topics because it's just about the best example for a few lines of code being mind-numbingly complex and borderline nonsensical.
In this particular case the JavaScript game I'm playing, HackMUD, has a T2 lock called "magnara". Magnara is an anagram for... anagram. If you rearrange the letters of "magnara" it can spell "anagram". This is one of the game's easiest locks to solve by hand because the word that needs to descrambled is only 4 letters. However, doing this programmatically using brute force is a little more complicated, which is what I intend to do.
https://linangdata.com/javascript-tester/
Realizing that this problem was an excellent candidate for recursion I got to work. The goal was to make a recursive function that scrambles a four-letter word into all possible combinations.
It did not go well!
let words = []
function scramble(word){ for (let letter of word){ let w = letter + scramble(word.replace(letter, '')) if(w.length === 4){ words.push(w) } } return word }
scramble('abcd')
console.log(words)
https://img.inleo.io/DQmZUeFvT9QUaZsNz7WyZ9Wh48uZ5CH5PNHHXvmXi4LvH49/image.png
My attempt at accomplishing this goal was a bit of a disaster. I spent hours trying to remember how this all works, and even getting a result without errors was an accomplishment. Unfortunately I was only able to get four of the 4! combinations (4x3x2x1 = 24).
The rundown of what's going on here.
A recursive function is a function that calls itself. We can see that my function's name is scramble() and this function is taking a letter from the word and then adding scramble() to it to create a new word. It's an extremely confusing thing that's quite difficult to explain, but I'll give it a whirl.
The way a recursive function prevents itself from going into an infinite loop is that it creates a base-case condition that will return a value when it reaches a dead end. In this case the dead end happens when the string word no longer has any letters left. Why does it have no letters left? Because the word.replace(letter, '') function deletes a letter if I've already used it. So every time the function gets called again it gets called with one less letter until there are no letters left.
Recursion can be quite inefficient.
Recursion is good for certain tasks up to a point and then it fails. This is because it can be a very expensive operation in which hundreds or even thousands of function calls are sitting in memory waiting to unwind once they find the dead-end base case. If the recursive function calls itself too many times before resolving it will completely fill up all the RAM that it's allowed to fill and then the program will crash.
Recursion is a stack.
A stack is a special kind of class that is used often in programming. It's even employed in games like Magic the Gathering. The rules of a stack are pretty simple: first in last out. If we push() ten items onto a stack then they resolve in the opposite order.
This is the same idea for a deck of playing cards. If you count out 10 cards (one at a time) and put them in a stack in front of you... when you start drawing from the top of the deck the one that you just put down will be resolved first. Items that get pushed first to the bottom of the stack get buried until the ones above them get resolved.
The reason why recursion is so confusing is that it works the same way, so we have to think a bit backwards to make sense of it. The first function call does nothing and gets put on the literal bottom of the stack and will resolve last. Only when those function calls start hitting dead ends and returning raw values does the magic happen as the stack unwinds.
let number = 4 function factorial(number){ if(number == 1) return 1 return number * factorial(number-1) } console.log(factorial(number))
https://img.inleo.io/DQmXzbMYyZiZftuxsW6LQqJu5NoZdRZbPaKJagjkSzunMk5/image.png
Simplifying my code to create an easier to understand example.
So this would be one of the most basic recursive examples possible. Instead of using a regular loop to calculate a factorial it uses recursion. This is not a good example to demonstrate the power/advantage of recursion, but rather only to show how it works.
The factorial of 4! == 4 * 3 * 2 * 1. This recursive function returns itself multiplied by a new function call minus one.
So all four functions get called at once before anything resolves. The program wants to return 4 * factorial(number-1), but it doesn't know what factorial(number-1) is so it has to figure it out by calling factorial(3). But then factorial(3) returns 3 * factorial(2), and the program doesn't know what factorial(2) is so it calls that. Then factorial(1) gets called and it finally hits a dead end.
So now we have four functions open on the stack and only one of them is known so far. factorial(1) returned 1 instead of another recursive call. Where did factorial(1) return? Back to factorial(2). Now the program knows that factorial(2) = 2 * 1. This function can resolve and return it's value back into factorial(3) which is 3 * 2. This can now return to factorial(4) which is 4 * 6... and thus the program finally manages to return the correct answer 24 after stacking and resolving four separate function calls in tandem on the stack. Only when it got to factorial(1) did it start figuring out the actual answer.
This is the SIMPLEST possible example.
And if you're thinking, "Hm, that's pretty not-simple," you would be right. This is why recursion is so hard to grasp and even harder to implement correctly. However when a programmer finally realizes how it's done and what problems it's good for it can turn 50 lines of code into 3 and turn some really complex problems into trivially easy ones to solve. Essentially recursion should be used when the problem at hand can be broken down into smaller and smaller repeatable chunks that are easier to achieve than the normal iterative loop solution.
https://img.inleo.io/DQmVuRLjmaCYc5EcWCXy7BsH5vyztm2XqsG7dNpZZ1LA5bs/image.png
A great example of when recursion is almost necessary is calculating distance on a 2D or 3D grid. Take the picture above for example. This is how water flows in Minecraft. This is a very trivial calculation to make with recursion, but it would be a complete pain in the ass with normal loops; just an absolute nightmare.
In fact recursion in this case is not only simpler to understand but also more efficient. All we have to do is is check() the block above/below/left/right and then recursively call that check() function over and over again until we reach the limit for how far water can flow (which is 7 blocks on flat terrain).
And most importantly: if we've already checked a block there's no reason to check it again. This is something that recursive functions do quite well that iterative solutions can struggle with. Thus an iterative solution might technically work but it also might be checking the same block 50 times. Inefficiency like that could lag the game or even make it unplayable as the code scaled up.
Also notice how there are walls in the way blocking the flow of water. The recursive method doesn't care about this at all. On the other hand it could completely mess up an iterative solution. We can see that the edge of the water is always 7 blocks away from the source no matter what. That's the power of recursion at work, and it gets even more interesting when the process resets and the water is flowing downhill. The rules for water-flow and other distance calculations in Minecraft are very specific and they would be complex, buggy, and inefficient without the use of recursion.
https://img.inleo.io/DQmP5YurPhemG5XHBKwMDXk1GBncGsf9DfsgGFiS25f7yTS/image.png
words = []
function shuffle(prefix, word) { let n = word.length if (n === 0) words.push(prefix) else for (let i = 0; i < n; i++) shuffle( prefix + word[i], word.slice(0,i) + word.slice(i+1,n) ) }
shuffle("", "stop") words
https://img.inleo.io/DQmX1ySut75zHFqP4ki9q4Kj2gUXWf6JTKz3KrtLupNikm6/image.png
Circling back to the anagram problem
It was taking too long to figure it out myself and there were a couple of posts online about college kids being stuck for days trying to come up with a solution so I cheated and copied someone else's code. It worked... but I mean... how did it work? lol
Well I still don't 100% understand this solution but I'll get there. What this function did remind me of is that many recursive functions require two different input variables. In this case the variable prefix is the string that has already been set-in-stone and is guaranteed to be returned, while word gets sliced down one letter and added to the prefix, until prefix is the entire word and word is an empty string. Let's see if I can rewrite it without breaking anything.
HMMMM NOPE
I tried to change
for (let i = 0; i < n; i++) >> for (let i in word)
and completely broke it.
No idea why either seeing as n is the length of word.
Oh well at a certain point it's not worth it.
Conclusion
Recursion is a confusing but powerful concept in programming. It's a tool that doesn't need to be used very often but when it does it can create very impressive and elegant solutions that play nice in an environment of modular and scalable code. As is the case with most things technical, the easiest way to understand it is to understand it. The learning curve is high but climbing over that wall can be a satisfying experience.
Return from Recursion Strikes Again! to edicted's Web3 Blog
