5 Simple Steps for Solving Any Recursive Problem
Vložit
- čas přidán 10. 12. 2019
- In this video, we take a look at one of the more challenging computer science concepts: Recursion. We introduce 5 simple steps to help you solve challenging recursive problems and show you 3 specific examples, each progressively more difficult than the last.
Support: / reducible
This video wouldn't be possible without the open source manim library created by 3blue1brown: github.com/3b1b/manim
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music:
October by Kai Engel freemusicarchive.org/music/Ka...
November by Kai Engel
freemusicarchive.org/music/Ka...
Cobweb Morning by Kai Engel
freemusicarchive.org/music/Ka...
For those of you who enjoyed this video on recursion, here's a new video on the famous Towers of Hanoi problem I made related to the topic. This is a more advanced recursive problem and I try to approach it from a different perspective with some additional helpful tips. Check it out at czcams.com/video/rf6uf3jNjbo/video.html&t
I don't know about the others, but tower of Hanoi is one the the easiest recursive problem I've ever solved. Maybe that day was my day...
It's simple logic.
Like if you want put n+1 disks to leftmost, first put n disks to middle, then put largest plate on leftmost, then put n from middle to leftmost. As simple as that....
Your first statement that it is the hardest topic in computer classes to learn is categorically wrong. And I am proof.
@@kpw84u2 Because clearly the hardest topic of all time is reversing linked lists or binary trees LOL
Ah yes, the 3Blue1Brown of comuter science. Keep up the excellent work!
how can I understand and dont undrestand in the same time?
First, I love this video...
I get that this is about HOW to do recursion. But nobody ever addresses the question of WHY/WHEN to do recursion.
For example. Every one of these tasks can be solved without recursion or iteration. Recursion is literally the slowest most cumbersome method. The problem is this: If you focus on Recursion as the _"cool new tool"_ for your toolbox - then every time you see a problem that can be broken into sub-problems, you'll use recursion!
Nobody teaches you to recognise when it's the _"right"_ tool : /
Here's a default: Recursion is *almost always* the wrong tool for the job! ... it's almost a tool of last resort! Certainly it's not the right tool for most of the recursion examples you'll see online.
I sense a rage storm brewing ... but, don't sh-tpost me just yet...
Now, I have to be careful. I'm really not trying to dump on anyone here... recursion is a very cool paradigm to understand, definitely. But, like any tool... you need to know when it's use is appropriate.
*How bad can it be? It gets the job done...*
To answer that, let me introduce you to Ted. Ted is a builder, and he's come to work on your house. Ted has all the latest tools at his disposal, but he's never been shown when/why to use them ... let's follow Ted around...
Hanging some picture frames? No problem... Nails go in holes... So, Ted drills some holes and puts nails in them. Job done!
Putting up a heavy bookshelf? No problem ... Ted hammers a few screws into the wall. Perfect!
Need a new roof??? ... Well, Ted realised very early in his career, that the ONLY way to build roofs is to start with the foundations and work upwards... it's literally the only way that makes sense. So, he bulldozes the house and starts again : )
Ted, to be fair, is a truly terrible builder : /
Software Development is an Engineering Discipline it's not just the How that's important... anyone can learn the How. Even Ted. It's the Why and the When... and it seems like nobody is teaching that, mainly because... well, it gets complicated : /
... It also offends anyone who's just cracked recursion, and is feeling (quite rightly) very proud of themselves.
*Take the first example...* (I know, I know... again, hear me out)
It certainly _"looks"_ VERY recursive... and that's the danger. When you've just got a shiny new hammer, everything around you looks like a nail! But it's obviously a great example of When NOT to do recursion. It's a great teaching prop - but an awful candidate.
So, if you're going to look at the problem long enough to understand its recursive nature ... you should probably also see that it's almost half of a square. We all know a square can be formed by two triangles! We notice that we can put two identical triangle-ish shapes together and they *almost* make a square... but it's shape is a little off :
The shape is (n) by (n+1) ... or (n+1) by (n) ... So, it's slightly rectangular! One side is exactly 1 larger than the other.
And if a rectangle is Width * Height .... Then our triangle MUST be (Width * Height) / 2
The solution is : N * (N+1) / 2 ... nothing fancy. We just had to ignore the shiny recursive pattern in front of our eyes : )))
But you all know that (hopefully), so why am I mentioning it?
*Before you all get mad at me...*
Yes... I know the first example is just to teach recursion in a simple way. I do 'get' that! ... Realise, that I'm just using it as an obvious example of how a pattern that looks VERY recursive isn't always a good candidate. Unfortunately, it usually isn't so obvious!
Remember: If you're looking at a problem through _"recursive glasses"_ ... it WILL soon look recursive ; )
Even worse, many people around you will congratulate you on choosing a GREAT tool ... it's just not the RIGHT tool: /
*So, learn recursion. But...*
- Recognise that recursion is awfully restrictive for a hundred reasons you probably won't fully appreciate till later.
- Recursion is *almost always* the wrong tool for the job !!! Consider it a red flag, and think a little more first.
- Perversely, it also happens to be the thing they're prompting you to demonstrate in a job interview : O
And be aware that *every problem given here,* has a nice neat fixed-time expression ... in fact, it's hard to find a _"recursion example"_ that doesn't have a linear or iterative expression.
Now... I'm an _(admittedly grumpy)_ old ASM coder, but here's some facts that might shock you...
*The Josephus Problem :* It looks recursive... but is solvable in 3 CPU Opcodes. Literally, the whole compiled code takes less space than it takes to store the word "Josephus", and it has no loops, uses no memory, makes no calls and uses no stack! It isn't any more complex in a high level language either ... just nicer to read.
*The Towers of Hanoi :* ... Wow, now that MUST be recursive, right ??? I mean... look at it go! Now, I know when I say this, a whole bunch of people will get salty... but the solution is only ONE opcode! Just a few bytes! That one opcode can calculate any 'move' of the solution, independently of the others ... so, you can just call it in a loop if you want the full solution. The C/C++ code for it is just a couple of short lines! I doubt the python is much bigger _(I don't use Python)_
*Binary Count Problems :* Similar to the "Towers Of Hanoi problem", any problem which is tied to a binary sequence will look VERY recursive. This is because a binary count looks very recursive... Learn to spot when apparent recursion is just following a binary sequence! It happens so often you'll start seeing it everywhere! It can make the difference between a simple counter (iterative) solution ... and a very expensive, inflexible and utterly pointless recursive solution.
*The Steps Problem :* and any recursive-looking problem that requires you to use the Fibonacci sequence. Fibonacci looks VERY recursive... and the solution to avoiding recursion isn't exactly obvious ... but Fibonacci turns up SO often in algorithms that you should probably be aware that you can calculate any Fibonacci number N, *without* solving ANY previous Fibonacci number... so, in production code, you'd NEVER use a recursive solution !
If interested, look up "Fibonacci Dijkstra" for a massive speed-up ... and "Fibonacci Benet" for a clever recursion-avoiding trick to memorise and put in your mental toolbox : )
And, don't feel bad... really! It takes experience to start spotting alternatives to recursion... and sometimes (rarely) recursion really IS the right solution... although, even then, you have much nicer options for implementing it that will become apparent with other tools, like Queues and Thread pools.
*So, having said all that...*
Don't get me wrong... if you're trying to ace an interview, and the problem looks recursive. They're *probably* hoping you'll show them a recursive solution *and* be able to explain it to them. So, for GODS SAKE LEARN RECURSION!
This video is GREAT for that... truly! One of the best.
But, afterwards, if you really want to stand out to the interviewer ... mention it! Say _"Of course, I'm not entirely sure it's a recursive problem... I think it can be solved in linear time"_ ... see if they just say _"No, it's fine, you've done what we wanted"_ ... or, if they say _"Really? Explain..."_
Then, you can wow them with ... well, not just the size of your toolbox : )
... but your deeper understanding of the Whys and Whens... and, importantly, the When Nots ; )
*In conclusion*
Stick with it! Practice! Learn it inside out... till you're ready to explain it to an interviewer! Then be prepared to spend the rest of your career avoiding it - and I mean _"like a crazy Ex girlfriend/boyfriend"_ level of avoiding ; ))))
Trust me, it's usually the right instinct.
Don't be Ted the Builder.
Woww!!! I'll go and like your comment from my other 3-4 accounts. btw I'm a CS student (2nd yr) still figuring out a lot of stuff but clueless😔
There's indeed rarely a proper usecase for recursion. Most developers won't ever see one.
Sometimes you can get creative with caches in recursion making it a somewhat proper solution. But it doesn't make sense to use it for 99% of problems.
@@simmerke1111 Pet peeve of mine : )
Recursion is not just evil, it's always the wrong answer!
Why?
Well. You can't easily suspend it to disk. You can't properly rebalance the load across cores. You can't prune the call queue based on new info. You can't queue more promising paths first and less likely paths last. You are committed to the call queue completion, so you have to unwind before exiting. It's damned slow.
TCO (tail-call- optimised) languages still don't fix the problem. In fact, they create some design issues.
Not to mention that the stack is a precious resource you're clobbering in place of cheap heap. And that is just terrible design!!!
Even if you think that you have the stack length, how much of that stack is actually free depends entirely on your calling program. Besides which, this stackspace dependency makes code less portable and increases the platform minimums.
And it's utterly unnecessary - ALWAYS!
The solution :
Consider that work units of data can be held in a FILO/FIFO, a DEQue or PQueue and processed by a thread pool or even a machine pool. This can handle anything a call-recursive solution can AND is considerably faster, even on a single thread. And the code is simpler to write, understand, test, verify and maintain!
This structured work queue can be paused, saved, restored, farmed out across machines, be processed by threads and split across cores. It can be pruned or reordered. It can blend depth-first and breadth-first strategies seamlessly... it's simpler, thread-capable and doesn't clobber the stack.
What's not to like?
There is literally NO good reason to use call recursion. And that's when a problem IS actually recursive.
Most supposedly "recursive" problems are NOT actually recursive at all - they just "look it" when you've not actually bothered to properly analyse the problem.
Take the 'Josephus' problem, which can be reduced to 3 ASM instructions and NO iteration...
Or, the Towers of Hanoi problem which looks absolutely recursive - yet resolves to a single opcode!!!! Just ONE opcode!!!! It looks recursive because it's a simple binary count.
Indeed, most supposedly "recursive" problems do NOT, in fact, require recursive solvers at all... and, those few that do should never use any actual call recursion outside of a classroom environment.
But the main problem with recursion is that it's sold as a powerful technique... and, when you have a favourite hammer - everything looks like a nail : (
Every lesson on code recursion should end with the words : _"So, now you know what recursive code is. And... if I EVER see any of you using it outside of this room, I will personally beat you to death with your own laptop !"_
@@garychap8384 While I agree that recursion is never the proper solution, in very, VERY, few cases it's the best solution found/possible.
It's a nice thing to understand, being able to find base cases is pretty important and will be useful.
That aside;
There are some solutions that will require recursive backtracking as of now. Something like solving a very hard sudoku puzzle for example. While easier ones can likely be done faster otherwise, sometimes there's no other way than to try a solution and go back if it turns out to be wrong.
Recursion is basically only a tool when no better solution has been discovered/developed. And should be treated as such. Code that must be replaced once the opportunity is there.
I only learned about recursion solving sudoku puzzles in class and we were told to optimize it to use as few recursive calls as possible.
Hope there aren't too many students who fall into the pitfall that is recursion. I know a lot of people fail interviews at my firm because they're grasping for it when a hashmap will do the trick.
In non performance critical tasks often recursion will turn out to be the most intuitive and simple solution and i think thats where it shines, it makes some hard problems really easy for the dev.
All its cons dont matter when no one cares because of computational overhead and the employer just wants a simple readable solution. And sometimes recursion gives just that.
I don't know why but this totally feels like a 3blue1brown video.
he uses the same animation software as 3b1b
and he kinda mimics 3b1b's way of speaking, as well
@@mistsu1171 I think that that’s just enunciating everything really hard. But yeah, after a minute of this video I was like, “is this channel affiliated with 3b1b?”
They are both using Manim, an opensource python library by Grant Sanderson from 3b1b.
Ye, but no 60fps :(
How to solve a recursion problem: solve the recursion problem.
My mathematical intuition tells me that this is not a recursion
@@overloader7900 recursion is defined as something that is defined in terms of itself. Like if i define the following function f(t) = f(t - 1) × f(t - 2). I could define another function in the following way, g(t) = g(t). This isn't helpful at all, but it's a function defined in terms of itself.
but func a(){a();} does literally nothing... Does it mean that it is impossible to solve recursion?
@@overloader7900 it's not that it does nothing, is just that we don't have enough information to know what it does. And just because this specific case of recursion isn't solvable, doesn't mean that every recursion problem isn't as well. It's like saying that the equation x = x + 1 doesn't have a solution and then concluding that no equation has solutions.
Thanks, but how do I solve the recursion problem?
One of the best tutorial of recursion i have even seen. Keep Making more video tutorials based of Recursion, Permutation, Combination, graph & tree. Finally Thank You.
Thank you! More videos on these topics are all in the plan :)
@@Reducible Extremely helpful! Thank you very much. Looking forward to your next videos!
czcams.com/video/xeMcWN_5qK4/video.html
This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!!
Watch now!!
This video deserves so much more love!! Thanks Reducible
The animation, explanation, everything about this video is top notch. I am actually surprised this is on CZcams. This deserves to be a part of a paid course. Much thanks man!
The 5 steps:
1. Find the simplest case (base case)
2. Play around with examples and visualize.
3. Relate the harder cases to the simpler cases.
4. Generalize pattern.
5. Combine recursive pattern with base case using code.
Basically induction
@@recepcanakdemir1558Yes!
This is an amazingly underrated video and explains the mental framework for recursion in an excellent manner. I'm really surprised that this hasn't gotten more views! subbed, and I'm definitely sharing this with everyone I know! Thanks for the excellent video :)
czcams.com/video/xeMcWN_5qK4/video.html
This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!!
Watch now!!
This is best video I found on youtube. Keeping making videos like this. Thank You.
Thank you, I appreciate the kind comment! New videos coming in the near future :)
@@Reducible sir please explain tower of hanoi(TOH) problem in same way i can not relate you idea to solve for TOH problem.
@@chandraprabhat3496 Next video is going to be on Towers of Hanoi! Your comment gave me the idea, so thank you! Stay tuned for that video!
Bhai mereko kuch samaj nahi aara...😭
I always tell my students in recursivity we break an important rule. It's one of the problems where we tell the computer what to do but not how to do it. You teach the computer how to solve the base cases and give it the formula of the general case.
Yeah that's a great perspective! Thanks for sharing!
"we tell the computer what to do but not how to do it."
Sounds like a bad idea.
@@Green24152 really! Why?
@@DZairCuisine Wasn't saying you were bad, just that telling a computer/A.I. what to do, but not how, usually results in the entire universe becoming paperclips.
@@Green24152 Given that most of the people who write compilers know more about programming than the average application-level dev, I don't see any problem with it. Logic languages like Prolog go even further: All you have to do is specify the logical structure of the problem; the compiler will write all of the imperative-level code for you. Not to mention SQL, which does that for databases. They're called 4GLs (fourth-generation languages).
I don't usually leave comments, but this was an amazing video. I'm really starting to understand the recursive framework because of this video. Thank you so much!
As a student studying programming.. This is the best lecture ever clearly described and explained recursion. Thank you Reducible!! Liked and subscribed!
holy shit this is 3blue1brown but computer science :0
i mean 3blue1brown also does computer science. he studied cs as well as math in college
@@joejohnson974 but his content is mainly math based, which is what the commentor is refering to
In the description he even thanks 3b1b for providing open-source access to manim, the animation library created by 3b1b
@@pipolwes000 I found this channel out from 3b1b's post itself
@@hybmnzz2658 yes please
Great Video buddy!Your video helped me realise the strong correlation between maths and CS.I am trying to figure out a solution for my problem for the last three years and your video gave me the exact direction to proceed.Please continue to make videos like these
This has such an incredible professional and clean level of explanation. I can't believe you have only 2.88k subs. I'm joining
Thanks for the video!
*enlightening music playing in the background with crystal clear explanation of recursive functions*
me : 👁️👄👁️
Liked, subscribed and shared.
Even my friends asked me to thank you for such a fabulous video.
Had been struggling with recursion for quite some time.
Most of the tutorials focus more on code rather than concepts.
With Love from India
This is an awesome video on recursion, I used to wonder why we need recursion, but seeing how simple the code is makes me appreciate the beauty of it.
Thank you! My university never really taught me what to think about when doing these recursion problems. Now I have a path I can follow. You are the best.
First time in my life I experience flow state during study. I was so immerge in learning even I forgot my snacks. Thank You so much man!!! Love you always! Be Happy.
Loved the video!
Keep creating content like this one.
Also, I am sure someone have thought of a more "mathematical" solution for the second problem (#paths from A to B), but here I go:
1) instead of thinking in "board" terms (M x N grid), think of the possibilities for moving (right, right, down, down, ...)
2) the number of "down"s is M - 1, and the number of "right"s is N - 1
3) for example, in a 2 x 2 grid, all the solutions are (right, down) and (down, right)
4) for example, in a 3 x 2 grid, (right, right, down), (right, down, right), (down, right, right)
5) therefore, the number of paths of a M x N grid is the number of permutations with two types of repeated elements (down, right), that is, factorial(M - 1 + N - 1)/(factorial(M - 1) * factorial(N - 1))
By far one of the best videos I’ve seen on the topic of Recursion. Great stuff.
Seriously the best video on the topic. It took me a long time to think and work through it, but so worth it. Thank you Reducible!
I had been struggling ever since I first came across recursion because I just couldn't visualize it which made it so difficult for me to understand it. Wherever I looked. they had the same kind of explanation for recursion and it just wasn't enough. Just recently I came across this channel while studying Towers of Hanoi and I loved that explanation. So I wanted to see if you had a video on recursion and after so many years of struggling with the topic, I have finally found a satisfactory explanation. Thanks a lot!
Thank you. Amazing video. This is one of the best explanations I have ever seen in youtube. Keep making more such videos.
I have referred to several videos, but this one is awesome. I am subscribing to this and I am recommending this to others in my circle. Thank you very much for helping with simple steps to understand and implement recursion.
Great video! I love the style of animations and the way you present your content! I almost thought it was a 3Blue1Brown video for a second. Keep up the good work!
Glad to see someone has used the sum of the first n non-negative integers instead of the factorial. It's much clearer because you can visualize the problem easily and from there find the recursive rule/case. This problem is especially interesting because you can also use instances of half the size (n/2) to build recursive solutions. I talk about this and many more problems in a book ("Introduction to Recursive Programming") that focuses exclusively on recursion, and also use similar steps as the ones mentioned in the video. Very nice video!!
czcams.com/video/xeMcWN_5qK4/video.html
This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!!
Watch now!!
I'm literally about to cry rn Thank God for guiding me to this video! This video is beyond magical
What a fantastic, simple and beautiful explanation of recursion. I've been looking for this for a long time. Thank you
I have been struggling to understand many things until I have seen this effort. Great effort, great editing. I just wanna say a big big thank you.
6 lines of code for a complex problem, damn this is badass
I completed the sololearn course and still had no idea what I was doing till you showed step 3 and 4. This is the kind of like "engineering" that I often lack. From now on if anyone has a recursion question I'm going to refer them to this. I was starting to think I had reached a mental wall and had exhausted my intelligence. Thank you.
That was the most useful video I have every watched. I really love the 3blue1brown vibes. Keep up the good work!
it's just outstanding. The way things are made simpler is really appreciable. keep it up buddy.
recursion was pretty straightforward. "talk to yourself in the corner, never leave."
Never leave until you reach a base conversation and use it to pop out of stack of conversations
thank you for these videos. i cant believe you don't have more views/subscribers for the level of quality work you're putting into these visualizations. its like a combination of Zach Star and 3blue1brown. im still struggling with recursion but ill keep practicing and trying to apply these steps
That is some high praise! Thank you! And yeah, like with anything difficult but worthwhile, it takes some time. Enjoy the process!
Must watch for everybody who wants to solve any problem using recursion.
It is not easy to make it easy for others, but you did it.
Really appreciate your effort.
Was really struggling on this recursion part in my data structure course many videos i have watch but they just show you the code in java and expect us to figure it out thank you from my deepest heart may god bless instructors like you.
you're genius! one of the best tutorial on recursion!
Great Explanation.
I didn't understand it at first, then, I took a rest, and for some other reason, I went back here again, and what a miracle. I just understood the concept in no time. How could that be?
mad lad
Sometimes a well rested mind leads to epiphany
There's actually an explanation for that. Your mind has a thread running on the background. When you stop thinking about a problem that thread takes it and processes it. If you want to know more, Coursera's Learning How to Learn explains that (it doesn't call it thread though).
As someone has mentioned, when we really think deeply about something yet still don't get it and take a rest, a part of our brain is still fixated on that topic. So when we return back, we may have the answer to it.
I guess your brain working is a miracle?
Hi Reducible, Thanks for making this video. Many videos work out one specific problem, whilst you give a general approach to solving many (recursive) problems!
Thanks this putting this together. wonderfully explained how to think into recursion problems. Partitions problem and animations used was really great and after this video never have to think into how others arrived at formula to solve similar problems. Kudos for wonderful work !!
It's interesting to see the relation of the second problem to Pascal's triangle. If you rotate your rectangle so your starting point is at the top, then every path is a series of decisions of going either left or right (always downwards). You can see that, just as in pascal'´s triangle, every case can be calculated by adding the two cases above it. The mathematical solution is just choose(n+m-2, n-1)
This was such a hard topic for me and the way you taught this really hard topic was amazing. I just subscribed to your channel. Please upload more videos.
That's the goal! I'm happy to hear that this video was helpful and thank you for subscribing! More videos are coming in the near future!
This is beautifully made and clearly illustrated. Thank you!
This is the BEST video I've seen about recursion. Awesome explanation! Thank you so much!
I'm taking an algorithm course on "LinkedIn Learning" and the teacher vaguely skims over this and only confused me. Then watching your video made things just click and felt refreshing like a nice glass of water! Thank you so much for taking the time to make this amazing video!
Thanks, I appreciate the kind comment!
This was by far the BEST explanation on recursion I've ever seen. Thank you so much!!!!
Great video! The increase in difficulty was really well done!
Thank you:)
I love this video. You have given a different perspective for tackling recursive problems. Keep up the excellent work!!! I've already subscribed to your channel.
Thanks for the video. The tips are good but I was confused by seemingly implicit restrictions of some of the problems you used. in 14:17 , there are implicit rules for the problem that werent explicitly stated, like in that problem it seems like the order doesn't matter, but if it did you could have every symmetric solutions (for n=3 and m=2, making the first item in the left partition and the other 2 in the right partition. There were implicit rule/s in the pervious problem/s too (like, you can't move in the grind in every which way, even when you take into account beginning at the top left and ending in the bottom right, there are ways you could move through the grid to get there which you didnt specify),
holy shit is this amazing. keep making more!
One of the best tutorials on Recursion which I come across. Thanks very much for the excellent presentation.
this is byfar the best video ive ever watched on any CS topic whatsoever, keep up the good work!!
These visuals help a lot a lot for people with ADHD, thank you so much
I thought I was the only one who struggled with recursion
Great Job!
Looks like a small mistake (19:35)
if (n
yes!
This is one of the greatest videos I've ever seen not only about recursion but programming in general. I loved it, and it was more than helpful. Thank you so much for making this brilliant content free online for everyone, it means more than you can imagine ❤
Great work. I loved the thorough explanation.
Many thanks for putting the time and effort into producing this, it is very helpful.
19:00 it's like a chirstmas tree
wait, this is not recursion, this is magic!!!
This is liberating stuff!
It's like some mental blocks are being cleared off in my head. This is crazy good!
Love you, bro!!!
This is some high quality content here. I will definitely recommend this to others taking computer science classes.
I loved learning recursion and it wasnt the hardest subject to learn in computers. It actually made the most sense to me.
Amazingly explained Sir. Please do make a complete playlist for recursive implementation of problems.
It will help all of us immensely.
Thanks for the comment, I have a couple more recursion related ideas on future videos so stay tuned! :)
How easy and intuitive this video is! Those steps really helped me to understand recursion better and to apply in Dynamic Programming top down approach. For me, step 2 & 3 takes time, to find the pattern and how one case relates to another.
Overall, the smooth animation and explanation really made this video one of my favourite.
Ooh man those animations really helped.
I appreciate it man
What about going from recursive functions to tail-recursive ones?
I think one reason that recursion is hard for beginners is that it is difficult to debug. When I had difficulty understanding an algorithm, I would go step by step to learn how it works. For recursion, I find it really hard to do similar work to it.
I face the same problem
What can you say about it now?
@@eyeteeee9507 You mean how I solve recursion problems now? I memorized multiple templates to solve them. There are not many different types of recursion problems out there and many recursion problems share the same core techniques. This works enough for me, but still, I don't think I fully understand it.
Every other recursion tutorial only uses factorial or fibonacci as examples, but I love how you use more complex examples with amazing visual animation. Thank you so much for this video, I think I finally have a firm grasp on recursive problems!
You really worked hard on animations in this video . Hats off. I was lost in watching animations in later part of the video.
This was great but it also should be noted that recursive functions that always return the same value for the same input should ALWAYS use a *memoize decorator*
It can make even the most inefficient recursive function to run in 1% of the time
When I saw the thumbnail, I thought we were going to design Tetris blocks :(
This is the best video talking about recursion on CZcams
Thanks man!
Bravo sir! Great explanations and visuals that make things more intuitive. Appreciate the hard work!
The thing is that with enough mathematical knowledge, almost all of these recursion problems can be coded in a more efficient way. Either by way of a loop, or by finding a closed formula. If you car either about runtime or want to use big numbers, recursion is the worst way of implementing it other than doing it wrong. It can be helpful for finding a closed formula, and under time crunch, it can be the only way to get it work, but if you have the time, try to find another way of doing it.
FFT
Recursive isn't that bad, I'M that bad
this is probably the greatest recursion video i have watched, thank you so much
The BEST recursion explaination I have ever seen. Thank you !!!!!!
>using sum as a function name
pain
what name would you use
@@michil.1192 something that isnt a function already
@@GanerRL what is in a particular namespace already is a specific language/environment thing, using a generic name like sum in pseudo-code like as done here, isn't an issue, don't be such a pedant.
@@MrGryph78 Can't agree more.
Steps covered for solving recursion:
1) What's the simplest possible input? (Base case)
2) Play around with some examples and visualize
3) Relate larger examples with smaller examples
4) Generalize the pattern
5) Write code by combing base case and recursive pattern
Commenting to bookmark it :)
@@user-nq4nt6ex2b great 😂
Your videos are amazing, it's very easy to understand these complicated concepts with illustrations. Thanx a lot.
Thanks for the video man. Really appreciate your time and knowledge on it. Subscribed.
Should I be watching this if I'm a high-school sophomore? 🤔
I’m even younger, so don’t worry :)
You are never too young to be great.
Yes! You'll thank yourself when you get to college
Absolutely!
Dude, I'm 12 and I know very little python, quit it and started c++ on my sister's advice and plan on relearning everything from start because I didn't practice coding enouhg
Love your video style! Very comprehensive and similar to 3B1B. Absolute G!
Beautiful video and super underrated channel. Thank you!
Managed to solve the last problem myself before the full video! Using the approach mentioned ofc, very helpful
One of the best practical way to analyze and code recursive.. life saver :)
How do you only have
thank you very much, I'm learning cs50 and strugling at recursion for 2 days, and this video help me to understand the concept after watching the first 5 mins. Nice vizualization!
one of the super extra special video which actually taught me something which I can take out with me
I didn't understand this concept in my lecture but it took you 5 minutes to explain it simply in an easy to understand way. thank you so much
Finally I found a video which described the steps for solving recursive problems. Hats off Maestro :D
this is one of those videos you get from time to time, that marks the next step of your learning journey.
Thanks for this video, great illustration and easy to understand
Haven't seen or heard better explanation than this. My search keyword was "i am not able to think recursively". Happy that i ended up here. Cheers to you 🍻
One of the best video out there for solving recursive problem
really amazing video and content. The animations helped a lot and made it even further interesting
The hardest part yet is finding the pattern and generalizing, but these examples were helpful in stablishing the mindset. Thank you for this video❤