In order to understand recursion you need to understand recursion.

@callofdutymuhammad

4 жыл бұрын

Overused.

@fnorgen

4 жыл бұрын

I hate it when I get stuck in a why-loop.

@klaxoncow

4 жыл бұрын

No. In order to understand recursion, you need to understand recursion, unless you already do, in which case do nothing. Don't forget the exit clause! ;D

@unclvinny

4 жыл бұрын

@@klaxoncow Now I'm stuck doing nothing for the rest of my life. Perfect!

@schifoso

4 жыл бұрын

If you think you understand recursion, you don't.

"It's like a super power, ja?". It's always nice to hear that.

@willd0g

4 жыл бұрын

Mateja Petrovic i came to the comments for this and the clever title associated with it!

@robertpeng5632

4 жыл бұрын

Resembalance of Einstein

@tabaks

4 жыл бұрын

Op trt, gevezn zajn.

@billoddy5637

4 жыл бұрын

Wehrner von Braun

@theepicguy6575

4 жыл бұрын

I sense Assassins creed black flag

A bit of trivia - the Python recursion limit is actually artificially implemented to prevent bad coding practice and on it's own doesn't cause a stack overflow. Lets say we run this code: def foo(x): foo(x) foo(3) It will give us a recursion error after running around 1000 times (Pythons built in recursion limit). Now try this: import sys sys.setrecursionlimit(100000) def foo(x): foo(x) foo(3) Instead of a recursion error, this one runs a bit longer until it returns a SegmentationFault (core dumped) error. This is all because Pythons recursion limit of roughly 1000 doesn't cause a stack overflow and is only implemented to prevent bad coding practice, using sys module you can make the limit much higher until you cause an actual stack overflow (the SegmentationFault).

@Z0mbieAnt

4 жыл бұрын

Yeah he doesn't seem to be too knowledgeable in python all together. If you want to put variables into a string you don't need the .format. Just put an f in front and enter the variable names into the curly braces. Makes the code way more readable. f'Move the disk from {f} to {t}!' (That is python 3.6 and up, but why would you teach your students anything else?) His if/pass/else is just absolutely terrible coding style. Just go if/return and keep your code flat.

@SergeMatveenko

4 жыл бұрын

Well, this is video about recursion and the stack, but not about Python's implementation details, right?

@SergeMatveenko

4 жыл бұрын

@@Z0mbieAnt Let me assure you that professor Altenkirch is aware of a lot of things in programming.

@Z0mbieAnt

4 жыл бұрын

​@@SergeMatveenko Oh I'm absolutely sure he is. He wouldn't be in that position if he wasn't. I'm mostly complaining about style issues, which are usually only relevant on bigger projects and teams. I might have been too rash in calling him out there.

@bytefu

4 жыл бұрын

@@Z0mbieAnt He probably doesn't use format strings, because then he would have to explain them to those who don't know Python well. Everyone gets method calls. Early returns make sense in relatively long functions (which you shouldn't write), where the rest of the code is noticeably longer than the conditional return, so it makes sense to separate the "real work" from the handling of edge cases. I prefer short functions and the style he used, because it is explicit and because it is an expression rather than a statement. Also an early return does not make code "flatter", because now the return and the rest of the code have different indentation level. And you definitely should not be that concerned about "flatness" of your code if it's only 6 lines long anyway. You're thinking too hard about this, while also not paying enough attention to details. That's a suboptimal way to reason about code.

The skills, the looks, the accent... Prime movie villain material!

@videobenny3

4 жыл бұрын

I love listening to the professor!

@vojtechstrnad1

4 жыл бұрын

He reminds me of Javier Bardem in Skyfall.

@YouGuysAreAHoles

4 жыл бұрын

The shirt: Prime grandmother material.

@Ayyy-lmao

4 жыл бұрын

If you cant program the hanoi puzzle the laser moves 5 inches per minute!

@KurtRichterCISSP

4 жыл бұрын

He doesn't have to be a bad guy. He can be Laszlo in Real Genius 2

It kills me that he'll put a space before a colon, but not around operators or after commas.

@pluseaqual

4 жыл бұрын

Absolutely barbaric

@tamasgal_com

4 жыл бұрын

Yeah, Jupyter needs a PEP 8 linter... And also one for Julia ;)

