5 Simple Steps for Solving Any Recursive Problem

Рет қаралды 1,188,196

4 жыл бұрын

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

Пікірлер: 1 100

@Reducible 3 жыл бұрын

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 kzfaq.info/get/bejne/qMxmqMlkz7TOkqM.html&t

@stv3qbhxjnmmqbw835 3 жыл бұрын

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

@kpw84u2 3 жыл бұрын

Your first statement that it is the hardest topic in computer classes to learn is categorically wrong. And I am proof.

@SimGunther 3 жыл бұрын

@@kpw84u2 Because clearly the hardest topic of all time is reversing linked lists or binary trees LOL

@sammyskye9498 3 жыл бұрын

Ah yes, the 3Blue1Brown of comuter science. Keep up the excellent work!

@miroslavdanilov902 3 жыл бұрын

how can I understand and dont undrestand in the same time?

@stylextv 3 жыл бұрын

I don't know why but this totally feels like a 3blue1brown video.

@matthewe3813 3 жыл бұрын

he uses the same animation software as 3b1b

@mistsu1171 3 жыл бұрын

and he kinda mimics 3b1b's way of speaking, as well

@jogiff 3 жыл бұрын

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

@s.tahsin.r2288 3 жыл бұрын

They are both using Manim, an opensource python library by Grant Sanderson from 3b1b.

@Nulley0 3 жыл бұрын

Ye, but no 60fps :(

@victorscarpes 3 жыл бұрын

How to solve a recursion problem: solve the recursion problem.

@overloader7900 3 жыл бұрын

My mathematical intuition tells me that this is not a recursion

@victorscarpes 3 жыл бұрын

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

@overloader7900 3 жыл бұрын

but func a(){a();} does literally nothing... Does it mean that it is impossible to solve recursion?

@victorscarpes 3 жыл бұрын

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

@ozargaman6148 3 жыл бұрын

Thanks, but how do I solve the recursion problem?

@phentm 3 жыл бұрын

holy shit this is 3blue1brown but computer science :0

@joejohnson974 3 жыл бұрын

i mean 3blue1brown also does computer science. he studied cs as well as math in college

@scrmnthn5233 3 жыл бұрын

@@joejohnson974 but his content is mainly math based, which is what the commentor is refering to

@pipolwes000 3 жыл бұрын

In the description he even thanks 3b1b for providing open-source access to manim, the animation library created by 3b1b

@mazharmumbaiwala7451 3 жыл бұрын

@@pipolwes000 I found this channel out from 3b1b's post itself

@spencerk7187 3 жыл бұрын

@@hybmnzz2658 yes please

@yashsinghal8820 3 жыл бұрын

The animation, explanation, everything about this video is top notch. I am actually surprised this is on KZfaq. This deserves to be a part of a paid course. Much thanks man!

@garychap8384 3 жыл бұрын

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.

@ummara2020 2 жыл бұрын

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😔

@simmerke1111 2 жыл бұрын

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.

@garychap8384 2 жыл бұрын

@@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 !"_

@simmerke1111 2 жыл бұрын

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

@lupsik1 2 жыл бұрын

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.

@palashhoque8739 4 жыл бұрын

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.

@Reducible 4 жыл бұрын

Thank you! More videos on these topics are all in the plan :)

@GlennDaytonIV 3 жыл бұрын

@@Reducible Extremely helpful! Thank you very much. Looking forward to your next videos!

@asshivam8117 Жыл бұрын

kzfaq.info/get/bejne/rst9lrp_xJvVe2g.html This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

@aadityamayankar3407 4 жыл бұрын

This video deserves so much more love!! Thanks Reducible

@SHY-sx8rm 3 жыл бұрын

As a student studying programming.. This is the best lecture ever clearly described and explained recursion. Thank you Reducible!! Liked and subscribed!

@premk191 4 жыл бұрын

This is best video I found on youtube. Keeping making videos like this. Thank You.

@Reducible 4 жыл бұрын

Thank you, I appreciate the kind comment! New videos coming in the near future :)

@chandraprabhat3496 4 жыл бұрын

@@Reducible sir please explain tower of hanoi(TOH) problem in same way i can not relate you idea to solve for TOH problem.

@Reducible 4 жыл бұрын

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

@karanpaul5525 2 жыл бұрын

Bhai mereko kuch samaj nahi aara...😭

@raksalim5860 3 жыл бұрын

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!

@aakangshamazumder2882 Жыл бұрын

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!

@howchen8529 3 жыл бұрын

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.

@heh3312 3 жыл бұрын

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

@asshivam8117 Жыл бұрын

kzfaq.info/get/bejne/rst9lrp_xJvVe2g.html This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

@DZairCuisine 3 жыл бұрын

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.

@Reducible 3 жыл бұрын

Yeah that's a great perspective! Thanks for sharing!

@Green24152 2 жыл бұрын

"we tell the computer what to do but not how to do it." Sounds like a bad idea.

