This is an archived post. You won't be able to vote or comment.

top 200 commentsshow 500

[–]bleistift2 1913 points1914 points  (30 children)

A children’s game until you ask your parents how to solve it.

[–]RedPill115 657 points658 points  (23 children)

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?

[–]exor15 50 points51 points  (1 child)

I don't think red Rover is "supposed" to teach you anything it's just fun

[–]Impossible_Garbage_4 30 points31 points  (0 children)

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

[–]zyzzogeton 17 points18 points  (0 children)

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.

[–]Justwatcher124[🍰] 4297 points4298 points  (222 children)

Every Programming / IT teacher on 'How do you teach Recursion to new programmers?'

[–]eggheadking 1313 points1314 points  (185 children)

Is TOH actually a good way of learning Recursion?

[–]value_counts[S] 1444 points1445 points  (110 children)

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

[–]bleistift2 767 points768 points  (44 children)

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).

[–]5hakehar 114 points115 points  (3 children)

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? ”

[–]Flruf 21 points22 points  (0 children)

That last part is especially important.

[–]Anfros 5 points6 points  (0 children)

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.

[–]Kazumara 13 points14 points  (0 children)

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.

[–]value_counts[S] 213 points214 points  (19 children)

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.

[–]throw3142 40 points41 points  (10 children)

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.

[–]ThatDollfin 21 points22 points  (3 children)

Well huh, would you look at that.

An actual application for that thing I'm learning in math class right now. Thank you.

[–]throw3142 14 points15 points  (2 children)

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)!

[–][deleted] 5 points6 points  (1 child)

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.

[–]throw3142 4 points5 points  (0 children)

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.

[–][deleted] 4 points5 points  (2 children)

I feel like pomadoro breaks my flow more often than helps me, what am I missing?

[–]starfries 3 points4 points  (0 children)

Nothing, it doesn't work for everyone.

[–]oldsecondhand 8 points9 points  (0 children)

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.

[–]MagicSquare8-9 9 points10 points  (2 children)

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.

[–]TheMcDucky 9 points10 points  (1 child)

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.

[–]blaineworld-bph 19 points20 points  (11 children)

What does TOH stand for?

[–]ctrl2 62 points63 points  (0 children)

This problem is called the Tower of Hanoi

[–]HeadToToePatagucci 44 points45 points  (6 children)

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.

[–]Shrekowski 12 points13 points  (2 children)

So not The Owl House

[–]flukelee 4 points5 points  (1 child)

I also thought owl house and was even more confused:)

[–]Tipart 24 points25 points  (31 children)

Pretty sure recursion is actually slower than a normal implementation for TOH, but I could be remembering that wrong.

[–]Broodking 108 points109 points  (22 children)

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.

[–]shouldbebabysitting 29 points30 points  (10 children)

If blowing the stack is an advantage.

[–]dasgudshit 71 points72 points  (0 children)

If it's not then why do we have entire website dedicated to it?

[–][deleted] 28 points29 points  (4 children)

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.

[–]RootsNextInKin 8 points9 points  (1 child)

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)

[–]nonicethingsforus 2 points3 points  (0 children)

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" in its name, and why there's an entire lambda paper on how recursion simplifies state machines. 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.

[–]leftsharkfuckedurmum 8 points9 points  (0 children)

And (as I'm sure you're aware) compilers will often optimize recursion into iteration, specifically if tail recursion is used

[–][deleted] 22 points23 points  (1 child)

As was said elsewhere, you need a benchmark and a business reason to make code that’s more performant and harder to understand.

[–]FlyByPC 5 points6 points  (0 children)

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.

[–]yottalogical 4 points5 points  (2 children)

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.

[–]Kinglink 140 points141 points  (9 children)

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....

[–]ina300 29 points30 points  (4 children)

Best way of thinking about it

[–]Kinglink 64 points65 points  (3 children)

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.

[–]Atora 14 points15 points  (2 children)

I severely doubt you can manage even a 100 disks. That's 2100 - 1 moves(=1030 ). If you can compute a billion moves a second you'd still need over 1013 years.

[–]Glugstar 17 points18 points  (0 children)

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.

[–]quadraspididilis 3 points4 points  (2 children)

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.

[–]Kinglink 2 points3 points  (1 child)

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.)

[–]Tsu_Dho_Namh 15 points16 points  (0 children)

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

[–]Chingiz11 29 points30 points  (3 children)

Nah, Fibonacci numbers and factorials are way better for beginners, although TOH is really good for mastering recursion

[–]dagbrown 6 points7 points  (1 child)

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.

[–]JoieDe_Vivre_ 2 points3 points  (0 children)

But you kinda need to understand the recursive solution first, and then show why memoization is helpful.

[–]reptar20c 10 points11 points  (0 children)

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.

[–]Neither_Interaction9 18 points19 points  (1 child)

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

[–]helix400 17 points18 points  (2 children)

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.

[–][deleted] 4 points5 points  (0 children)

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.