@ori61511

4 жыл бұрын

PEP -8

@unclvinny

4 жыл бұрын

Quoting Conrad: "The horror! ..... the horror!"

@iliakorvigo7341

4 жыл бұрын

@@tamasgal_com Jupyter would really benefit from a built-in static analyser. Unfortunately, I don't see it happening any time soon.

"I will leave the robotic arm as an exercise"

@KieranShort

4 жыл бұрын

@MichaelKingsfordGray lol

@fathifathi8750

4 жыл бұрын

XDDD 😂😂😂😂

@afoiheagadwade2009

4 жыл бұрын

>every teacher ever

@egg5474

3 жыл бұрын

STEM Professors in a nutshell :

Recursion is a magic spell and stack space is its mana.

@henrydorsett6076

4 жыл бұрын

Nice. This analogy will get used when teaching. :)

@jacobrose9606

4 жыл бұрын

and you're a wizard

I do not understand anything, but I was satisfied when he moved the last disc from B to C.

@hammerjoe2008

2 жыл бұрын

The thing to understand how this works is that the code is not telling you what the size of the disc is. Its simply telling you to move the disc on A to C and so on. Because to solve this puzzle its simply a repetitive pattern (its always the same moves) the recursion works. Also note that the code starts at the bottom and recurses up, meaning that N=4 in reality is the bottom piece and not the top ond.

1:09 Of course, Prof. Altenkirch brushed up on his game beforehand with "Conceptual Programming with Python" (by Thorsten Altenkirch) XD

@stumbling

4 жыл бұрын

altenkirch = lambda py_knowledge : altenkirch(py_knowledge)

@Elesario

4 жыл бұрын

Subtle

@rramphal

4 жыл бұрын

Casual product placement 😋

@NicholasLeader0

4 жыл бұрын

Recursive

@fluffigverbimmelt

4 жыл бұрын

I bet he prepared for writing the book by reading "Conceptual Programming with Python" (by Thorsten Altenkirch)

i love how everyone on Computerphile has a great sense of humor and they're charismatic as well

This video made me learn Python. Today, I have built a specific calculator for work and a document generator, albeit simple. Thank you. I still feel i know very little, but i am looking forward to continue learning.

This seems so magical! In every introduction to this game it is made clear that you cannot put a smaller disc on a larger one. But here we have no explicit mention of that!

I have used recursion two times in my programming life. Once when I learned recursion using the tower of hanoi example in class. The second when I wrote my thesis, and in the x-reference section I wrote; Recursion, see Recursion.

@tmcode2010

4 жыл бұрын

I also only used 1 recursion on my programming life to make a tree view from 1 table. It took me 1 full day, but I'm proud of myself LOL

@Katatonya

4 жыл бұрын

I use it often when solving coding puzzles.

@RijuChatterjee

3 жыл бұрын

Never did a data structures course? Depth-first tree and graph traversals are what I associate recursion with most strongly.

I am disappointed with the lack of f-strings! In all seriousness, always love seeing Prof Altenkirch! Excellent, simple video illustrating a powerful tool.

@menelikm9779

4 жыл бұрын

I know right! My friend was using .format() in his project and when I tried to make it an f-string he looked so confused haha

@GuilhermeDiGiorgi

2 жыл бұрын

At first I was using "yada yada" + str(variable) + "yada yada" logic, then I learn to use .format, and of last month and so, I am getting used to f-strings, it's very satisfying to get to know better techniques over time.

I love the way he uses simple and clear examples to demonstrate an idea that is rather complex. Great work!

I'm not going to read all comments but i just want to make sure you guys appreciate his shirt. It's absolutely marvellous. And this absolutely dry german manner when he delivered the jupiter joke, i love it.

Wow. That's amazing power of recursion! Glad to experience it with hands on practice.

Please have this guy on more! His explanations are sooo good

I once found a recursive function call in an exception handler in C#. In the catch it waited 5 seconds and then called the same function again with the same arguments. Genius!

@softwaretechnologyengineering

4 жыл бұрын

If at first you don't succeed...

