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)
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))
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.
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.
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
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.
I remember spending 8 hours writing a difficult recursive program in LISP back in college as part of an AI class. In the end it only took 8 lines to solve the problem, so it no doubt counts as the lowest lines/hour of any program I ever wrote. I remember all of this, but I no longer can recall what the program did :-)
Now that you mention it I believe I did a recursive thing in my AI class as well.
I also can't remember what it did, lol.
Although now that I think about it I remember I made a
I'm betting it was the ant colony that had weird recursion stuff.
What a coincidence! The practical part of the AI course I took at the university was also focused on LISP. :)
I remember doing something recursively too, but I have no idea what it was or how many lines of code it had, lol. I remember liking LISP at the time. It was completely different from all other programming languages I had learned before. Too many parentheses though. :)
I’ve got friends who are into coding and I heard that it is really difficult
Is that true?
Looks fairly difficult after reading this post.
Writing code is easy but making something that's actually useful is quite hard.
It can take dozens of professional developers years to finish a product depending on scope.
Creating a robust modular product that isn't going to break when things change is even harder.
Perhaps the hardest thing any programmer can do is to make a "program" easy to use. It's why so much time is devoted to error checking and idiot proofing. It's also why UI design is deceptively easy yet maddeningly difficult.
When I was learning C in college (but before I had learned C++), I was introduced to recursion by needing to solve the Towers of Hanoi problem: Move 4 rings from Tower A to Tower C one at a timewhile top ring stays smaller than rings under it. Without recursion, you would end up wanting to celebrate your birthday with Justin Sun.
One practical problem to solve using recursion is to find all the ways to pay for 1st class postage using 4 stamps. This is easier to bisualize conceptually, and recursion makes more sense here
Eventually the light bulb turns on regarding recursion. Once that happens, you'll want to go back to your older code and see where you can replace older code with recursive code.
Writing code is the easy part - anyone can learn to write code. Debugging it, making it work together with existing code, etc - all the other parts of being a programmer... that's the hard stuff (And the reason I don't fear AI taking my job).
I remember the most common error I got when using recursion the wrong way was "Stack overflow". That either happened because the code was conceptually wrong and didn't have a good condition to terminate the recursive loop or that it needed to go so deep that the stack really reached its limit, in which case, there were three solutions: increase the stack limit, reduce the amount of information saved in the stack (for example, the number of the parameters of the recursive function or the memory they need), and third, and more likely, rewrite the code iteratively.
😀
Good
Just like when we used to study things were much more difficult and now with artificial intelligence technology things have become much easier helping the student a lot.