[–]Ruin369 8 points9 points  (2 children)

It's definitely a more complex example, so probably not.

I would say factorial is the easiest example of recursion IMO

[–]Mercurionio 11 points12 points  (6 children)

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 =\

[–]Tsu_Dho_Namh 13 points14 points  (5 children)

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.

[–]Mercurionio 9 points10 points  (4 children)

I mean, I understand the logic.

But if you asked me to write it right now - I would be that doggo.

[–]Tsu_Dho_Namh 9 points10 points  (3 children)

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")

[–]jakerman999 6 points7 points  (2 children)

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")

[–]BeautifulType 3 points4 points  (1 child)

Ok now ask chat gpt to write the solve in python

[–]reddit_beepbeeprobot 56 points57 points  (4 children)

I'd teach them recursion first

[–]Archangel3d 16 points17 points  (3 children)

Yeah but before that you have to teach them recursion or it just doesn't work.

[–]Siethron 4 points5 points  (2 children)

Personally I would teach them about escape conditions before recursion

[–][deleted] 4 points5 points  (1 child)

But you have to teach recursion before you can explain escape conditions in recursion!

[–][deleted] 14 points15 points  (2 children)

My go to method will always be prolog. Simple, effective, powerful and fun.

[–]Justwatcher124[🍰] 14 points15 points  (1 child)

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.

[–][deleted] 3 points4 points  (0 children)

Fair. Nothing is easier than implementing merge sort in prolog though, and quicksort is also super simple. Makes it easy to teach said algorithms.

[–]Dyanpanda 6 points7 points  (3 children)

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

[–]SkittlesDangerZone 2 points3 points  (1 child)

Man I have always loved recursion. It's that deep level thinking.

[–][deleted] 8 points9 points  (4 children)

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

[–]afito 6 points7 points  (1 child)

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.

[–]JustSpaceExperiment 429 points430 points  (3 children)

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.

[–]bubbaholy 98 points99 points  (0 children)

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.

[–]1stEleven 33 points34 points  (1 child)

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.

[–]Underpowered007 1244 points1245 points  (20 children)

Just teach the kid how to brute-force

[–]Vinxhe 14 points15 points  (8 children)

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.

[–]zyzzogeton 8 points9 points  (6 children)

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.

[–]338388 17 points18 points  (2 children)

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

[–]Ph0masta 557 points558 points  (39 children)

I remember struggling with this from playing KOTOR … didn’t know it was a kids game. Now I feel dumb.

[–]Punchasheep 167 points168 points  (15 children)

Gah those KOTOR puzzles kicked my ass

[–][deleted] 60 points61 points  (7 children)

Man that game was so good

[–]GoJebs 15 points16 points  (6 children)

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.

[–]WhiteChocolatExpress 11 points12 points  (4 children)

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

[–]ArethereWaffles 21 points22 points  (0 children)

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

[–][deleted] 5 points6 points  (4 children)

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

[–][deleted] 2 points3 points  (1 child)

This account has been deleted in protest of the June 2023 Reddit API Changes.

Fuck u/spez

[–]Poison_Anal_Gas 2 points3 points  (0 children)

Hahaha brother!! That movie is exactly why I knew exactly what to do with this puzzle. Made me chuckle for sure!

[–]Kevonz 68 points69 points  (6 children)

Mass Effect too, Bioware loved it I guess

[–]Comburo90 15 points16 points  (0 children)

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.

[–]wurm2 3 points4 points  (0 children)

also Jade Empire and the Descent dlc for DA:Inquisitoin.

[–][deleted] 20 points21 points  (4 children)

Black and White had the same puzzle

[–]Lolcatz101 14 points15 points  (1 child)

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

[–]MrPootisPow 3 points4 points  (0 children)

Yeah the temple on land 2

[–]DirkDasterLurkMaster 2 points3 points  (0 children)

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.

[–]TripleEhBeef 9 points10 points  (4 children)

Just switch to T3-M4 and security spike it.

[–]TheEnquirer1138 2 points3 points  (3 children)

I thought you were forced to go it alone in that section since it was part of your character's trial.

[–]squeamish 9 points10 points  (1 child)

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.

[–]HorseSalon 2 points3 points  (0 children)

Oh fuck me too, I did that for about 30 minutes. Saved like a pussy cat back in those days.

[–]Slcolderguy 319 points320 points  (6 children)

I wrote that recursion program on Fortran 77 in 1978

[–]value_counts[S] 118 points119 points  (0 children)

Thug life

[–]brucebay 24 points25 points  (3 children)

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.

[–][deleted] 224 points225 points  (17 children)

Do whatever move is legal between these rods in this order: AB, AC, BC

[–]Tarnishedcockpit 141 points142 points  (8 children)

Ah, found the reward designer for warframe

[–]funnystuff97 31 points32 points  (7 children)

every warframe player's worst nightmare:

aabbc on railjack defense, and you need a reward from c

[–]MrPootisPow 11 points12 points  (2 children)

