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 ukposts.info/have/v-deo/qpZnqZxqoYSbw6M.html&t

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

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

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.

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.

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 UKposts. This deserves to be a part of a paid course. Much thanks man!

holy shit this is 3blue1brown but computer science :0

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

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!

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

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.

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!

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

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

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.

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!

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

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.

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!

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

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.

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

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.

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

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.

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

This is beautifully made and clearly illustrated. Thank you!

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

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

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

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

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

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

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!

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.

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

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.

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!

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

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

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

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.

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

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

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.

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

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)

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?

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

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.

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

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

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

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

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

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 ❤

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.

holy shit is this amazing. keep making more!

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

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

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

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

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

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

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

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

19:00 it's like a chirstmas tree

This is the best video talking about recursion on UKposts Thanks man!

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!

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.

what an explanation! you are amazing,fantastic,mind-blowing,fabulus and what not

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

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

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.

Love your video style! Very comprehensive and similar to 3B1B. Absolute G!

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.

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

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

Ooh man those animations really helped. I appreciate it man

One of the best practical way to analyze and code recursive.. life saver :)

>using sum as a function name pain

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

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

Managed to solve the last problem myself before the full video! Using the approach mentioned ofc, very helpful

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

one of the super extra special video which actually taught me something which I can take out with me

Beautiful video and super underrated channel. Thank you!

Thanks for the video man. Really appreciate your time and knowledge on it. Subscribed.

Best video on recursion! Saving this for future reference

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

One of the best video out there for solving recursive problem

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!

Definitely the best tutorial I've ever seen. I only knew how to compute factorial using recursion before this XD

Really good explanation! Thank you a lot man!

The video is really amazing and gives the idea to approach a problem and i love it.

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