@BlockOfRed

4 жыл бұрын

I've done something like this one time (without a sleep)… It caused my program to send roughly 10000 mails to a colleague… 😂

@matteopascoli

4 жыл бұрын

caw25sha : maybe in python 4 they will add the try:except:retry construct 😈

@BlockOfRed

4 жыл бұрын

@@matteopascoli Retry until it works: for i in …: while True: try: # Do something… except: continue break

@matteopascoli

4 жыл бұрын

@@BlockOfRed : retry n times: for i in reversed(range(n)): try: foo() bar() baz() break except: if i == 0: raise but the retry construct would not repeat foo() if bar() raised ;)

Oh man recursion. It wasn't until I did Standard ML that I finally got to understand it. Definitely awesome stuff!

Is it weird that I understood recursion but not how the solution to this puzzle works?

@livedandletdie

4 жыл бұрын

It is easy, You move disc from Point A to Point C or to point B then you move a disc from Point A B or C to Point A B or C, until such as all discs have moved from Point A to C and are in the same ordering. It's really simple though For 1 disc it's simple you just move disc 1 from A to C for 2 discs it's move A to B A to C B to C. For 3 it's slightly harder, but it's AC AB CB AC BA BC AC, for 4 it's AB AC BC AB CA CB AB AC BC BA CA BC ACand so on.

@vadrif-draco

4 жыл бұрын

@@livedandletdie Thank you, Major.

@sairohit8201

4 жыл бұрын

@@livedandletdie you are simply amazing salute to you major

@kuyaraf110

4 жыл бұрын

@@livedandletdie But where in the program is the "in the same ordering" implementation ? Why does the program build the tower on C like it was initially standing on A, biggest disk on bottom, smallest disk on top ?

@JNCressey

4 жыл бұрын

@@kuyaraf110, If there is only 1 disk to move, this is easy, we just move it from the start peg to the peg we want to move it to. If there are N disks to move, with N>1, we use that we can call the function recursively to shift the top N-1 disks. We shall use a simple 3 step process: 1. Use the function call to move the top N-1 disks from the start to the spare peg. 2. Move the remaining disk to the destination peg. 3. Use the function call again to move those N-1 disks back on top of the last one on the destination peg. So in our call of the function to solve for N disks, it has twice called the function again to solve for N-1 disks while ignoring the Nth disk. - each of those calls would then need to call two times the function again to solve for N-2 disks while ignoring the N-1th disk. Since any instance of the function only cares about some top amount of disks, any disks that it is ignoring are larger so are valid to be placed upon with the disks it's working with. Therefore the rule about smaller going on top of bigger is obeyed all the time. This recursion happens all the way down until we have calls for the function to solve for just the top 1 disk while ignoring all the disks underneath. This time through the function, it can use our trivial solution of just moving the disk to where is needs to be. And when the function has an answer for its little part of the puzzle, it returns it to the instance of the function which called it, allowing that to read an answer and pass that on, and so on until it gets all the way back out to our original function call that produces an answer. In our main function call, the Nth disk is placed in the destination, and *then* the rest (N-1) are. In the call solving for N-1 disks, the N-1th disk is placed in the destination, and *then* the rest (N-2) are. This reasoning goes all the way through, and forces the final order of the disks.

More of these basic concepts with examples from this man please that was brilliant.

This was soooooooo supercool! My professor just copied the code and explained. Now, I understand the power. And, I really love his carefree nature and his accent.

This man not only amaze me with his skills, his dry homour cracks me up.

There is a way to do Towers of Hanoi without recursion, but doing this problem with recursion is insanely easy, and figuring it out non-recursively takes a wild insight I think. Anyways, 3Blue1Brown made a video about how you can use counting in Binary to solve Towers of Hanoi. Titled "Binary, Hanoi and Sierpinski, part 1".

Any recursive algorithm can be implemented nonrecursively using a stack. I learned that 25 years ago in an undergraduate computer science course. If you use a recursive algorithm, you are in effect just using the built-in stack managed by the compiler / interpreter.

@user-kh5tv9rb6y

4 жыл бұрын

