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).
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 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.
@@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.
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
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.
@maaikevreugdemaker9210 Continued doing small projects for work. Dipped toes in javascript. now with Chagpt and AI i can get base code for simple tasks, i would say that i can do more, but i feel i learned less.
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.
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'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.
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!
@@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 ;)
I am disappointed with the lack of f-strings! In all seriousness, always love seeing Prof Altenkirch! Excellent, simple video illustrating a powerful tool.
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.
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.
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.
@@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 ?
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
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.
@@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 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.
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".
Towers of Hanoi was a puzzle my dad gave me. I figured out that it eventually was just repeating steps and i could answer how many moves it would take. Yet when I learned recursion I was still blown away by it.
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.
@@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.
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.
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.
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.
@@MinusPi-p9c 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 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.
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)
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. 👍🏻
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.
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
He may be using an older version of Python, or not yet broken the habit of string formatting. That said, f-strings are a godsend and one of my favorite recent features.
@@xario2007 I would say, str.format() builds on the knowledge that values of parameters listed in a function call are passed into the function (used in majority of programming languages) and a literal string can behave like an object and have methods (only a subset of languages). fstrings at first sight look like specially marked literal strings; they require the knowledge that the interpreter itself evaluates the string at runtime using variables in the scope.
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.
@@SergeMatveenko It has nothing to do with implementation limitations. The problem is keeping track of stack frames, and it just gets messy when debugging. Java does not optimize tail recursion either, for the same reason.
@@TheMysteriousMrM That's exactly the meaning of "depending on the implementation." Easily keeping track of debugging info (e.g. stack trace) is a trade-off you get by not allowing tail-call optimization (or as a subset, tail-call recursion). IMO, Guido is a bit too militant with this decision (there are some ways to keep a decent amount of debugging info with TCO).
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).
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.
@@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.
@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.
@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.
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.
But I think that the video has been shortened because it does not stress enough importance of trivial cases for recursion. And then there are more types of recursion, of course, which are not mentioned there.
loots of stuff in coding/computer science is like that: there's a obvious to anyone solution, that is not too hard to implement, but extremely inefficient. then, there's a completely different solution, probably invented by Euler(or at least some other mathematician), that wasn't even supposed to have anything to do with computers, that solves the problem much more efficiently. my favorite example is the Fibonacci sequence. in python code: obvious solution: def Fibonacci(N): if n < 1: return 1 else: return Fibonacci(N - 1) + Fibonacci(N - 2) the problem of this solution is that it calculates the lower Fibonacci numbers over and over again, resulting in a lot repetitive computation to calculate result you already knew, and this problem gets worse as N increases, making this algorithm exceedingly slow for any practical use. but did you know that the Fibonacci sequence can be approximated by (phi^N)/root(5)? yeah, instead of all this recursion, repeatedly calculating the same values, there's a way to go straight from the index of the number on the sequence to, approximately, the number itself. with some extra code for the rounding/square roots we have: def round(x: (int, float), r: float = 0.5) -> int: """ Rounds up if the fractional part of x is greater than r, otherwise down""" if x - int(x) > r: return int(x)+1 else: return int(x) def root(x, r=2): """ root function, since i don't like to import just one function""" return x**(1/r) """ the number phi ~ 1.618""" phi = (1 + root(5))/2 def fibo(n: (int, float), rounded: bool = True) -> (int, float): """ calculate the Nth Fibonacci number using it's approximate exponential, (phi^n) / root(5), then rounding if desired""" res = (phi**(n))/5**(1/2) if rounded: res = round(res) return res if you want to be ... scientific about how bad the recursive implementation is(even when using a cache to avoid repeating the same index!), the recursive implementation(with cache!) has time complexity(how longer the program tends to take as N increases) of O(phi^(N)), meaning, it increases exponentially(I.E. super fast -> inefficient algorithm), meanwhile second implementation has a time complexity of O(1), which means, it doesn't increase even as N becomes larger and larger(not exactly true, due to the fact that as N gets bigger storing it becomes harder for the computer which increases overhead, but the number of operations, which is what the O notation cares about, stays the same)
Yeah, recursive solutions are normally simpler. But simpler to us. You have to avoid recursion when programming, is usually horribly inefficient and has the inherent limit of the stack size. Fortunately, there's always a way to do it non-recursively.
Marc Gràcia As with all things, there are exceptions to that. For example, the recursive solution for calculating greatest common denominators (developed by Euclid) is actually the most efficient solution.
//N=4 a=A b=B c=C line 1 //N=3 a=A b=C c=B line 2 //N=2 a=A b=B c=C line 3 //N=1 a=A b=C c=B line 4 //Move a to c from line 4 A-B //End of recursion from line 4, continues back to line 3 //Move a to c from line 3 A-C //N=1 a=B b=A c=C line 5 //Move a to c from line 5 B-C //End of recursion from line 5, continues back to line 2 //Move a to c from line 2 A-B //N=2 a=C b=A c=B line 6 //N=1 a=C b=B c=A line 7 //Move a to c from line 7 C-A //End of recursion from line 7, continues back to line 6 //Move a to c from line 6 C-B //N=1 a=A b=C c=B line 8 //Move a to c from line 8 A-B //End of recursion from line 8, continues back to line 6 //End of recursion from line 6, continues back to line 1 //Move a to c from line 1 A-C //N=3 a=B b=A c=C line 9 //N=2 a=B b=C c=A line 10 //N=1 a=B b=A c=C line 11 //Move a to c from line 11 B-C //End of recursion from line 11, continues back to line 10 //Move a to c from line 10 B-A //N=1 a=C b=B c=A line 12 //Move a to c from line 12 C-A //End of recursion from line 12, continues back to line 9 //Move a to c from line 9 B-C //N=2 a=A b=B c=C line 13 //N=1 a=A b=C c=B line 14 //Move a to c from line 14 A-B //End of recursion from line 14, continues back to line 13 //Move a to c from line 13 A-C //N=1 a=B b=A c=C line 15 //Move a to c from line 15 B-C //End of recursion from line 15 //End of recursion I lost 3 brain cells doing this.
2:40 "you download something called anaconda" conda is completely optional to run jupyter notebook , just do `pip install jupyter` then do `jupyter notebook` and you are set
I prefer pip over anaconda just because it is easier for me to install requirements.txt using pip. Although I haven't tried anything other than pip3 so far
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.
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.
Single letter variable names are horrible. You could just as well call your variables Hans or Susi. It tells you nothing about what is in there, or what it's for. Why call something "f"? Because it stands for "from". Then why not call it "from". Or better yet, call it "fromTower". This way you know exactly what it's for, without having to derive the meaning every single time.
It looks nicer and is faster to type. For simple cases like this I think it's actually a better practice, the function has 4 lines of code, figure out by yourself what the variables mean if you really need to.
_"Please please please do not encourage new programmers to use single-letter variable names!!""_ Why? It wouldn't really help here and having longer names makes the code really tedious. What would actually help would be a comment saying what the function does and its type e.g., > -- hanoi n f h t gives list of moves to take stack of size n from f to t via h hanoi :: Int -> Peg -> Peg -> Peg -> [Move] hanoi n f h t = ...
Twenty disks should require 1,048,575 moves. Although that is a lot, a computer should be able to print 1 million lines to the console in a fairly short amount of time.
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...
The rules of the towers of Hanoi force discs to always be in order - smallest on top, larger in the bottom. Every function call is moving the largest disc it knows about to a space that has no smaller discs, because it just made a recursive call to move any smaller discs to the third (helper) stack. It finishes by transferring the smaller discs onto the large disc, ensuring that all the smaller discs are on one pillar when the function returns. As long as the deepest call works, and it will because it won't have to move any discs, the whole arrangement of movements will complete the task. Some call designing a function like this "leap of faith" programming; by divide and conquer, we assume we can complete the task for some smaller problem. We then find a set of smallest needed problems to solve, and address those specifically.
So the solution uses the cases of "one disk less" (n-1) to solve the problem for any amount of disks (n), but how can this work you ask? In case 0 (base case): we simply don't move, done, nice job. In case 1: We use the solution for 0 to move 0 disks from A to B (via C), then we move our single disk from A to C, then we move 0 disks from B to C (via A). In case 2: We use the solution for 1 to move 1 disk from A to B (via C), then we move our single disk from A to C, then we move 1 disk from B to C (via A). In case 3: We use the solution for 2 to move 2 disks from A to B (via C), then we move our single disk from A to C, then we move 2 disks from B to C (via A). You can already very clearly see the pattern that arises. We always start with all disks on A and (B and C) empty, and (that's also important for this solution) with all disks ordered from smallest at the top to biggest at the bottom! Given such problem (n) we can look at a simpler problem of "one disk less" (n-1) and just "ignore" the biggest disk (1) on the bottom as all other disks are smaller and thereby can move freely onto the bigger one by definition of the problem. Then solve (n-1), move our previously ignored single disk over to the target and now repeat the process for the (n-1) disks. So how do we solve (n-1)? That's easy, we already did that, didn't we? We know we can move (n-1) disks from A to C (via B) by simplifying the problem to (n-2). Now that we know we can move (n-1) disks from A to C (via B) we also know we could do the same to move them from A to B (via C), we just switch target and helper this time (or switch accordingly for any desired origin, destination and helper). Knowing this we can solve for n! We first simplify the problem and: We use the solution for (n-1) to move (n-1) disks from A to B (via C), then we move our single disk from A to C, then we move (n-1) disks from B to C (via A). But that sentence is exactly what I used for cases 0 to 3 isn't it? The sentence above is also basically already the code (with A = f, B = h, C = t): "We use the solution for (n-1)" already screams recursion base case is 0, we don't work with "negative disks" -> if n == 0: pass else "move (n-1) disks from A to B (via C)" -> hanoi(n-1, f, t, h) "then we move our single disk from A to C" -> move(f, t) "then we move (n-1) disks from B to C (via A)" -> hanoi(n-1, h, f, t) So in essence this simply works because the case of "one disk less", which ultimately boils down to the base case of 0, works. Example 5: How do we solve for 5? We solve for 4, move 1 over, solve for 4 again, done. But how do we solve for 4? We solve for 3, move 1 over, solve for 3 again, done. But how do we solve for 3? We solve for 2, move 1 over, solve for 2 again, done. But how do we solve for 2? We solve for 1, move 1 over, solve for 1 again, done. But how do we solve for 1? We solve for 0, move 1 over, solve for 0 again, done. But how do we solve for 0? We are already done.
I always wonder what programmers or professors have against using readable names? If you mean "from" and "to", just call the variables "from" and "to" instead of 'f' and 't'. Please. It makes your application so much more readable and easier to understand.
When I started programming all variable names were either a single letter or a single letter with a digit - the programming language simply didn't allow more than that (early versions of BASIC). It's hard to break the habit. The professor looks older than me, which means probably spent more years in environments with limited variable names, and the habit is even more ingrained for him.
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
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).
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.
Well, this is video about recursion and the stack, but not about Python's implementation details, right?
@@Z0mbieAnt Let me assure you that professor Altenkirch is aware of a lot of things in programming.
@@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.
@@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.
"It's like a super power, ja?". It's always nice to hear that.
Mateja Petrovic i came to the comments for this and the clever title associated with it!
Resembalance of Einstein
Op trt, gevezn zajn.
Wehrner von Braun
I sense Assassins creed black flag
In order to understand recursion you need to understand recursion.
Overused.
I hate it when I get stuck in a why-loop.
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
@@klaxoncow Now I'm stuck doing nothing for the rest of my life. Perfect!
If you think you understand recursion, you don't.
It kills me that he'll put a space before a colon, but not around operators or after commas.
Absolutely barbaric
Yeah, Jupyter needs a PEP 8 linter... And also one for Julia ;)
PEP -8
Quoting Conrad: "The horror! ..... the horror!"
@@tamasgal_com Jupyter would really benefit from a built-in static analyser. Unfortunately, I don't see it happening any time soon.
The skills, the looks, the accent... Prime movie villain material!
I love listening to the professor!
He reminds me of Javier Bardem in Skyfall.
The shirt: Prime grandmother material.
If you cant program the hanoi puzzle the laser moves 5 inches per minute!
He doesn't have to be a bad guy. He can be Laszlo in Real Genius 2
i love how everyone on Computerphile has a great sense of humor and they're charismatic as well
"I will leave the robotic arm as an exercise"
@MichaelKingsfordGray lol
XDDD 😂😂😂😂
>every teacher ever
STEM Professors in a nutshell :
Recursion is a magic spell and stack space is its mana.
Nice. This analogy will get used when teaching. :)
and you're a wizard
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.
How's it going after 4y?
@maaikevreugdemaker9210 Continued doing small projects for work. Dipped toes in javascript. now with Chagpt and AI i can get base code for simple tasks, i would say that i can do more, but i feel i learned less.
1:09 Of course, Prof. Altenkirch brushed up on his game beforehand with "Conceptual Programming with Python" (by Thorsten Altenkirch) XD
altenkirch = lambda py_knowledge : altenkirch(py_knowledge)
Subtle
Casual product placement 😋
Recursive
I bet he prepared for writing the book by reading "Conceptual Programming with Python" (by Thorsten Altenkirch)
I do not understand anything, but I was satisfied when he moved the last disc from B to C.
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.
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'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.
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!
If at first you don't succeed...
I've done something like this one time (without a sleep)… It caused my program to send roughly 10000 mails to a colleague… 😂
caw25sha : maybe in python 4 they will add the try:except:retry construct 😈
@@matteopascoli Retry until it works:
for i in …:
while True:
try:
# Do something…
except:
continue
break
@@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 ;)
I am disappointed with the lack of f-strings!
In all seriousness, always love seeing Prof Altenkirch! Excellent, simple video illustrating a powerful tool.
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
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.
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.
Is it weird that I understood recursion but not how the solution to this puzzle works?
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.
@@livedandletdie Thank you, Major.
@@livedandletdie you are simply amazing salute to you major
@@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 ?
Just move the bottom one *with the rest on top*
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
"To move a robotic arm.....zzzz zzzzz"
I died🤣🤣
Please have this guy on more! His explanations are sooo good
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.
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
I use it often when solving coding puzzles.
Never did a data structures course? Depth-first tree and graph traversals are what I associate recursion with most strongly.
Dijkstra entered the chat
It is like: "Mom, I will be home for 20 minutes. If I am not, read it again." 🤣
@MichaelKingsfordGray explain why. And what name has to do?
Who is your dealer?
@@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.
@@tubeyoukonto but you can do it with recursion also, right?
@@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.
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".
Towers of Hanoi was a puzzle my dad gave me. I figured out that it eventually was just repeating steps and i could answer how many moves it would take. Yet when I learned recursion I was still blown away by it.
I love the way he uses simple and clear examples to demonstrate an idea that is rather complex. Great work!
Recursion is like an applied induction proof. Never thought of it this way before.
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
Yeah
Was thinking the same thing as I watched this
Oh man recursion. It wasn't until I did Standard ML that I finally got to understand it. Definitely awesome stuff!
I bet this dude is a member of some industrial music band.
he's dave grohl from foo fighters lol
@@sairohit8201 foo(x) fighters
Wow. That's amazing power of recursion! Glad to experience it with hands on practice.
This professor explains things very well.
This still blows my mind. Very jolly good video.
PEP8 police does not approve!
It hurts to look at the space before the colons and at the missing space after the commas
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.
It's called "PEP 8", not "PEP8".
@@tamasgal_com Technically, it's PEP-0008 😏
@@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.
0 Sekunden und nach dem SOOOOO weiß man schon dass der deutsch ist xD
"das wird dem studierenden als Übung überlassen"
ich krieg Alpträume
Weiß=Deutsch...
Am geilsten war eigentlich schon noch "Anakonda"
Wanz ju no rekörschen.
@@vorrnth8734 xDD
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.
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.
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.
@@MinusPi-p9c 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.
I'm new to computer science: Are you saying that you shouldn't use recursive functions, and instead just use the stack?
@@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.
Officially my new favorite Computerphile guy.
I spent a so long trying to understand recursion... and this guy made it so easy to understand.
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)
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.
i remember in school learning this. it was a real moment of "before" and "after".
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
WILD WILD VAPE haha, I have had that happen the other way around too haha
I remember the Hanoi recursion puzzle from back when I was in University. It's en excellent exercise for a beginner programmer.
For me, it was a terrible intro. Recursion really clicked for me when I learned how the map function worked in Haskell.
This guy is like every lecturer i've ever had rolled into one
This man not only amaze me with his skills, his dry homour cracks me up.
First 40 seconds and I already love this guy..
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. 👍🏻
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
More of these basic concepts with examples from this man please that was brilliant.
Professor Thorsten Altenkirch looks like Dave Grohl and Taylor Hawkins have morphed into 1 person and quit Foo Fighters for Foo(x) Pythons.
LOL yes! He also looks like the guy from the 'give me compliments' music video
Love the accent, love the shirt, love recursion explanation. This video is a pure win situation.
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.
Thanks for sharing one of your superpowers with us, Thor!
Downloaded Anaconda and it throws “GOT NO BUNS” error
Do some squats
@@7027-s6f will that make me a better programmer?
@@Blox117 Worse.
if ( ! social_prospects ) code();
raise AnacondaDontError
Exception handling, bro do one of those
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
1:57 'i'll leave [the robotic arm] as an excercise' *smirk* And they say Germans don't do jokes haha
Those variable names are stellar.
Awesome. I've just added this to stack overflow.
I wish all questions in there had an answer like that!
Muito interessante!.....🤔
@@lpkuchembuck hahahahahahahahaha
Not sure If toxic community
Or very critical of code
I liked the way in which Professor Altenkirch used the toy to write the program. Visualizing things really helps us to program.
Recursion in German is recursion (recursioooon)
You mean recurziooon
It' Rekursion.
This is exactly the type of guy that I would expect to learn recursion from
3:20 why not use fstrings? print(f'Hello {variable}') (or use " if you want)
He may be using an older version of Python, or not yet broken the habit of string formatting.
That said, f-strings are a godsend and one of my favorite recent features.
Then he would have to explain them to non-pythonists, but everyone gets method calls.
@@bytefu Arent fstrings also kinda self explanatory? Since they are so easy to read.
@@xario2007 I would say, str.format() builds on the knowledge that values of parameters listed in a function call are passed into the function (used in majority of programming languages) and a literal string can behave like an object and have methods (only a subset of languages).
fstrings at first sight look like specially marked literal strings; they require the knowledge that the interpreter itself evaluates the string at runtime using variables in the scope.
I liked this video after the first 48 seconds. The way he described recursion as a Super Power. Just take my money.
Unfortunately this video about recursion doesn't mention a video about recursion that mentions a video about recursion that....
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.
:Jupiter.. I think it's also a planet? Something like this."
How did the program know the rule that you cannot put a larger disk on a smaller disk?
Sadly, there is no tail optimized recursion in Python:(
Why so ? It doesn't depends on language right
@UCxfH8O5kzZjtweUpr_w5WIg I'd say almost impossible. Also, it is something not that easy to implement in a dynamic language.
@@overclockinggames2419 It depends on a specific language implementation. CPython simply doesn't do this optimization. Period.
@@SergeMatveenko It has nothing to do with implementation limitations. The problem is keeping track of stack frames, and it just gets messy when debugging. Java does not optimize tail recursion either, for the same reason.
@@TheMysteriousMrM That's exactly the meaning of "depending on the implementation." Easily keeping track of debugging info (e.g. stack trace) is a trade-off you get by not allowing tail-call optimization (or as a subset, tail-call recursion). IMO, Guido is a bit too militant with this decision (there are some ways to keep a decent amount of debugging info with TCO).
Brilliant product placement! Had to order the book!
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).
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.
@@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.
@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.
@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.
I don’t know why I havent seent this before. This solution is *stupidly* elegant. Amazing!
Is the
if x: pass
else: do_something()
construct pythonic?
Alternative would be
if not x: do_something(), right?
Yes. Or just
if n==0: return
and then the rest. Don't even need an else statement there
if *variable* != *otherVariable*:
He is so naturally funny! I'd love for him to be my mentor!
Lucky we saved *all that typing* with single letter variable names. :D
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 cant believe the problem can be solved with that simple code
But I think that the video has been shortened because it does not stress enough importance of trivial cases for recursion. And then there are more types of recursion, of course, which are not mentioned there.
loots of stuff in coding/computer science is like that:
there's a obvious to anyone solution, that is not too hard to implement, but extremely inefficient.
then, there's a completely different solution, probably invented by Euler(or at least some other mathematician), that wasn't even supposed to have anything to do with computers, that solves the problem much more efficiently.
my favorite example is the Fibonacci sequence. in python code:
obvious solution:
def Fibonacci(N):
if n < 1:
return 1
else:
return Fibonacci(N - 1) + Fibonacci(N - 2)
the problem of this solution is that it calculates the lower Fibonacci numbers over and over again, resulting in a lot repetitive computation to calculate result you already knew, and this problem gets worse as N increases, making this algorithm exceedingly slow for any practical use.
but did you know that the Fibonacci sequence can be approximated by (phi^N)/root(5)?
yeah, instead of all this recursion, repeatedly calculating the same values, there's a way to go straight from the index of the number on the sequence to, approximately, the number itself. with some extra code for the rounding/square roots we have:
def round(x: (int, float), r: float = 0.5) -> int:
""" Rounds up if the fractional part of x is greater than r, otherwise down"""
if x - int(x) > r:
return int(x)+1
else:
return int(x)
def root(x, r=2):
""" root function, since i don't like to import just one function"""
return x**(1/r)
""" the number phi ~ 1.618"""
phi = (1 + root(5))/2
def fibo(n: (int, float), rounded: bool = True) -> (int, float):
""" calculate the Nth Fibonacci number using it's approximate exponential, (phi^n) / root(5), then rounding if desired"""
res = (phi**(n))/5**(1/2)
if rounded:
res = round(res)
return res
if you want to be ... scientific about how bad the recursive implementation is(even when using a cache to avoid repeating the same index!), the recursive implementation(with cache!) has time complexity(how longer the program tends to take as N increases) of O(phi^(N)), meaning, it increases exponentially(I.E. super fast -> inefficient algorithm),
meanwhile second implementation has a time complexity of O(1), which means, it doesn't increase even as N becomes larger and larger(not exactly true, due to the fact that as N gets bigger storing it becomes harder for the computer which increases overhead, but the number of operations, which is what the O notation cares about, stays the same)
That's the super power of recursion!
Yeah, recursive solutions are normally simpler. But simpler to us.
You have to avoid recursion when programming, is usually horribly inefficient and has the inherent limit of the stack size.
Fortunately, there's always a way to do it non-recursively.
Marc Gràcia As with all things, there are exceptions to that. For example, the recursive solution for calculating greatest common denominators (developed by Euclid) is actually the most efficient solution.
wow, nice and simple illustration to the super power of recursion
Highness level: Yes.
//N=4 a=A b=B c=C line 1
//N=3 a=A b=C c=B line 2
//N=2 a=A b=B c=C line 3
//N=1 a=A b=C c=B line 4
//Move a to c from line 4 A-B
//End of recursion from line 4, continues back to line 3
//Move a to c from line 3 A-C
//N=1 a=B b=A c=C line 5
//Move a to c from line 5 B-C
//End of recursion from line 5, continues back to line 2
//Move a to c from line 2 A-B
//N=2 a=C b=A c=B line 6
//N=1 a=C b=B c=A line 7
//Move a to c from line 7 C-A
//End of recursion from line 7, continues back to line 6
//Move a to c from line 6 C-B
//N=1 a=A b=C c=B line 8
//Move a to c from line 8 A-B
//End of recursion from line 8, continues back to line 6
//End of recursion from line 6, continues back to line 1
//Move a to c from line 1 A-C
//N=3 a=B b=A c=C line 9
//N=2 a=B b=C c=A line 10
//N=1 a=B b=A c=C line 11
//Move a to c from line 11 B-C
//End of recursion from line 11, continues back to line 10
//Move a to c from line 10 B-A
//N=1 a=C b=B c=A line 12
//Move a to c from line 12 C-A
//End of recursion from line 12, continues back to line 9
//Move a to c from line 9 B-C
//N=2 a=A b=B c=C line 13
//N=1 a=A b=C c=B line 14
//Move a to c from line 14 A-B
//End of recursion from line 14, continues back to line 13
//Move a to c from line 13 A-C
//N=1 a=B b=A c=C line 15
//Move a to c from line 15 B-C
//End of recursion from line 15
//End of recursion
I lost 3 brain cells doing this.
2:40 "you download something called anaconda"
conda is completely optional to run jupyter notebook , just do `pip install jupyter` then do `jupyter notebook` and you are set
I prefer pip over anaconda just because it is easier for me to install requirements.txt using pip. Although I haven't tried anything other than pip3 so far
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).
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.
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.
Please please please do not encourage new programmers to use single-letter variable names!!
Single letter variable names are horrible. You could just as well call your variables Hans or Susi. It tells you nothing about what is in there, or what it's for.
Why call something "f"? Because it stands for "from". Then why not call it "from". Or better yet, call it "fromTower". This way you know exactly what it's for, without having to derive the meaning every single time.
It looks nicer and is faster to type. For simple cases like this I think it's actually a better practice, the function has 4 lines of code, figure out by yourself what the variables mean if you really need to.
@@3snoW_ No, it looks awful, and speed of typing is an irrelevant concern. Please do not write any software ever!
_"Please please please do not encourage new programmers to use single-letter variable names!!""_
Why? It wouldn't really help here and having longer names makes the code really tedious.
What would actually help would be a comment saying what the function does and its type e.g.,
>
-- hanoi n f h t gives list of moves to take stack of size n from f to t via h
hanoi :: Int -> Peg -> Peg -> Peg -> [Move]
hanoi n f h t = ...
fuk outta here, just read the comments
Thanks for the video(s)... I just purchased your book... Looking forward to digging into it.
This guy is the Rick Wakeman of programming... just needs the cape! 😂
This video is brilliant, he's a great teacher!
I tried looking up "recursion" in the dictionary, and it said "see 'recursion'."
I tried looking up "originality" and it said to avoid RUclips comment sections.
Sorry, long day at work.
Quoth the Jargon File: "tail recursion, noun: if you're not sick of it already, see tail recursion"
I forgot about that one .... very nicely explained, thank you.
Never do the mistakes of running this with 20 discs... (for hours now, my computer still writing hundreds/sec of "move disc ... to ...")
Twenty disks should require 1,048,575 moves. Although that is a lot, a computer should be able to print 1 million lines to the console in a fairly short amount of time.
@@coolguy284_2 takes about 10-15 minutes, in my experience.
M=2^n-1
n: number of disqus
M: number of move
So you need 2^20-1 about 1,048,575 move
Have you checked the parameters?
Awesome teaching style 👌
brad pitt is into programming now?
Very easy to understand hanoi with this video ! Thanks !
This was done in BASIC in the 1970s without recursion.
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...
Start at 9:30 and use return instead of else please.
Just brilliant bit of exposition.
I traced the code by hand with some simple cases so I get how it operates now but, I still don't get exactly why this solution should work.
The rules of the towers of Hanoi force discs to always be in order - smallest on top, larger in the bottom. Every function call is moving the largest disc it knows about to a space that has no smaller discs, because it just made a recursive call to move any smaller discs to the third (helper) stack. It finishes by transferring the smaller discs onto the large disc, ensuring that all the smaller discs are on one pillar when the function returns. As long as the deepest call works, and it will because it won't have to move any discs, the whole arrangement of movements will complete the task.
Some call designing a function like this "leap of faith" programming; by divide and conquer, we assume we can complete the task for some smaller problem. We then find a set of smallest needed problems to solve, and address those specifically.
So the solution uses the cases of "one disk less" (n-1) to solve the problem for any amount of disks (n), but how can this work you ask?
In case 0 (base case): we simply don't move, done, nice job.
In case 1: We use the solution for 0 to move 0 disks from A to B (via C), then we move our single disk from A to C, then we move 0 disks from B to C (via A).
In case 2: We use the solution for 1 to move 1 disk from A to B (via C), then we move our single disk from A to C, then we move 1 disk from B to C (via A).
In case 3: We use the solution for 2 to move 2 disks from A to B (via C), then we move our single disk from A to C, then we move 2 disks from B to C (via A).
You can already very clearly see the pattern that arises.
We always start with all disks on A and (B and C) empty, and (that's also important for this solution) with all disks ordered from smallest at the top to biggest at the bottom!
Given such problem (n) we can look at a simpler problem of "one disk less" (n-1) and just "ignore" the biggest disk (1) on the bottom as all other disks are smaller and thereby can move freely onto the bigger one by definition of the problem. Then solve (n-1), move our previously ignored single disk over to the target and now repeat the process for the (n-1) disks.
So how do we solve (n-1)? That's easy, we already did that, didn't we? We know we can move (n-1) disks from A to C (via B) by simplifying the problem to (n-2).
Now that we know we can move (n-1) disks from A to C (via B) we also know we could do the same to move them from A to B (via C), we just switch target and helper this time (or switch accordingly for any desired origin, destination and helper).
Knowing this we can solve for n!
We first simplify the problem and:
We use the solution for (n-1) to move (n-1) disks from A to B (via C), then we move our single disk from A to C, then we move (n-1) disks from B to C (via A).
But that sentence is exactly what I used for cases 0 to 3 isn't it?
The sentence above is also basically already the code (with A = f, B = h, C = t):
"We use the solution for (n-1)" already screams recursion
base case is 0, we don't work with "negative disks" ->
if n == 0:
pass
else
"move (n-1) disks from A to B (via C)" -> hanoi(n-1, f, t, h)
"then we move our single disk from A to C" -> move(f, t)
"then we move (n-1) disks from B to C (via A)" -> hanoi(n-1, h, f, t)
So in essence this simply works because the case of "one disk less", which ultimately boils down to the base case of 0, works.
Example 5:
How do we solve for 5?
We solve for 4, move 1 over, solve for 4 again, done.
But how do we solve for 4?
We solve for 3, move 1 over, solve for 3 again, done.
But how do we solve for 3?
We solve for 2, move 1 over, solve for 2 again, done.
But how do we solve for 2?
We solve for 1, move 1 over, solve for 1 again, done.
But how do we solve for 1?
We solve for 0, move 1 over, solve for 0 again, done.
But how do we solve for 0?
We are already done.
@@victos-vertex Well articulated, much thanks.
This is a really helpful video - what a guy
I always wonder what programmers or professors have against using readable names? If you mean "from" and "to", just call the variables "from" and "to" instead of 'f' and 't'. Please. It makes your application so much more readable and easier to understand.
I agree but 'from' is a keyword in python so that's not the best example ;)
@@sharkinahat Ah, well. I'm not a pythonian. Call it 'source' or whatever. But not just f, t, n, ... That just gets confusing.
When I started programming all variable names were either a single letter or a single letter with a digit - the programming language simply didn't allow more than that (early versions of BASIC). It's hard to break the habit. The professor looks older than me, which means probably spent more years in environments with limited variable names, and the habit is even more ingrained for him.
It might save time on a blackboard. In an editor, not so much, and words are both more distinct and descriptive.
Vielen dank für den Trick. Hatte da nie so drüber nachgedacht.
10:22 how the move(f, t) function even get called when hanoi(n-1, f, t, h) is called before!!?
n gets reduced to 0,
then hanoi(0, f, h, t) gets called. It passes and the method higher in the recursion-chain moves to the next command: move()
Could never imagine the use of recursion except for factorials.
Nice job!
I dont have a lot of examples but its used in sorting algorythms eg. Merge Sort