@DZairCuisine 2 жыл бұрын

@@Green24152 really! Why?

@Green24152 2 жыл бұрын

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

@RagingGeekazoid 2 жыл бұрын

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

@elhamnazif 2 жыл бұрын

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.

@manjunadhkandavalli1017 3 жыл бұрын

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

@emreturker4175 3 жыл бұрын

*enlightening music playing in the background with crystal clear explanation of recursive functions* me : 👁️👄👁️

@YuralRock 3 жыл бұрын

6 lines of code for a complex problem, damn this is badass

@esindurmaz4709 3 жыл бұрын

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.

@xuexiaosu 3 жыл бұрын

This is beautifully made and clearly illustrated. Thank you!

@christopherraris8667 3 жыл бұрын

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.

@drivethelightning 2 жыл бұрын

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.

@user-cg2nh5jy5w Жыл бұрын

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.

@weirdbunnydotcom 2 жыл бұрын

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!

@richardrodrigues4960 3 жыл бұрын

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

@clublulu399 3 жыл бұрын

By far one of the best videos I’ve seen on the topic of Recursion. Great stuff.

@hendrixgryspeerdt2085 3 жыл бұрын

This is some high quality content here. I will definitely recommend this to others taking computer science classes.

@nikhil6842 3 жыл бұрын

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

@jacksonwang3974 3 жыл бұрын

I'm literally about to cry rn Thank God for guiding me to this video! This video is beyond magical

@cristianlopez6095 3 жыл бұрын

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!

@chrisjaromin5835 3 жыл бұрын

What a fantastic, simple and beautiful explanation of recursion. I've been looking for this for a long time. Thank you

@irockrock44 3 жыл бұрын

you're genius! one of the best tutorial on recursion!

@sandipchanda6522 3 жыл бұрын

Thank you. Amazing video. This is one of the best explanations I have ever seen in youtube. Keep making more such videos.

@amaarquadri 3 жыл бұрын

Great video! The increase in difficulty was really well done!

@anonymousperson9757 Жыл бұрын

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!

@stephenkolostyak4087 3 жыл бұрын

recursion was pretty straightforward. "talk to yourself in the corner, never leave."

@rishabhdev2890 3 жыл бұрын

Never leave until you reach a base conversation and use it to pop out of stack of conversations

@manuelrubiosanchez 3 жыл бұрын

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

@asshivam8117 Жыл бұрын

kzfaq.info/get/bejne/rst9lrp_xJvVe2g.html This is awesome!! Clear all your doubts about Recursion and master it in just 15 minutes!! Watch now!!

@maheshvshet 3 жыл бұрын

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.

@TheTessatje123 2 жыл бұрын

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!

@patrickmayer9218 Жыл бұрын

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.

@recepcanakdemir1558 7 ай бұрын

Basically induction

@patrickmayer9218 7 ай бұрын

@@recepcanakdemir1558Yes!

@pierce3992 3 жыл бұрын

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

@Reducible 3 жыл бұрын

That is some high praise! Thank you! And yeah, like with anything difficult but worthwhile, it takes some time. Enjoy the process!

@praveen544com 3 жыл бұрын

One of the best tutorials on Recursion which I come across. Thanks very much for the excellent presentation.

@kartikpodugu 7 ай бұрын

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.

@alejrandom6592 Жыл бұрын

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)

@neeyatiajmera869 3 жыл бұрын

This was by far the BEST explanation on recursion I've ever seen. Thank you so much!!!!

@ManojKumar-yt8qd 3 жыл бұрын

it's just outstanding. The way things are made simpler is really appreciable. keep it up buddy.

@niemandisthier3227 Жыл бұрын

this is one of those videos you get from time to time, that marks the next step of your learning journey.

@jayantverma6196 4 жыл бұрын

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.

@Reducible 4 жыл бұрын

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!

@user-wc1sm8cj8s 3 жыл бұрын

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?

@kevinthai6777 3 жыл бұрын

mad lad

@Fakipo 3 жыл бұрын

Sometimes a well rested mind leads to epiphany

@Arielkun14 3 жыл бұрын

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

@anonymous_4276 2 жыл бұрын

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.

@pearz420 2 жыл бұрын

I guess your brain working is a miracle?

@recep36 Жыл бұрын

This is the BEST video I've seen about recursion. Awesome explanation! Thank you so much!

@hugonavakopp 3 жыл бұрын

Great work. I loved the thorough explanation. Many thanks for putting the time and effort into producing this, it is very helpful.

@Dev-zr8si 4 жыл бұрын

holy shit is this amazing. keep making more!

@TheBrotherHolmes 3 жыл бұрын

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!

@Reducible 3 жыл бұрын

Thanks, I appreciate the kind comment!

@catLoverNimga 2 жыл бұрын

Ooh man those animations really helped. I appreciate it man

@tristanlee1171 2 жыл бұрын