It always annoyed me how in the video do the Ackerman function the guys says that there's just no way to avoid recursion. It *has* to be turned into a loop, that's just how computers work.

@zamalek4079

4 жыл бұрын

Using a custom stack is one possible outcome of defunctionalizing the continuation. You can also get simple loops (i.e. tail call optimization) or other solutions that require less memory. It's a refactoring worth learning.

@lycan1602

4 жыл бұрын

@@user-kh5tv9rb6y The reason that's said is because the loop you would have to write the calculation of the Ackerman function in is so impractical it becomes impossible, and it would take a tremendous amount of lines to write down. Recursion allows you to write it down in just a few lines instead. In that same video, he predicted the calculation (that was already going on for 2 months) would take a literal eternity to complete, but it is computable. To write it down in a for loop, however, is not possible, as you would run out of atoms to write it on.

@TheRiskyChance

4 жыл бұрын

I'm new to computer science: Are you saying that you shouldn't use recursive functions, and instead just use the stack?

@jej3451

4 жыл бұрын

@@TheRiskyChance Not at all. Sometimes a recursive implementation is the simplest one, and that usually means it's the best. I was just quibbling with the claim in the video that it isn't possible to implement the algorithm nonrecursively.

Recursion is like an applied induction proof. Never thought of it this way before.

@boonator1496

4 жыл бұрын

I can see where you draw that analogy from, but I don't think that's true, I still have to give it some thought for a definite answer though

@benwincelberg9684

4 жыл бұрын

Yeah

@jonahcornish6160

4 жыл бұрын

Was thinking the same thing as I watched this

This still blows my mind. Very jolly good video.

I don't know why, but just the way he speaks make me smile, with a hidden sense of laughter, but still saying serious because I gotta understand recursion

This professor explains things very well.

i remember in school learning this. it was a real moment of "before" and "after".

Thanks for sharing one of your superpowers with us, Thor!

I liked the way in which Professor Altenkirch used the toy to write the program. Visualizing things really helps us to program.

Really good case for recursion. In most cases you can use a while loop (or tail recursion in the functional programming languages which is the same).

Officially my new favorite Computerphile guy.

I only noticed after a couple of minutes that he was speaking English... Ich dachte er redet deutsch mit mir.. so hart war de Akzent :D

@tainicon4639

4 жыл бұрын

WILD WILD VAPE haha, I have had that happen the other way around too haha

I spent a so long trying to understand recursion... and this guy made it so easy to understand.

The example I always use to demonstrate recursion is the Fibonacci sequence, but I have to agree Towers of Hanoi is a very elegant example.

It is like: "Mom, I will be home for 20 minutes. If I am not, read it again." 🤣

@pararera6394

4 жыл бұрын

@MichaelKingsfordGray explain why. And what name has to do?

@pararera6394

4 жыл бұрын

Who is your dealer?

@tubeyoukonto

4 жыл бұрын

@@pararera6394 let me answer the question, as the asshole wouldnt. The effect you describe is basically a while-loop always just asking if you arrived already. You dont need recursion for that. Recursion is used when the iterations/steps/layers are dependent of each other, especially when the ith iteration is dependent on the i+1th iteration. So you could have something like this: while(not at home) sleep(20 minutes) I mean, you can always create recursions on a way that they act like loops but thats bad practice. You would for example use recursion to calculate the nth number of the fibonacci sequence. You can google recursive implementations of that. Basically, a loop is just that, a loop. And recursion is a tree/graph, which is built up and then breaks itself down again to return the calculated outcome in the first node.

@pararera6394

4 жыл бұрын

@@tubeyoukonto but you can do it with recursion also, right?

@tubeyoukonto

4 жыл бұрын