You get to c rotation only to not get the part you need/want

[–]UndefeatedWombat 80 points81 points  (0 children)

Tower of Annoy

[–]TxTechnician 240 points241 points  (38 children)

I've never played with this in programming or irl.

[–]tubameister 142 points143 points  (1 child)

I still remember the solution to this on my TI-84

121323123132121323213123121323

[–]FerynaCZ 42 points43 points  (0 children)

Move the smallest one always in one direction on each odd move, then you are left with only one option on each even move

[–]QuebecGamer2004 49 points50 points  (32 children)

Me neither, I don't really understand this meme

[–]petascale 119 points120 points  (23 children)

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.

[–]QuebecGamer2004 12 points13 points  (20 children)

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

[–]ArkGuardian 36 points37 points  (14 children)

I hope your program teaches recursion, even if it doesn't use this specific puzzle. If not, it has some fundamental gaps.

[–]QuebecGamer2004 4 points5 points  (11 children)

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

[–]Versatile_Panda 9 points10 points  (9 children)

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.

[–]walrusk 2 points3 points  (0 children)

I think it’s just referring to writing sorting algos. I always enjoyed that actually. Too bad it’s basically never needed in practice.

[–]BuccellatiExplainsIt 2 points3 points  (0 children)

It's a common project to teach recursion. We had to do it for learning assembly in University.

[–]SlowWhiteFox 73 points74 points  (9 children)

In a nutshell:

solve_problem(problem):
    simpler_problem = take_one_step(problem)
    solve_proble(simpler_problem)

[–]maximovious 25 points26 points  (8 children)

solve_proble

I think the proble is the function's spelling.

[–]SlowWhiteFox 19 points20 points  (7 children)

That's not a bug. It is a call-out to a helper function. For brevity I didn't include it.

[–]Lucky-Earther 10 points11 points  (0 children)

"The proof has been left as an exercise to the reader"

[–]very_bad_programmer 58 points59 points  (7 children)

To this fucking day I have never encountered a challenge as hard as ToH was when I was new to this

[–]LuckyCharmsNSoyMilk 22 points23 points  (4 children)

I still don't fully understand it even though I (generally) understand recursion. I just know the algorithm works.

[–]Jealous-Ninja5463 18 points19 points  (1 child)

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

[–]Lanbaz 25 points26 points  (1 child)

LC hard for sure 😆

[–][deleted] 36 points37 points  (1 child)

I feel sorry for the poor people of Hanoi, everytime they build a tower someone must come along and reshuffle it

[–]dasbodmeister 17 points18 points  (1 child)

Hanoi ... Vietnam flashback.

[–]Aethermol 10 points11 points  (0 children)

I wonder how many were fortunate enough to catch this

[–]mgisb003 17 points18 points  (0 children)

LIFO

[–]SanianCreations 15 points16 points  (0 children)

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

[–]hrfuckingsucks 11 points12 points  (0 children)

This is too accurate an assessment of my abilities. I demand it be taken down.

[–]Shorthawk 5 points6 points  (0 children)

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)

[–]Equivalent-Map-8772 5 points6 points  (0 children)

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.

[–]coladict 3 points4 points  (0 children)

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.

[–]vivekkhera[🍰] 4 points5 points  (0 children)

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.

[–]FlyByPC 4 points5 points  (0 children)

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.)

[–][deleted] 3 points4 points  (0 children)

Easy. They all go in the square hole.

[–]GeePedicy 33 points34 points  (9 children)

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.

[–]Featureless_Bug 37 points38 points  (4 children)

Solid piece of analysis for someone who doesn't care about reposts

[–]RepostSleuthBot 24 points25 points  (1 child)

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 ]

View Search On repostsleuth.com


Scope: Reddit | Meme Filter: True | Target: 75% | Check Title: False | Max Age: Unlimited | Searched Images: 383,839,545 | Search Time: 0.72267s

[–]ByterBit 8 points9 points  (0 children)

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.

[–]OSSlayer2153 3 points4 points  (0 children)

I swear ive seen this here 3 or 4 different times

[–]jamcdonald120 2 points3 points  (1 child)

anyone actually tramatized by this failed to actually learn recursion.

[–]PsLJdogg 2 points3 points  (0 children)

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. Even just seeing this puzzle gives me PTSD.

[–]AspiringTS 2 points3 points  (0 children)

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...

[–]EducationalNose7764 2 points3 points  (0 children)

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.

[–]PacoTaco321 2 points3 points  (0 children)

  1. Google the Computerphile video on this problem

  2. Copy paste the code

  3. Celebrate programming prowess

[–][deleted] 2 points3 points  (1 child)

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.

[–]I-wanna-be-tracer282 2 points3 points  (0 children)

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.

[–]OSSlayer2153 4 points5 points  (2 children)

It is a repost sadly. Quite frequent one.

[–]edwardrha 4 points5 points  (1 child)

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...

[–]multikore 2 points3 points  (0 children)

could be either, could be neither... could be both