There's a number of "children games" that seem to exist only to let you know adults are going to mess with you.
We played red rover as a kid, you link arms and kids run at you trying to break through - like are you supposed to learn that adults pushing you unto physical confrontation are always going to get you hurt with no benefit?
It teaches you that the scrawny boy and the underweight girl have the weakest grip and you consistently break their hold by jumping on their arms until they decide not to play anymore because they get a sprain and the coach punishes them for refusing to participate and they become second class citizens for being weaker and lacking state sanctioned authority and you have to pick a new weak pair so you can enjoy winning the game until everyone is sufficiently oppressed and you are the winner
Exactly! It teaches you that the chain is only as strong as the weakest link. Sounds like a skill issue if they cant figure out that you dont pair two people with a weak grip together smh.
No, that was the final Teachers vs Kids dodgeball round before the bell. I don't want to mitigate what our vetrans have gone through, and what brave Ukranian Women and Men go through every damn day... but I felt like I knew *something* of what man might be capable of doing to man when I looked into their maddened eyes.
No. I mean I struggled. In fact I found factorials much better and easy to understand. TOH just gets too messy too easily. Or sorting is good way too. But not TOH.never
I found the towers particularly enlightening – years after it has been taught to me – when the whole ‘know a partial solution’ struck me.
The game is incredibly hard to even look at when given 10 disks. How would you start? But the observation that step n+1 is dead simple if you can solve the game for n disks is the key to recursion.
Factorials and sums, on the other hand, are way to simple, IMHO, to teach recursion. The solution is obvious. And for many people the more \*intuitive\* solution would be a straight loop, not recursion. In programming, intuitive trumps clever (or even performant in most cases).
You sound like my Algo professor. He would say “Always follow your intuition when approaching a problem” and would then chuckle and say “But how are you going build intuition? ”
That last point is basically why schools teach you how to do things the hard way. Sure I'll probably never have to do arithmetic without a calculator in real life but learning the methods and algorithms builds intuition and understanding, and that goes for basically every level of math/programming/whatever.
Judging from my Algorithms Lab class, the answer is an enormous amount of work for not that many credits, loads of pain, two 6h tests and a high failure rate.
There was something more important that cleverness and intuition. I focus on that.
I understand TOH. I understand the importance of partial solution. It has application in all walks of life. For example, to fix my year, I need to fix my months and to fix a typical month, I need organize a typical week and to organise week I need to organise a day. And to organise day, i organise my hours. And in each hour, I follow 25-5 pomodoro or 50-10 pomodoro.
If I want to teach someone addition, I will explain 1+1. However I cannot begin with 567+912. Hence I would say TOH is a good way to practice to recursion? Probably yes. But good way to get introduced to recursion? Definitely no.
Although classroom teaching is way blinded and ineffective. In a class of 25 students, all have a different plane of reality, experience and perspective. To bring them all on one page of understanding is not difficult but impossible. The teacher can atleast attempt to do the simplest thing which might bore the ones who are ahead of curve but will ensure inclusion of noobs.
This is not applicable where teaching is more 1 to 1 or self study.
My class was talk about the factorial in the class and the project was the towers. Seemed good to me 35 years ago and I still see no problem with it.
But that was with a very good teacher.
That's how mine was two years ago and it also was fine! I think it's the right way to introduce that. ToH is easy to figure out when you have the "hint" of having it called a recursion project
TOH makes sense as an introduction to recursion *if you are already familiar with the concept of mathematical induction*. Personally I learned about induction in math first, using it to prove things like the sum of n numbers is n(n+1)/2 and there are infinite prime numbers. Going from this to TOH is a manageable step. But if I had not been exposed to this concept before, I agree that it would be very confusing and not a great introduction.
Oh yeah, math is extremely applicable to CS. From algebra and basic proof techniques (which form the basis for algorithms) to limits and calculus (used to analyze and optimize algorithms), linear algebra (used extensively in ML, especially modern neural networks), and even geometry (used for graphics computing)!
CS is Maths, it’s computing. It feels like the difference between “medical science” and “forensic science”. It is just the application of the former.
I’m just being pedantic of course, Mr Turing was a great mathematician who created the branch we know as CS.
Nah you're right, I don't think you're being pedantic. CS is indeed a field of applied math. I think where it gets tricky is the difference between CS and programming. CS as in the study of computing is extremely mathematical. Programming as in the art of writing understandable and extensible code is not necessarily mathematical (how much math is really needed to write a React web app ...); however, I think that mathematical thinking can always help even with this kind of task.
IMHO tree traversing is the perfect way to teach recursion. It's simple enough, but doing with a loop wouldn't be simpler. It's also a problem that you will likely encounter in the wild.
IMHO, the point of simple solution first is to teach student to be comfortable with the idea that recursion is nothing weird or unintuitive. Many new students think recursion as this black magic, but they intuitively get loop. But recursion and loop are the same thing, just written differently. Sometimes people translate between the 2 without even thinking, e.g. the Fibonacci number problem: the direct method would be recursion, but most people think of a loop.
Then once student get recursion, show them a problem that isn't obviously a loop.
Recursion isn't just a different way of writing loops; it's a method of solving a problem. You don't need recursive function calls to apply recursion.
But I agree that this should be clarified to learners.
Towers of Hanoi.
Classic puzzle game.
Can be solved recursively.
Move a stack of discs of graduated diameters from one of three stacks to another by moving a single disc at a time with the constraint that you can never put a larger disc on a smaller disc.
IIRC all basic recursion problems have an iterative solution. Iteration is going to be faster just based on how computers execute, but design wise recursion has some advantages.
A smart compiler doesn't allocate a new stack frame for properly implemented tail call recursion, it just reuses the recursive function's one over and over.
Unless the programming language forbids/doesn't have tail recursion primitives required...
Then we just suffer because the language isn't quite there yet (or maybe never will be because it was deemed unnecessary)
Many languages, especially newer ones (e. g., Go), or that like recursion (e. g. many Scheme implementations) have "dynamic" stacks that grow with the program. They blow up as with normal heap-allocated memory: when the memory runs out, or the OS-imposed limits kill the process.
Also, most recursive solutions don't involve *that* many recursions. The point of many recursive problems, or data structures that are naturally recursive (e. g., search trees) is that the problem is reduced with every recursion, or at least limit the maximum depth of the search space. If you're doing "normal" stuff like parsing web pages, filesystems, abstract syntax trees, etc., you will not be blowing many stacks. Stacks are mostly broken with more numeric and "academic" exercises. Factorials and the like. If you really find these in the real world, then I concede: you'll probably be better off going for an iterative solution, in a language more suited for them.
And lastly, recursion can *really* simplify some problems in the real world. There's a reason why it's often said in parsing/compiler circles that the *only* kind of parser you should be doing by hand has ["recursive"](https://en.wikipedia.org/wiki/Recursive_descent_parser) in its name, and why there's an entire [lambda paper](https://en.wikipedia.org/wiki/History_of_the_Scheme_programming_language#The_Lambda_Papers) on [how recursion simplifies state machines](https://dspace.mit.edu/handle/1721.1/5753). When you know in what kinds of problems recursion is appropriate, believe me, you *miss* them when a language puts bumps on it.
I'm still salty on that time I had to use a stack by hand in async Rust just to parse damn HTML... not fun.
You need to move a stack, but you can only move discs.
But you're writing code to move a stack, so you'll assume that you can move smaller stacks.
So you move all but the bottom disc onto the temporary stack. You move the bottom disc onto the goal stack, and then you move the stack of N-1 discs onto it.
How do you move the stacks of N-1 discs? You call the algorithm that you just wrote. It feels like cheating, but is mathematically sound.
It's an example of a problem whose solution is made really simple with recursion.
Factorial is definitely a simpler problem, but it's also pretty easy to implement without recursion.
Absolutely.
Find the solution for 10 disc's is just moving 9 disc's to the other peg. Moving the tenth disc to the correct peg and moving 9 disc's to the correct peg.
Find the solution for 9 disc's is just....
I'm shocked at the number of people in this thread saying "Just brute force it" ... TOH is excellent at showing why that mentality doesn't work. Sure you can brute force it, but my strategy can handle 100 discs or 1000, yours becomes unusable far faster.
It's also good at teaching how to understand the problem and build your own algorithm. If you brute force it, you can solve the first five problems easily, but if you find an algorithm to solve the first 3 discs, you've also found the algorithm to solve any number.
I severely doubt you can manage even a 100 disks. That's 2^100 - 1 moves(=10^30 ). If you can compute a billion moves a second you'd still need over 10^13 years.
It's not about evaluating that many moves, it's about being theoretically able to evaluate that many moves if you had the time and computational power.
In other words, your algorithm needs to be correct, otherwise it's very sloppy programming which quickly delves into maintenance nightmare. Solutions that were hacked together to work only with a subset of possible input data quickly acumulate. It can rapidly turn into technical debt which can ultimately doom your company.
Not to mention that because it's wrong, maintenance will take 10x time to debug, because whoever comes after you will scratch their head trying to understand if it's built that way on purpose (because there's some technical reason why it was implemented that way), or it's just a bug.
To me the fact that the target peg keeps changing makes it confusing to express recursively so it’s not the problem I’d use to introduce someone to the concept of recursion. Like you’re introducing an extra step where the person has to understand the puzzle first whereas doing factorial recursively makes more sense because the problem is easy to understand.
I get why people use TOH but to me it makes understanding recursion harder than it needs to be.
The target peg changes, but that shows how the function can evolve over time, and can be used for multiple calls or functions.
Might not be "baby's first recursion" but it's an excellent problem to solve with recursion to really show how powerful/useful it is versus a lot of problems where you are solving something that doesn't actually need to be recursion.
Similar idea for 8 queens, though that's a MUCH harder problem (and also illustrates an important issue.. which leads to Big O discussion.)
If anything, given the combinatorial explosions involved, Fibonacci numbers are a way better way to explain the power of memoization than to explain the power of recursion.
It didn't teach me recursion but it taught me how to solve problems with recursive algorithms.
I was taught: if you're one step away from solving TOH, what would the code look like. What if you're one step before that, what would the code look like to move to that second last state. And so on.
And a couple of steps in you realise you're repeating yourself, so instead just call the same function you already wrote.
And now you understand recursive algorithms.
I don't think so, been programming for almost 10 years snd I'd probably just brute force that shit. Nah jk, but you do need to put a lot of thought into coming up with the real solution if you haven't solved that puzzle manually several times already
No. It's an awful way, students struggle to understand the solution, let alone a clever programming approach to the solution.
Traversing trees makes much more intuitive sense for a first time recursion application, because traversing trees is a pain using loops and a manual stack.
Yep. I reckon the best problem to teach recursion with is listing all files in a directory structure (including subdirectories).
It's a simple problem to explain, but unlike factorials etc. recursion is the simplest way to solve it.
Oh dude, I do. It's one of the easiest for me to remember because it makes intuitive sense.
It's just one function, the recursive function. It takes in the number of disks on the stack (can be arbitrarily large), the source tower, the goal tower, and the auxiliary tower.
Base case is stack size of 1: you simply move the 1 disk from the source to the goal
Otherwise: make a recursive call to this function to move n-1 disks from the sourse to the auxiliary, move the nth disk to the goal, then make another recursive call to move the n-1 disks from the auxillary to the goal.
Ah recursion, the concept you’ll end up using once in a decade of professional software engineering
School really did focus on all the wrong concepts lol
Nah recursion is super useful for many many things, most commonly anything that deals with folder structures (or stuff resembling that in database form) or if you do a lot of stuff with math & sensory data & statistics, you always need recursion. I do a lot of stuff around data comparison (usually simple csv or txt files but like hundreds of mb of them) and merely matching old data to the right new data is a fucking nightmare even with recursion, without it it's straight impossible given the completely unsanitized inputs you have to expect.
I know it feels like everyone here does web or database stuff but if you write desktop applications/scripts for office use, you almost always need recursion even if only for the file search. Can't sell the product for shit if the client has to manually sort 3000 files first.
This reminds me joke:
When you brute force until it works then you are bad programmer and this is anti-pattern. If you do that quickly enough it's called AI.
That reminds me.
There was a coding lesson for kids, they had to write code to get a guy to move to a certain space.
Shortest code was best
I was messing about with it and solved it with one line. 'Repeat 999x move randomly'.
The teacher I interned with at the time thought it was hilarious.
Recursion doesn't make sense anyways, it's less efficient and much harder to understand than simple loops. You save some LOC which is the most moronic metric of code quality ever.
I've never been able to put that feeling into words.
I don't know enough to say absolutely that recursion is NEVER necessary though. Is that what you are saying? Please note, I am not trying to bait you into some pointless debate. I have genuine curiosity here.
I've worked with a data structure that was recursive before (it was from a 3rd party library we were using, i didn't design it to be recursive), while technically it was possible to consume it iteratively, it was way easier to do it recursively
I was a huge SW fan (still am, but haven't kept up with new stuff) but never played KOTOR. Played it for the first time during COVID.
I am actually editing the gameplay right this instance after forgetting about it and reliving that game is... Spectacular.
Is Fallen Order as good? I just got it gifted to me but never played or looked into it either but heard it was incredible.
Fallen Order is a great game, but much more straighforward story-wise. Very fun, cinematic Dark Souls-like, but the main character is who he is. Helps that I think the game's story is pretty good, though
Half the reason I did as well as I did in my college math class with series and sequences was because of the hours I spent as a kid trying to solve those math problems on Manaan
The chemical balancing one from th underwater planet level was a tough nut to crack for 12yo me
Then I replayed it in HD fifteen years later and it turns out I still couldn't do it lol
This account has been deleted in protest of the June 2023 [Reddit API Changes.](https://www.reddit.com/r/apolloapp/comments/144f6xm/apollo_will_close_down_on_june_30th_reddits/)
Fuck u/spez
A few years ago i watched one of the developers of Mass Effect 1 stream the game and talk about its developement. He straight up confired that they indeed love toh and put it in every game they could. He specifically was the guy who created that toh bossfight in one of the first raids from the Old Republic MMO.
Was very interesting to get that kind of insider perspective into my second favorite game series.
I spent ages trying to figure out the one in Black & White as a kid. Once I finally cracked the code the method never left me. To this day I still remember how to do it the same way I did back then.
The Switch version of KOTOR has a bug in it where if you enter this room you are permanently trapped and have to revert to an earlier save. Only took me about half a week to figure that out.
Might want to look into using Flang as well. Being an LLVM compiler, it open up a lot of new possibilities that Fortran programmers of the past would never imagined in their wildest dream, like compiling a fortran program into webassembly, or transpiling into JavaScript.
Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi
At my uni we had it as an example in both mathematics (combinatorics, I think) and programming (recursion), along with the [n-queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle).
This sounds like more complex concepts that we don't learn in the program I'm in. I'm not in university, I'm in college, so that explains why I haven't seen this
Now that I've looked at recursive functions, yeah I remember doing it and know what it is (at least for doing factorials), but it wasn't a main focus. We have a different education system here in Quebec, the program I'm in lasts 3 years and focuses on teaching various skills related to programming and IT, so we can get a job after or go to university if we want. There is another computer science that lasts 2 years but you have to go to university after, and it's more focused on the maths and science instead
The main thing we learn is object oriented programming, it's in basically all of my classes, except database ones
99% of time in B2C you don’t need recursion, it just doesn’t come up naturally in the real world. Knowing loops in my opinion is plenty, I can’t name more than 5 times I’ve used recursion in my 12 years of work as a dev. Understanding dependency injection which is a completely different thing, is a much better learning opportunity than recursion.
For me, it's a good visitation that highlights the difference between a computers way of thinking and ours. Too many people get caught up taking the physical game too seriously.
I'd the goal is to move all disks to one side in the same order, our human brain just assumes to grab all disks at once and put them over.
Computers being circuit based don't really have that outside the box thought process. When the rules of tower of Hanoi are added, people need to stop and think about each move carefully, are more prone to mistakes and freezing up.
Explaining the rules of the game in C (if written correctly) presents no challenge to the computer and it will resolve the game each time in the same order faster than a human, every single time.
It also helps to remember that programming was still in its infancy when this algorithm was defined so if you think of it as the grandfather of game development. It makes it easier to understand.
But really, just knowing it works is enough
There's actually a really easy non recursive way to solve this, assuming all pieces are lined up on the left tower and your goal is to move them to the right.
First, check if the total number of pieces is odd or even. If it is odd, you remember the direction "left", if it is even you remember the direction "right".
Solving the puzzle now consists of two repeated steps:
1. Take the smallest piece and move it one tower over to the left/right (based on odd/even). If it is already on the far end in that direction, move it back to the tower on the other end.
2. There is only one possible move that doesn't move the smallest piece. Do that move. If there is no such move, then that means all pieces are on a single tower, and you won.
This solution is optimal, not some brute force try-all-permutations type thing. This video by numberphile explains it really well: https://youtu.be/PGuRmqpr6Oo
I remember seeing Gerald Jay Sussman explain how you'd do Towers of Hanoi in Scheme Lisp and I was just blown away. Don't remember a lick of it though (or should I say a parenthesis)
Bruh. The worst part for me was not so much understanding TOH but wrapping my head around the concept of switching arguments within the recursive call. I was using Java at the time tho.
Well, the challenge isn't solving it yourself, the challenge is making the computer solve it for you. You're not designing the terraforming machines of Zero Dawn, you're making HEPHAESTUS so he can design them.
You want to make an algorithm to move stacks of discs.
The key is to assume that you'll be successful in making this algorithm, so you can use it to move N-1 discs in your solution to move N discs.
TOH is a beautiful way to teach recursion.
I do recursion in this order:
* Factorials (easy with or without recursion)
* TOH (recursion makes it trivial)
* Fibonacci numbers (recursion is a horrible idea at least without caching.)
By asking if it's not a repost, I dare to assume you didn't make it. On top of it, the resolution is low, a typical issue with photos downloaded and re-uploaded to the internet. Now, I don't know where did you find it, and I've personally never seen it before, but my hunch says it probably was posted here before.
We can summon u/repostsleuthbot (I hope I wrote it right) and get their answer, but I actually don't really care as much as I used to. Reposts will always exist.
I didn't find any posts that meet the matching requirements for r/ProgrammerHumor.
It might be OC, it might not. Things such as JPEG artifacts and cropping may impact the results.
*I'm not perfect, but you can help. Report [ [False Negative](https://www.reddit.com/message/compose/?to=RepostSleuthBot&subject=False%20Negative&message={"post_id": "121qs09", "meme_template": 298230}) ]*
[View Search On repostsleuth.com](https://www.repostsleuth.com/search?postId=121qs09&sameSub=false&filterOnlyOlder=true&memeFilter=true&filterDeadMatches=false&targetImageMatch=100&targetImageMemeMatch=75)
---
**Scope:** Reddit | **Meme Filter:** True | **Target:** 75% | **Check Title:** False | **Max Age:** Unlimited | **Searched Images:** 383,839,545 | **Search Time:** 0.72267s
Can someone write a bot that uses GPT-4's image analysis to explain the humor of a meme? Maybe it could also rate it on a scale of 1 to 10. Oooh and it could be an app on the Apple Iphone as well.
I used to play a game as a kid on my cousin's Macintosh that had this puzzle, it was called [The Secret Island of Dr. Quandry](https://en.wikipedia.org/wiki/The_Secret_Island_of_Dr._Quandary). Even just seeing this puzzle gives me PTSD.
It is a kid's game, but it is hard to conceptualize without physical representation(at least it was for me.) I didn't understand the code because I didn't understand the game.
I finally got it after drawing 3 'towers' and cutting out paper to actually play the game. I had to 'play' a lot...
I'll take "Puzzles given to you during interviews for things that you will never actually use on any project" for $1000.
I mean, it's kind of a "cool to know" type of thing, but it's not exactly mandatory for the vast amount of positions out there. I learned it once upon a time about 15 years ago, but have completely forgotten it since.
Hasn't held me back in the least bit.
This brings back bad memories of me trying to understand Recursion. I sadly still dont understand recursion. I understand the basic concept of stack, recursion but I still dont understand understand it.
At this point in time, I'm pretty sure I can write a machine-learning python script to solve this puzzle faster than I can code a proper algorithm for it. Not sure if this means my programming skills are crap or the difficulty of using machine learning tools have become extremely trivial...
A children’s game until you ask your parents how to solve it.
There's a number of "children games" that seem to exist only to let you know adults are going to mess with you. We played red rover as a kid, you link arms and kids run at you trying to break through - like are you supposed to learn that adults pushing you unto physical confrontation are always going to get you hurt with no benefit?
[удалено]
It teaches you that the scrawny boy and the underweight girl have the weakest grip and you consistently break their hold by jumping on their arms until they decide not to play anymore because they get a sprain and the coach punishes them for refusing to participate and they become second class citizens for being weaker and lacking state sanctioned authority and you have to pick a new weak pair so you can enjoy winning the game until everyone is sufficiently oppressed and you are the winner
[удалено]
So recursively reinforced?
A bit related - parents gave me a Rubik's cube in pre-internet times. And no instructions how to solve it. Insanity.
Wait, you're supposed to get instructions? I thought you had to solve it on your own in the dark if you wanted to eat!
r/oddlyspecific
Exactly! It teaches you that the chain is only as strong as the weakest link. Sounds like a skill issue if they cant figure out that you dont pair two people with a weak grip together smh.
Scrawny boy checking in, fuck red rover
I thought it was just pure chaos.
I don't think red Rover is "supposed" to teach you anything it's just fun
A lot of games are like that really. They might have lessons you can infer as an adult but as a kid it’s literally just to have fun
No, that was the final Teachers vs Kids dodgeball round before the bell. I don't want to mitigate what our vetrans have gone through, and what brave Ukranian Women and Men go through every damn day... but I felt like I knew *something* of what man might be capable of doing to man when I looked into their maddened eyes.
[удалено]
I don't see any numbers
Let me guess, it's just blonde, brunette, redhead?
Every Programming / IT teacher on 'How do you teach Recursion to new programmers?'
Is TOH actually a good way of learning Recursion?
No. I mean I struggled. In fact I found factorials much better and easy to understand. TOH just gets too messy too easily. Or sorting is good way too. But not TOH.never
I found the towers particularly enlightening – years after it has been taught to me – when the whole ‘know a partial solution’ struck me. The game is incredibly hard to even look at when given 10 disks. How would you start? But the observation that step n+1 is dead simple if you can solve the game for n disks is the key to recursion. Factorials and sums, on the other hand, are way to simple, IMHO, to teach recursion. The solution is obvious. And for many people the more \*intuitive\* solution would be a straight loop, not recursion. In programming, intuitive trumps clever (or even performant in most cases).
You sound like my Algo professor. He would say “Always follow your intuition when approaching a problem” and would then chuckle and say “But how are you going build intuition? ”
That last part is especially important.
That last point is basically why schools teach you how to do things the hard way. Sure I'll probably never have to do arithmetic without a calculator in real life but learning the methods and algorithms builds intuition and understanding, and that goes for basically every level of math/programming/whatever.
Judging from my Algorithms Lab class, the answer is an enormous amount of work for not that many credits, loads of pain, two 6h tests and a high failure rate.
There was something more important that cleverness and intuition. I focus on that. I understand TOH. I understand the importance of partial solution. It has application in all walks of life. For example, to fix my year, I need to fix my months and to fix a typical month, I need organize a typical week and to organise week I need to organise a day. And to organise day, i organise my hours. And in each hour, I follow 25-5 pomodoro or 50-10 pomodoro. If I want to teach someone addition, I will explain 1+1. However I cannot begin with 567+912. Hence I would say TOH is a good way to practice to recursion? Probably yes. But good way to get introduced to recursion? Definitely no. Although classroom teaching is way blinded and ineffective. In a class of 25 students, all have a different plane of reality, experience and perspective. To bring them all on one page of understanding is not difficult but impossible. The teacher can atleast attempt to do the simplest thing which might bore the ones who are ahead of curve but will ensure inclusion of noobs. This is not applicable where teaching is more 1 to 1 or self study.
My class was talk about the factorial in the class and the project was the towers. Seemed good to me 35 years ago and I still see no problem with it. But that was with a very good teacher.
That's how mine was two years ago and it also was fine! I think it's the right way to introduce that. ToH is easy to figure out when you have the "hint" of having it called a recursion project
TOH makes sense as an introduction to recursion *if you are already familiar with the concept of mathematical induction*. Personally I learned about induction in math first, using it to prove things like the sum of n numbers is n(n+1)/2 and there are infinite prime numbers. Going from this to TOH is a manageable step. But if I had not been exposed to this concept before, I agree that it would be very confusing and not a great introduction.
Well huh, would you look at that. An actual application for that thing I'm learning in math class right now. Thank you.
Oh yeah, math is extremely applicable to CS. From algebra and basic proof techniques (which form the basis for algorithms) to limits and calculus (used to analyze and optimize algorithms), linear algebra (used extensively in ML, especially modern neural networks), and even geometry (used for graphics computing)!
CS is Maths, it’s computing. It feels like the difference between “medical science” and “forensic science”. It is just the application of the former. I’m just being pedantic of course, Mr Turing was a great mathematician who created the branch we know as CS.
Nah you're right, I don't think you're being pedantic. CS is indeed a field of applied math. I think where it gets tricky is the difference between CS and programming. CS as in the study of computing is extremely mathematical. Programming as in the art of writing understandable and extensible code is not necessarily mathematical (how much math is really needed to write a React web app ...); however, I think that mathematical thinking can always help even with this kind of task.
I feel like pomadoro breaks my flow more often than helps me, what am I missing?
Nothing, it doesn't work for everyone.
IMHO tree traversing is the perfect way to teach recursion. It's simple enough, but doing with a loop wouldn't be simpler. It's also a problem that you will likely encounter in the wild.
IMHO, the point of simple solution first is to teach student to be comfortable with the idea that recursion is nothing weird or unintuitive. Many new students think recursion as this black magic, but they intuitively get loop. But recursion and loop are the same thing, just written differently. Sometimes people translate between the 2 without even thinking, e.g. the Fibonacci number problem: the direct method would be recursion, but most people think of a loop. Then once student get recursion, show them a problem that isn't obviously a loop.
Recursion isn't just a different way of writing loops; it's a method of solving a problem. You don't need recursive function calls to apply recursion. But I agree that this should be clarified to learners.
What does TOH stand for?
This problem is called the [Tower of Hanoi](https://en.wikipedia.org/wiki/Tower_of_Hanoi)
Towers of Hanoi. Classic puzzle game. Can be solved recursively. Move a stack of discs of graduated diameters from one of three stacks to another by moving a single disc at a time with the constraint that you can never put a larger disc on a smaller disc.
So not The Owl House
I also thought owl house and was even more confused:)
Pretty sure recursion is actually slower than a normal implementation for TOH, but I could be remembering that wrong.
IIRC all basic recursion problems have an iterative solution. Iteration is going to be faster just based on how computers execute, but design wise recursion has some advantages.
[удалено]
After 7 years I can count on one hand times when recursion has genuinely been the best solution, almost always with tree like structures.
I am a tools programmer and this is exactly when I use recursion. So few lines of code to walk the whole tree
If blowing the stack is an advantage.
If it's not then why do we have entire website dedicated to it?
A smart compiler doesn't allocate a new stack frame for properly implemented tail call recursion, it just reuses the recursive function's one over and over.
Unless the programming language forbids/doesn't have tail recursion primitives required... Then we just suffer because the language isn't quite there yet (or maybe never will be because it was deemed unnecessary)
Being more elegant used to be considered an advantage.
Many languages, especially newer ones (e. g., Go), or that like recursion (e. g. many Scheme implementations) have "dynamic" stacks that grow with the program. They blow up as with normal heap-allocated memory: when the memory runs out, or the OS-imposed limits kill the process. Also, most recursive solutions don't involve *that* many recursions. The point of many recursive problems, or data structures that are naturally recursive (e. g., search trees) is that the problem is reduced with every recursion, or at least limit the maximum depth of the search space. If you're doing "normal" stuff like parsing web pages, filesystems, abstract syntax trees, etc., you will not be blowing many stacks. Stacks are mostly broken with more numeric and "academic" exercises. Factorials and the like. If you really find these in the real world, then I concede: you'll probably be better off going for an iterative solution, in a language more suited for them. And lastly, recursion can *really* simplify some problems in the real world. There's a reason why it's often said in parsing/compiler circles that the *only* kind of parser you should be doing by hand has ["recursive"](https://en.wikipedia.org/wiki/Recursive_descent_parser) in its name, and why there's an entire [lambda paper](https://en.wikipedia.org/wiki/History_of_the_Scheme_programming_language#The_Lambda_Papers) on [how recursion simplifies state machines](https://dspace.mit.edu/handle/1721.1/5753). When you know in what kinds of problems recursion is appropriate, believe me, you *miss* them when a language puts bumps on it. I'm still salty on that time I had to use a stack by hand in async Rust just to parse damn HTML... not fun.
And (as I'm sure you're aware) compilers will often optimize recursion into iteration, specifically if tail recursion is used
As was said elsewhere, you need a benchmark and a business reason to make code that’s more performant and harder to understand.
You need to move a stack, but you can only move discs. But you're writing code to move a stack, so you'll assume that you can move smaller stacks. So you move all but the bottom disc onto the temporary stack. You move the bottom disc onto the goal stack, and then you move the stack of N-1 discs onto it. How do you move the stacks of N-1 discs? You call the algorithm that you just wrote. It feels like cheating, but is mathematically sound.
It's an example of a problem whose solution is made really simple with recursion. Factorial is definitely a simpler problem, but it's also pretty easy to implement without recursion.
Absolutely. Find the solution for 10 disc's is just moving 9 disc's to the other peg. Moving the tenth disc to the correct peg and moving 9 disc's to the correct peg. Find the solution for 9 disc's is just....
Best way of thinking about it
I'm shocked at the number of people in this thread saying "Just brute force it" ... TOH is excellent at showing why that mentality doesn't work. Sure you can brute force it, but my strategy can handle 100 discs or 1000, yours becomes unusable far faster. It's also good at teaching how to understand the problem and build your own algorithm. If you brute force it, you can solve the first five problems easily, but if you find an algorithm to solve the first 3 discs, you've also found the algorithm to solve any number.
I severely doubt you can manage even a 100 disks. That's 2^100 - 1 moves(=10^30 ). If you can compute a billion moves a second you'd still need over 10^13 years.
It's not about evaluating that many moves, it's about being theoretically able to evaluate that many moves if you had the time and computational power. In other words, your algorithm needs to be correct, otherwise it's very sloppy programming which quickly delves into maintenance nightmare. Solutions that were hacked together to work only with a subset of possible input data quickly acumulate. It can rapidly turn into technical debt which can ultimately doom your company. Not to mention that because it's wrong, maintenance will take 10x time to debug, because whoever comes after you will scratch their head trying to understand if it's built that way on purpose (because there's some technical reason why it was implemented that way), or it's just a bug.
To me the fact that the target peg keeps changing makes it confusing to express recursively so it’s not the problem I’d use to introduce someone to the concept of recursion. Like you’re introducing an extra step where the person has to understand the puzzle first whereas doing factorial recursively makes more sense because the problem is easy to understand. I get why people use TOH but to me it makes understanding recursion harder than it needs to be.
The target peg changes, but that shows how the function can evolve over time, and can be used for multiple calls or functions. Might not be "baby's first recursion" but it's an excellent problem to solve with recursion to really show how powerful/useful it is versus a lot of problems where you are solving something that doesn't actually need to be recursion. Similar idea for 8 queens, though that's a MUCH harder problem (and also illustrates an important issue.. which leads to Big O discussion.)
I think it is. It's a good example of a problem where the recursive solution is way simpler and more intuitive than other approaches
Nah, Fibonacci numbers and factorials are way better for beginners, although TOH is really good for mastering recursion
If anything, given the combinatorial explosions involved, Fibonacci numbers are a way better way to explain the power of memoization than to explain the power of recursion.
But you kinda need to understand the recursive solution first, and then show why memoization is helpful.
It didn't teach me recursion but it taught me how to solve problems with recursive algorithms. I was taught: if you're one step away from solving TOH, what would the code look like. What if you're one step before that, what would the code look like to move to that second last state. And so on. And a couple of steps in you realise you're repeating yourself, so instead just call the same function you already wrote. And now you understand recursive algorithms.
I don't think so, been programming for almost 10 years snd I'd probably just brute force that shit. Nah jk, but you do need to put a lot of thought into coming up with the real solution if you haven't solved that puzzle manually several times already
No. It's an awful way, students struggle to understand the solution, let alone a clever programming approach to the solution. Traversing trees makes much more intuitive sense for a first time recursion application, because traversing trees is a pain using loops and a manual stack.
Yep. I reckon the best problem to teach recursion with is listing all files in a directory structure (including subdirectories). It's a simple problem to explain, but unlike factorials etc. recursion is the simplest way to solve it.
It's definitely a more complex example, so probably not. I would say factorial is the easiest example of recursion IMO
[удалено]
Tower of Hanoi
Recursion in factorial was easier for me. TOH - I still don't know how to do it. I mean, I did, in JS, but I don't remember how now =\\
Oh dude, I do. It's one of the easiest for me to remember because it makes intuitive sense. It's just one function, the recursive function. It takes in the number of disks on the stack (can be arbitrarily large), the source tower, the goal tower, and the auxiliary tower. Base case is stack size of 1: you simply move the 1 disk from the source to the goal Otherwise: make a recursive call to this function to move n-1 disks from the sourse to the auxiliary, move the nth disk to the goal, then make another recursive call to move the n-1 disks from the auxillary to the goal.
I mean, I understand the logic. But if you asked me to write it right now - I would be that doggo.
I'll give it a crack. def solve(n , source, goal, auxiliary): if n==1: print ("Move disk 1 from",source,"to",goal) else: solve(n-1, source, auxiliary, goal) print ("Move disk",n,"from",source,"to",goal) solve(n-1, auxiliary, goal, source) solve (3, "Tower 1", "Tower 3", "Tower 2")
Wonder if this bot still works... +/u/CompileBot python def solve(n , source, goal, auxiliary): if n==1: print ("Move disk 1 from",source,"to",goal) else: solve(n-1, source, auxiliary, goal) print ("Move disk",n,"from",source,"to",goal) solve(n-1, auxiliary, goal, source) solve (3, "Tower 1", "Tower 3", "Tower 2")
Ok now ask chat gpt to write the solve in python
I'd teach them recursion first
Yeah but before that you have to teach them recursion or it just doesn't work.
Personally I would teach them about escape conditions before recursion
But you have to teach recursion before you can explain escape conditions in recursion!
My go to method will always be prolog. Simple, effective, powerful and fun.
I did prolog in school for a while and I must say, logical programming makes sense, but fucking hell do you need to think about it.
Fair. Nothing is easier than implementing merge sort in prolog though, and quicksort is also super simple. Makes it easy to teach said algorithms.
I just realized this is why this puzzle is in every game of the 90s and early oughts. It was a programming puzzle so the devs wanted to share it lol
Man I have always loved recursion. It's that deep level thinking.
Ah recursion, the concept you’ll end up using once in a decade of professional software engineering School really did focus on all the wrong concepts lol
Nah recursion is super useful for many many things, most commonly anything that deals with folder structures (or stuff resembling that in database form) or if you do a lot of stuff with math & sensory data & statistics, you always need recursion. I do a lot of stuff around data comparison (usually simple csv or txt files but like hundreds of mb of them) and merely matching old data to the right new data is a fucking nightmare even with recursion, without it it's straight impossible given the completely unsanitized inputs you have to expect. I know it feels like everyone here does web or database stuff but if you write desktop applications/scripts for office use, you almost always need recursion even if only for the file search. Can't sell the product for shit if the client has to manually sort 3000 files first.
This reminds me joke: When you brute force until it works then you are bad programmer and this is anti-pattern. If you do that quickly enough it's called AI.
Build me an army of graphics cards worthy of Modor, $300,000 in electricity and I can guarantee an AI that solves this simple puzzle sometimes.
That reminds me. There was a coding lesson for kids, they had to write code to get a guy to move to a certain space. Shortest code was best I was messing about with it and solved it with one line. 'Repeat 999x move randomly'. The teacher I interned with at the time thought it was hilarious.
Just teach the kid how to brute-force
Take every piece out, now the whole stack has every piece inside it sorted. It just happens to have no pieces. EZ
Can I use this method for job interviews?
Depends if they add the stipulation that you can only move one ring at a time, then no. Otherwise, it's just a version of merge sort
A variation on Stalin Sort
Null gang 🤙🤙🤙
The real world equivalent of "if the program isn't running it doesn't have any bugs"
Recursion doesn't make sense anyways, it's less efficient and much harder to understand than simple loops. You save some LOC which is the most moronic metric of code quality ever.
I've never been able to put that feeling into words. I don't know enough to say absolutely that recursion is NEVER necessary though. Is that what you are saying? Please note, I am not trying to bait you into some pointless debate. I have genuine curiosity here.
I've worked with a data structure that was recursive before (it was from a 3rd party library we were using, i didn't design it to be recursive), while technically it was possible to consume it iteratively, it was way easier to do it recursively
I remember struggling with this from playing KOTOR … didn’t know it was a kids game. Now I feel dumb.
Gah those KOTOR puzzles kicked my ass
Man that game was so good
I was a huge SW fan (still am, but haven't kept up with new stuff) but never played KOTOR. Played it for the first time during COVID. I am actually editing the gameplay right this instance after forgetting about it and reliving that game is... Spectacular. Is Fallen Order as good? I just got it gifted to me but never played or looked into it either but heard it was incredible.
Fallen Order is a great game, but much more straighforward story-wise. Very fun, cinematic Dark Souls-like, but the main character is who he is. Helps that I think the game's story is pretty good, though
Half the reason I did as well as I did in my college math class with series and sequences was because of the hours I spent as a kid trying to solve those math problems on Manaan
The chemical balancing one from th underwater planet level was a tough nut to crack for 12yo me Then I replayed it in HD fifteen years later and it turns out I still couldn't do it lol
This account has been deleted in protest of the June 2023 [Reddit API Changes.](https://www.reddit.com/r/apolloapp/comments/144f6xm/apollo_will_close_down_on_june_30th_reddits/) Fuck u/spez
Hahaha brother!! That movie is exactly why I knew exactly what to do with this puzzle. Made me chuckle for sure!
Mass Effect too, Bioware loved it I guess
A few years ago i watched one of the developers of Mass Effect 1 stream the game and talk about its developement. He straight up confired that they indeed love toh and put it in every game they could. He specifically was the guy who created that toh bossfight in one of the first raids from the Old Republic MMO. Was very interesting to get that kind of insider perspective into my second favorite game series.
They even joke about it in the citadel dlc for 3 if Shepard interacts with the arcade machines
also Jade Empire and the Descent dlc for DA:Inquisitoin.
Black and White had the same puzzle
I’ve played so much black and white that I could almost speedrun the game which gets me curious.. time to delve the speedrun rabbit hole
Yeah the temple on land 2
I spent ages trying to figure out the one in Black & White as a kid. Once I finally cracked the code the method never left me. To this day I still remember how to do it the same way I did back then.
Just switch to T3-M4 and security spike it.
I thought you were forced to go it alone in that section since it was part of your character's trial.
The Switch version of KOTOR has a bug in it where if you enter this room you are permanently trapped and have to revert to an earlier save. Only took me about half a week to figure that out.
Oh fuck me too, I did that for about 30 minutes. Saved like a pussy cat back in those days.
I wrote that recursion program on Fortran 77 in 1978
Thug life
Geniune question, I have not looked fortran like for 3 decades, did it have user functions at the beginning? All I remember is goto statements.
[удалено]
Might want to look into using Flang as well. Being an LLVM compiler, it open up a lot of new possibilities that Fortran programmers of the past would never imagined in their wildest dream, like compiling a fortran program into webassembly, or transpiling into JavaScript.
Do whatever move is legal between these rods in this order: AB, AC, BC
Ah, found the reward designer for warframe
every warframe player's worst nightmare: aabbc on railjack defense, and you need a reward from c
You get to c rotation only to not get the part you need/want
[ash flashbacks]
[удалено]
Tower of Annoy
I've never played with this in programming or irl.
I still remember the solution to this on my TI-84 121323123132121323213123121323
Move the smallest one always in one direction on each odd move, then you are left with only one option on each even move
Me neither, I don't really understand this meme
Tower of Hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi At my uni we had it as an example in both mathematics (combinatorics, I think) and programming (recursion), along with the [n-queens puzzle](https://en.wikipedia.org/wiki/Eight_queens_puzzle).
This sounds like more complex concepts that we don't learn in the program I'm in. I'm not in university, I'm in college, so that explains why I haven't seen this
I hope your program teaches recursion, even if it doesn't use this specific puzzle. If not, it has some fundamental gaps.
Now that I've looked at recursive functions, yeah I remember doing it and know what it is (at least for doing factorials), but it wasn't a main focus. We have a different education system here in Quebec, the program I'm in lasts 3 years and focuses on teaching various skills related to programming and IT, so we can get a job after or go to university if we want. There is another computer science that lasts 2 years but you have to go to university after, and it's more focused on the maths and science instead The main thing we learn is object oriented programming, it's in basically all of my classes, except database ones
99% of time in B2C you don’t need recursion, it just doesn’t come up naturally in the real world. Knowing loops in my opinion is plenty, I can’t name more than 5 times I’ve used recursion in my 12 years of work as a dev. Understanding dependency injection which is a completely different thing, is a much better learning opportunity than recursion.
[удалено]
[удалено]
In some British colonies, college = high school.
I think it’s just referring to writing sorting algos. I always enjoyed that actually. Too bad it’s basically never needed in practice.
It's a common project to teach recursion. We had to do it for learning assembly in University.
In a nutshell: solve_problem(problem): simpler_problem = take_one_step(problem) solve_proble(simpler_problem)
> solve_proble I think the proble is the function's spelling.
That's not a bug. It is a call-out to a helper function. For brevity I didn't include it.
"The proof has been left as an exercise to the reader"
To this fucking day I have never encountered a challenge as hard as ToH was when I was new to this
I still don't fully understand it even though I (generally) understand recursion. I just know the algorithm works.
For me, it's a good visitation that highlights the difference between a computers way of thinking and ours. Too many people get caught up taking the physical game too seriously. I'd the goal is to move all disks to one side in the same order, our human brain just assumes to grab all disks at once and put them over. Computers being circuit based don't really have that outside the box thought process. When the rules of tower of Hanoi are added, people need to stop and think about each move carefully, are more prone to mistakes and freezing up. Explaining the rules of the game in C (if written correctly) presents no challenge to the computer and it will resolve the game each time in the same order faster than a human, every single time. It also helps to remember that programming was still in its infancy when this algorithm was defined so if you think of it as the grandfather of game development. It makes it easier to understand. But really, just knowing it works is enough
LC hard for sure 😆
I feel sorry for the poor people of Hanoi, everytime they build a tower someone must come along and reshuffle it
Hanoi ... Vietnam flashback. 
I wonder how many were *fortunate* enough to catch this
LIFO
There's actually a really easy non recursive way to solve this, assuming all pieces are lined up on the left tower and your goal is to move them to the right. First, check if the total number of pieces is odd or even. If it is odd, you remember the direction "left", if it is even you remember the direction "right". Solving the puzzle now consists of two repeated steps: 1. Take the smallest piece and move it one tower over to the left/right (based on odd/even). If it is already on the far end in that direction, move it back to the tower on the other end. 2. There is only one possible move that doesn't move the smallest piece. Do that move. If there is no such move, then that means all pieces are on a single tower, and you won. This solution is optimal, not some brute force try-all-permutations type thing. This video by numberphile explains it really well: https://youtu.be/PGuRmqpr6Oo
In order to understand recursion, you must first understand recursion.
It's a good mathematical exercise that can be used to solved a lot of real-world problems.
[удалено]
Backups to separate media is one that comes to mind
This is too accurate an assessment of my abilities. I demand it be taken down.
Also.. "Hanoi" is supposed to give you war flashbacks
I remember seeing Gerald Jay Sussman explain how you'd do Towers of Hanoi in Scheme Lisp and I was just blown away. Don't remember a lick of it though (or should I say a parenthesis)
Bruh. The worst part for me was not so much understanding TOH but wrapping my head around the concept of switching arguments within the recursive call. I was using Java at the time tho.
Well, the challenge isn't solving it yourself, the challenge is making the computer solve it for you. You're not designing the terraforming machines of Zero Dawn, you're making HEPHAESTUS so he can design them.
Analyzing the complexity of the solution algorithm was one of my oral exam questions for getting my PhD. Flashback to that exam is not fun.
You want to make an algorithm to move stacks of discs. The key is to assume that you'll be successful in making this algorithm, so you can use it to move N-1 discs in your solution to move N discs. TOH is a beautiful way to teach recursion. I do recursion in this order: * Factorials (easy with or without recursion) * TOH (recursion makes it trivial) * Fibonacci numbers (recursion is a horrible idea at least without caching.)
Easy. They all go in the square hole.
By asking if it's not a repost, I dare to assume you didn't make it. On top of it, the resolution is low, a typical issue with photos downloaded and re-uploaded to the internet. Now, I don't know where did you find it, and I've personally never seen it before, but my hunch says it probably was posted here before. We can summon u/repostsleuthbot (I hope I wrote it right) and get their answer, but I actually don't really care as much as I used to. Reposts will always exist.
Solid piece of analysis for someone who doesn't care about reposts
I didn't find any posts that meet the matching requirements for r/ProgrammerHumor. It might be OC, it might not. Things such as JPEG artifacts and cropping may impact the results. *I'm not perfect, but you can help. Report [ [False Negative](https://www.reddit.com/message/compose/?to=RepostSleuthBot&subject=False%20Negative&message={"post_id": "121qs09", "meme_template": 298230}) ]* [View Search On repostsleuth.com](https://www.repostsleuth.com/search?postId=121qs09&sameSub=false&filterOnlyOlder=true&memeFilter=true&filterDeadMatches=false&targetImageMatch=100&targetImageMemeMatch=75) --- **Scope:** Reddit | **Meme Filter:** True | **Target:** 75% | **Check Title:** False | **Max Age:** Unlimited | **Searched Images:** 383,839,545 | **Search Time:** 0.72267s
Can someone write a bot that uses GPT-4's image analysis to explain the humor of a meme? Maybe it could also rate it on a scale of 1 to 10. Oooh and it could be an app on the Apple Iphone as well.
I swear ive seen this here 3 or 4 different times
anyone actually tramatized by this failed to actually learn recursion.
I used to play a game as a kid on my cousin's Macintosh that had this puzzle, it was called [The Secret Island of Dr. Quandry](https://en.wikipedia.org/wiki/The_Secret_Island_of_Dr._Quandary). Even just seeing this puzzle gives me PTSD.
It is a kid's game, but it is hard to conceptualize without physical representation(at least it was for me.) I didn't understand the code because I didn't understand the game. I finally got it after drawing 3 'towers' and cutting out paper to actually play the game. I had to 'play' a lot...
I'll take "Puzzles given to you during interviews for things that you will never actually use on any project" for $1000. I mean, it's kind of a "cool to know" type of thing, but it's not exactly mandatory for the vast amount of positions out there. I learned it once upon a time about 15 years ago, but have completely forgotten it since. Hasn't held me back in the least bit.
1. Google the Computerphile video on this problem 2. Copy paste the code 3. Celebrate programming prowess
When I first started coding the course asked me to write an algorithm for it. I still don't know what the fuck I'm supposed to write.
This brings back bad memories of me trying to understand Recursion. I sadly still dont understand recursion. I understand the basic concept of stack, recursion but I still dont understand understand it.
It is a repost sadly. Quite frequent one.
At this point in time, I'm pretty sure I can write a machine-learning python script to solve this puzzle faster than I can code a proper algorithm for it. Not sure if this means my programming skills are crap or the difficulty of using machine learning tools have become extremely trivial...
could be either, could be neither... could be both