@@pararera6394 well, yes. You could, but as I said its bad practice. You needlessly build a stack of iterations that dont hold any important information. If you would do this recursive like function waitIfImNotThere() { If(not arrived) { wait 20 min waitIfImNotThere() } } Then the program would remember every iteration. So it builds a stack. If(not arrived) { Wait 20 min If(not arrived) { Wait 20 min If(not arrived) { .... You remember all of that information. And if you have a bad exit condition and its never called (thats where the recursion works back again, returning the values back to the iterations that called them), you might run into an error, a stack overflow, because that stack building runs indefinetly or at least until the limit is reached. So yes, its possible, but nobody should ever use recursion like that. Thats what loops are for :) Because loops basically throw away the information after every iteration. You dont build a stack. The only information you can save is the one that is based outside the loop and that you only manupulate/override in the loop, still saving it outside. So if you simply looped waitIfImNotThere. There would be no stack and after every iteratiln all info within that functiln is lost. However, if you initialize a variable outside of the loop and always add the waiting time to it, that info obviously stays. Because the reference is outside the loop and will be available in that frame.

I remember the Hanoi recursion puzzle from back when I was in University. It's en excellent exercise for a beginner programmer.

@DutchmanDavid

4 жыл бұрын

For me, it was a terrible intro. Recursion really clicked for me when I learned how the map function worked in Haskell.

I once at work created a program where the use of recursion simplified the solution. What it does is that the program takes one input file and generates an output file. The output file is just a sequential file containing the structure of xml(tags, attributes, elements, namespaces) and the values. It just converts the xml from one markup language to another, cobol-friendly, markup language. It goes the orher way around aswell. Generating an xml from the sequential data file. I did use recursion to visit every child of the xml-node I was standing at. So for every node the function called itself until I had visited every node on that xml-tree. It was done using python and we use it everytime we have to handle xml-files in cobol. 👍🏻

Your looks and accent really goes well together. It's awesome! In the best way possible.

wow, nice and simple illustration to the super power of recursion

"To move a robotic arm.....zzzz zzzzz" I died🤣🤣

Love the accent, love the shirt, love recursion explanation. This video is a pure win situation.

Thanks for the video(s)... I just purchased your book... Looking forward to digging into it.

Brilliant product placement! Had to order the book!

I forgot about that one .... very nicely explained, thank you.

0 Sekunden und nach dem SOOOOO weiß man schon dass der deutsch ist xD

@MilitantPacifista

4 жыл бұрын

"das wird dem studierenden als Übung überlassen" ich krieg Alpträume

@livedandletdie

4 жыл бұрын

Weiß=Deutsch...

@boonator1496

4 жыл бұрын

Am geilsten war eigentlich schon noch "Anakonda"

@vorrnth8734

4 жыл бұрын

Wanz ju no rekörschen.

@Luca-hn2ml

4 жыл бұрын

@@vorrnth8734 xDD

What an amazing professor, he looked boring and intimidating at the beginning , but you discover he's funny, interesting and smart once he begins explaining. I I gotta look into his book now

I have to say, as a C.S. master I do not understand recursion. I always write down the base case and the inductive/recursive step(s) and am always amazed that it just works. With recursion I can trust my worked out theory. Formulating this loop-based with some mutating data-structures taxes my programming skills, which I am less confident of.

Could never imagine the use of recursion except for factorials. Nice job!

@Sebastian-ru3ed

4 жыл бұрын

I dont have a lot of examples but its used in sorting algorythms eg. Merge Sort

Awesome. I've just added this to stack overflow. I wish all questions in there had an answer like that!

@lpkuchembuck

4 жыл бұрын

Muito interessante!.....🤔

@jjuca_

4 жыл бұрын

@@lpkuchembuck hahahahahahahahaha

@justinlindfors8512

4 жыл бұрын

Not sure If toxic community Or very critical of code

Just brilliant bit of exposition.

This is exactly the type of guy that I would expect to learn recursion from

I used to use recursion for input error checking for code at school. Throw the input and the expected type into the function, the fucntion checks it and if invalid, printed a message. Then you would add another input, throw it into itself, and so on. When a legit input was found the fucntions would all 'collapse' back out and give you your input back. I came up with it around year 10 (14-15 yrs old) while writing programs at school. I've never seen anyone else do it

Just to be hannoying: For an odd number of disks (for even, replace "right" with "left"), the iterative solution goes as follows. move the smallest disk to the right (with wrap around) repeat 2^(n-1) times: make the unique valid move between the two other poles move the smallest disk to the right (with wrap around)

PEP8 police does not approve!

@vincenzo3574

4 жыл бұрын

It hurts to look at the space before the colons and at the missing space after the commas

@BlazingSun46

4 жыл бұрын

Well, that’s one of the beauties of Python, everybody uses it. Researcher, Mathematician, Educator, they don’t care one bit about convention, as long as it get stuff done (and they aren’t coding in a team) it’s fine.

@tamasgal_com

4 жыл бұрын

It's called "PEP 8", not "PEP8".

@code-dredd

4 жыл бұрын

@@tamasgal_com Technically, it's PEP-0008 😏

@code-dredd

4 жыл бұрын

@@BlazingSun46 As long as I don't have to clean it up, then he's free to create (and maintain!) his own mess. The problem is that, in reality, someone else must always end up reading and working with such code.

First 40 seconds and I already love this guy..

This video is brilliant, he's a great teacher!

That’s a great shirt. Thanks for making me less afraid of recursion.

You want me to explain recursion? Wait a bit I gotta get my towers of hanoi. Literaly every video about recursion I've seen uses this problem, and it's clear why. It sums it up really nice.

Vielen dank für den Trick. Hatte da nie so drüber nachgedacht.

Those variable names are stellar.

As a mathematician, I get recursion. As someone who hasn't done much coding since Borland was still putting out Pascal, this feels a little like magic.

This guy is like every lecturer i've ever had rolled into one

I bet this dude is a member of some industrial music band.

@sairohit8201

4 жыл бұрын

he's dave grohl from foo fighters lol

@reljasaurus

4 жыл бұрын

@@sairohit8201 foo(x) fighters

Had to do simple script to automate workflow and I remembered this clip. Surprisingly short script code seems to work fine so I am probably close to understanding something about recursion.

This is actually the best explanation of recursion on an example that i've seen. Thanks, it's much clearer now!

Thanks for making such videos. I have the feeling that people tend to not think about algorithms anymore but rather run a random sh*t 100 gazillion times with a deep neural network behind the scenes, bursting hundreds of thousands of CPU time and producing a neural network which solves this for exactly N disks and M sticks. Halleluja...

Top work on the thumbnail.

This is a really helpful video - what a guy

If I remember right, back in the mid/late 80ies, I saw this as an example file in one of the earliest versions of Autocad. Drew the game in 3D and moved the discs. Of course created in AutoLisp.

He is so naturally funny! I'd love for him to be my mentor!

In thinking about this before watching the video, I am stuck on the fact that If I were to build this in the "real world" I would be error-checking to make sure that the discs were never on top of a smaller disc, and keeping track of all the disc sizes, just for error checking purposes.. (even it it was just error checking that the human setting up the discs didn't make a mistake) but this is a truly elegant solution for the specific case where the starting setup is assumed correct, which it must be, by the rules of the game. In situations like this, I need to wrap my head around the fact that you should not worry about the definition of the "given" situation, and not complicate code just to detect or avoid error situations that cannot exist.

I liked this video after the first 48 seconds. The way he described recursion as a Super Power. Just take my money.

Explanation is perfect

The reason for an iterative solution rather a recursive solution is that, although easier to implement, the recursive solution usually has higher time and space complexities. I remember the tower of hanoi is related to counting in base 2, so if I wanted to implement an iterative solution, assuming that the tower of hanoi is Primitive Recursive, I would use the counting in base 2 as my starting point for analysis.

Neat! You can easily guess how many steps you have to do to complete it based on number of discs. Its (2^n)-1.

Very easy to understand hanoi with this video ! Thanks !

I had this problem in a quiz using Pascal , I used two as the base case , it did not cross my brain to use zero as the base case. Granted it was the day is pen and pencil, and I have two more problems to solve but this is quite clever

Loved the video! John Mcclane says Hi.

Professor Thorsten Altenkirch looks like Dave Grohl and Taylor Hawkins have morphed into 1 person and quit Foo Fighters for Foo(x) Pythons.

@muhaha714

3 жыл бұрын

LOL yes! He also looks like the guy from the 'give me compliments' music video

Nicely done! Thorsten! :-)

Awesome teaching style 👌

Great video!

I think the first time I figured recursion out was when I was writing a function that listen all the files and directories inside a given path and realized the only way to do it was for the function to call it's self until it ran out of new subdirectories

In my computer science classes that was one of the first exercises we were taught in order to learn about recursion but back then we used C. I remember logging in and making the number of disks a large number and running my program to see how long it took for the college’s computer to run and/or crash. I believe I let it run for awhile and then just killed the program. Don’t remember but I recall the number of disks used makes the number of moves go up exponentially. Could be wrong this was many years ago.

Amazing way to show..

Was such a good video.

:Jupiter.. I think it's also a planet? Something like this."

Nice subtle book plug

Love this guy

Downloaded Anaconda and it throws “GOT NO BUNS” error

@user-oh4ky7rv5i

4 жыл бұрын

Do some squats

@Blox117

4 жыл бұрын

@@user-oh4ky7rv5i will that make me a better programmer?

@WhompingWalrus

4 жыл бұрын

@@Blox117 Worse. if ( ! social_prospects ) code();

@rob011

4 жыл бұрын

raise AnacondaDontError

@tombrady7390

3 жыл бұрын

Exception handling, bro do one of those

this professor is explaining it beautifully..never listen 😃

he explains it super well

Recursion itself isn't that difficult but figuring out when you should use it can be hard especially in non functional languages. Even in functional languages you generally will have access to iterators and recursion won't always be the best choice (though the system probably uses recursion in the iterator).

@gileee

4 жыл бұрын

You only use recursion when doing it Iteratively would be much more difficult or impossible (since problems which have an iterative solution is a subset of the problems with recursive solutions). I mostly use it when my code branches like when going over an n-ary tree. But recursion can be a fun exercise. I've written a c++ program before where I removed all loops and just used recursion, so for example my main program loop was the main function calling itself.

@draakisback

4 жыл бұрын

@@gileee sure you are absolutely right. I use recursion quite a bit when working with elixir and clojure since it's fairly intuitive to do so in those languages. With clojure youve got concepts like transducers which rely on recursive code (they are essentially combined reduce functions) and in elixir it's not uncommon to write multiple function heads which call each other recursively. It can also help with managing state especially since all of the data types are immutable.

@gileee

4 жыл бұрын

@MichaelKingsfordGray Tail recursion sure, just replace it with a loop and however many extra variables outside the loop you need. But in the general case it's as trivial as implementing your own stack and program flow control from scratch.

@gileee

4 жыл бұрын

@MichaelKingsfordGray But at the end of the day you're just moving where your program saves the calls, which granted does give you an option of dynamically increasing the stack as needed (which is very useful if you're willing to take the small performance hit). But it's still going to crash eventually when you hit the max memory available to your program. Binary, Ternary... recursions can't be optimized out since logically you keep needing to hold more data at each step into a new function. With tail recursion you can just replace the current function call with the new one, so your tail recursive function never grows the stack beyond the 1 function call.

Brilliant!!!

I like how he explains this.

the last thing he said is correct, that (in this case) its easier to use recursion but what i learned so far is that for every recursive solution there is an iterable solution too and the other way around. it sounded for me like there would be no solution without recursion.

@shdon

4 жыл бұрын

The iterative solution is trivial too and much easier to process when doing it by hand: 1. move the smallest disk one peg to the left (if it's on the leftmost peg, move it to the rightmost peg - basically wrapping around) 2. if not solved, do the only move you can make that doesn't involve the smallest disk 3. if not solved, go to step 1 You can also move the disk to the right in the first step, as long as you do it consistently. Moving to the left will end up with the stack on peg B for an even number of disks and on peg C for an odd number of disks. Moving to the right will end up with the stack on peg B for an odd number of disks and on peg C for an even number of disks. I suppose you could adjust step 1 to make sure it always ends up on peg C.

@raykent3211

4 жыл бұрын

@@shdon tracing that through for two disks (even), move right solves in two steps. Move left also solves, but in six steps. So I think your last point is for efficiency?

@shdon

4 жыл бұрын

@@raykent3211 That is correct, it basically moves the stack in the direction of small disk movement by 1 peg. And for an even number of disks, the stack moves in the opposite direction by 1 peg. So if you want to move the stack to peg B or peg C, you need to choose appropriately.