That was the most useful video I have every watched. I really love the 3blue1brown vibes. Keep up the good work!

@badwolf8112 3 жыл бұрын

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

@Sarah-re7cg 2 жыл бұрын

These visuals help a lot a lot for people with ADHD, thank you so much

@info662 2 жыл бұрын

I thought I was the only one who struggled with recursion

@HXYZZZ Жыл бұрын

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

@anbesivamkamal 4 жыл бұрын

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.

@kpw84u2 3 жыл бұрын

I loved learning recursion and it wasnt the hardest subject to learn in computers. It actually made the most sense to me.

@sonashubhamvats6317 3 жыл бұрын

wait, this is not recursion, this is magic!!!

@sohelmahmud3394 3 жыл бұрын

Finally I found a video which described the steps for solving recursive problems. Hats off Maestro :D

@tedioushugo 3 жыл бұрын

The BEST recursion explaination I have ever seen. Thank you !!!!!!

@mehrankazeminia8557 3 жыл бұрын

Great Job! Looks like a small mistake (19:35) if (n

@greendog105 Жыл бұрын

yes!

@justingolden21 3 жыл бұрын

19:00 it's like a chirstmas tree

@indianjitsingh8838 3 жыл бұрын

I am currently attending university and these are the exact same examples that were used when we were learning recursion. This video is easier to understand.

@t-distributedkid3825 11 ай бұрын

This is liberating stuff! It's like some mental blocks are being cleared off in my head. This is crazy good! Love you, bro!!!

@VirajChokhany 4 жыл бұрын

Amazingly explained Sir. Please do make a complete playlist for recursive implementation of problems. It will help all of us immensely.

@Reducible 4 жыл бұрын

Thanks for the comment, I have a couple more recursion related ideas on future videos so stay tuned! :)

@DanielDaniel-xz2yp 3 жыл бұрын

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

@usrrrrrrr5677 2 жыл бұрын

this is probably the greatest recursion video i have watched, thank you so much

@veryepicgameplay 3 жыл бұрын

Really good explanation! Thank you a lot man!

@Oscar1618033 3 жыл бұрын

What about going from recursive functions to tail-recursive ones?

@linyerin Жыл бұрын

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.

@sowhardobinatik4348 Жыл бұрын

I face the same problem

@eyeteeee9507 Жыл бұрын

What can you say about it now?

@linyerin Жыл бұрын

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

@cfalk36 3 жыл бұрын

Bravo sir! Great explanations and visuals that make things more intuitive. Appreciate the hard work!

@user-rr7xc9ih3r 5 ай бұрын

this is byfar the best video ive ever watched on any CS topic whatsoever, keep up the good work!!

@nafidhimas2340 2 жыл бұрын

Recursive isn't that bad, I'M that bad

@JonathanMandrake 2 жыл бұрын

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.

@KitagumaIgen Жыл бұрын

FFT

@sidharthraj340 3 жыл бұрын

You really worked hard on animations in this video . Hats off. I was lost in watching animations in later part of the video.

@adrianagaraychavez7330 3 ай бұрын

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 ❤

@CST1992 3 жыл бұрын

When I saw the thumbnail, I thought we were going to design Tetris blocks :(

@GanerRL 3 жыл бұрын

>using sum as a function name pain

@michil.1192 3 жыл бұрын

what name would you use

@GanerRL 3 жыл бұрын

@@michil.1192 something that isnt a function already

@MrGryph78 3 жыл бұрын

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

@emanonvolmodaoist686 3 жыл бұрын

@@MrGryph78 Can't agree more.

@EchidnaFolder Жыл бұрын

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

@pruthvipatel8720 2 жыл бұрын

Best video on recursion! Saving this for future reference

@leepakshiyadav1643 3 жыл бұрын

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

@user-nq4nt6ex2b 3 жыл бұрын

Commenting to bookmark it :)

@leepakshiyadav1643 3 жыл бұрын

@@user-nq4nt6ex2b great 😂

@joeshmoe8660 3 жыл бұрын

Should I be watching this if I'm a high-school sophomore? 🤔

@CalamityInAction 3 жыл бұрын

I’m even younger, so don’t worry :)

@elijahbuchanan2368 3 жыл бұрын

You are never too young to be great.

@oleksiishekhovtsov1564 3 жыл бұрын

Yes! You'll thank yourself when you get to college

@forgodalone7416 3 жыл бұрын

Absolutely!

@vilmafernandes5803 3 жыл бұрын

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

@omkulkarni637 3 жыл бұрын

Found this channel through 3b1b and I cannot be happier

@youtubezcy 3 жыл бұрын

Beautiful video and super underrated channel. Thank you!

@ksalarang 2 жыл бұрын

This is such a great explanation! Keep it up!

@wemake4u444 3 жыл бұрын

Your videos are amazing, it's very easy to understand these complicated concepts with illustrations. Thanx a lot.

@amandeep000786 3 жыл бұрын

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 🍻