Recursion (Think Like a Programmer)

[@vantonspraul]

If you liked this video, be sure to check out my other videos about recursion: Divide and Conquer: kzbin.info/www/bejne/Z2K5aHyhZa51frc Dynamic Programming: kzbin.info/www/bejne/n6fCqnugotCpaqs The Peg Puzzle: kzbin.info/www/bejne/j5mVqoiqhbV7qqc

[@ahmedsohail9855]

hey provide your book free for people like me as have no proper sources

[@techsavvy1457]

Youth Inititiative It is for free.

[@abhilashajha8822]

I have been your fan ever since I read your book. It was such a great beginning for someone trying to learn to programme on her own.

[@vantonspraul]

Thanks for the kind words. Glad you liked it!

[@ShrestaBS]

Finally someone who can teach recurrence without Fibonacci!! Good video 👍

[@xxMpEGxx]

Amen xD

[@cswaale4498]

Yess bro

[@rameshreddibathuni]

Exactly!!

[@ranjeet5806]

hahaha

[@kamleshkumarsahu4699]

🤣🤣🤣best

[@azngiant]

OMG, I was watching other recursion videos and still didn't get it until I saw yours. I thought the moment you replaced the dispatcher method to call itself without changing anything was magical! Biggest epiphany I ever experienced. You just got yourself a subscriber. I'll be watching your other videos. THANK YOU!

[@vantonspraul]

Hey, that's great to hear! This idea has really helped a lot of my students, although I think it is most appreciated by those who, like you, were frustrated by other explanations first.

[@vantonspraul]

Thanks, Alek. I agree, problem solving is often the missing ingredient when programming is taught.

[@yoshuadiaz514]

Your video it`s amazing, I tried to understand recursion before without results, but, with your approach, I gain confidence and I tried with the Fibonacci and Factorial problems by myself with your approach (and without other guides) and I solved by myself without consulting stack overflow ! Thanks a lot! I bought your book! You are the man (and Batman in the night for sure)!!! Cheers from México!

[@vantonspraul]

Wow! Thank you so much! You sound like you are heading in the right direction for sure. There's nothing like the feeling a solving a programming problem on your own.

[@igniteyourdesire]

I wish i had your videos 11 years ago. I would have learned programming so much better. Thank you. I was told in college after I asked how you know what to do with problems. They told me you either understand it, or you dont, and since I didn't, I gave up.

[@vantonspraul]

I didn't mean to suggest that recursion should be forced on any situation where it doesn't fit. I just meant that when learning this particular technique of recursive problem solving, I would start with applying it to situations you already can solve with iteration.

[@mainaofficial8398]

Nice thx sir

[@mamdouhwaleed9514]

I really wish I had found this earlier, I have already been struggling with Recursion for a while, thanks for making this whole series, my life is way easier now

[@solstice9339]

Im in literal shock right now. I'm trying your method out any recursive problem I can think of and it keeps working. It feels like this is too good to be true..

[@johnneiberger7311]

I'm so glad I found this video. I tried to learn clojure a couple of years ago and have been trying to learn Erlang off and on this past year. In both cases, I struggle with how to think recursively. It's so foreign to me that my brain kind of locks up with any recursive problem more complicated than factorials or fibonacci sequences. I even watched a video on dynamic programming, and while the examples made perfect sense in hindsight, I never would have come up with those approaches on my own.

[@tg8iq954]

I have been stuck on the topic of recursion for several days, and now it has finally clicked.

[@黎銘-s9n]

This explanation of recursion is something like the bullet of a sniper that hits the target as expected. All the secret is trust, trust the result of recursive call. It reminds me of learning swimming. People can have confidence in the coach and people around that they are 100% safe in the pool. The actual steps of watching several problems solved successfully both in looping and recursion build the confidence. It's also something like building a skyscraper from the top, which is truly terrifying.

[@vantonspraul]

Those are good analogies.

[@NeelSandellISAWESOME]

The way I think of recursion is that I have a very long rectangle. Everytime I make a function call I am taking a small bite out of that rectangle. I eventually get to my base case and return a certain value.

[@thesuperiorman8342]

I'm so glad I clicked on this video. I understood the concept of recursion but I struggled to write it in code. Your approach of converting an iterative solution to a recursive one gave me the key to unlock this otherwise difficult problem. Thank you so much.

[@parasarora5869]

finally i get to know the big idea and baby steps to take while learning recursion. all thanks to you sir. 😄

[@parasarora5869]

sir...i just now solved my first ever recursive problem by myself. i am so happy. i solved the maxVal problem without even looking at your solution. i am so thankful to you. ♥

[@chenzoe8]

Totally fall in love with the book. Thanks so much. I am now even able to write recursion function on the binary search tree. Before reading the book, I can hardly understand the factor function.

[@vantonspraul]

That's great! Glad my book was so helpful. Recursion can be pretty fun to play with once you get the hang of it.

[@varun9836]

True. I am getting this feeling after going through your tutorial. Thanks.

[@Towhid-ze3rw]

Sir, thanks a lot for this. If I am cracking that interview, much credit will be given to you.

[@YOUTUBE_IS_WOKE]

@8:35 , you don't need to call totalDiffDispatcher you can directly call totalDiff function and it will return the total difference. The function totalDiffDispatcher in this iterative call is redundant and should be removed. How do you write a code to solve and count the number of nodes in a treenode? Not return one single value, but show the total nodes for each sub-branches. This is easily done with forEach in C#, but in recursion it's a bit challenging, but interesting.

[@hosamhasan6871]

simply , you are the best . because you are the only one that explains me Recursion and i understand it directly . or may be i am stupid :)

[@vantonspraul]

Thanks, glad I could help. Believe me, lots of smart people are thrown off by recursion. It's a very different way of thinking.

[@tommyeagen3763]

I love your book man amazing I comeback to it often when i feel like I am losing the ability to solve problems especially the first 2 chapters and the chapter that relates most to the problem i’m struggling with

[@vantonspraul]

Thanks! I'm glad it's continuing to help.

[@thejesse247]

Just found your channel. Thank you for putting amazing teaching content online for free, I would have killed for teachers like you in college.

[@manamsetty2664]

Please don't

[@davidjames1684]

Recursion has its place in programming, but doesn't define who a programmer is. Recursion can be replaced by iteration, and self stack management (or equivalent), so it is not required. In some cases, relying on recursion will not work, as some programming environments have greatly limited stack space/capabilities. The default setting of this may need to be increased to make a "deeply" recursive program run without a stack error.

[@enzoyasuo9264]

Thanks! Recursion really is a difficult topic but this helped me with some difficulties, but now I got to test them out

[@Towhid-ze3rw]

I can't apply the dispatcher function logic for the problem statement "Remove duplicates in a string". Someone please help.

[@abdenourbacha4782]

thank you very much sir ,only god knows how much i have struggled with reccursion before this video.

[@vantonspraul]

Glad to help!

[@richikghosh5207]

one liner: base case; return totalDiffDispatcher(SensorA,SensorB,size-1)+abs(SensorA[size-1]+SensorB[size-1]);

[@richikghosh5207]

Btw good video.

[@DavidKing-wk1ws]

OK thats it I will buy the book but I need it hand written in no.2 pencil, reflecting 2 forms of ID, 4 major credit cards and a note from the publishers mother with proof she signed it. :)

[@ruchisharma8105]

Best recursion video so far.

[@rawanfouda2291]

Good technique! we somehow always use it but you've put it into words so that we can embrace it. Thank you!

[@MultiSteveB]

Nice video. I had dabbled in recursion before, and wrote a PHP program to read an XML file into a ragged array.

[@barelylate]

Step 3 blew my mind. So cool. Thank you for this video sir

[@xinfinity4756]

what is an example of a problem that iteration can't solve or can't solve easily that recursion can solve or can solve easily?

[@mariusandries4103]

This is quite nice explanation on recursive function. Thanks Sir.

[@vantonspraul]

You're welcome. I'm glad it was helpful!

[@mohitrai7896]

this playlist will also help you in recursion kzbin.info/aero/PLawezQIZQjjtlQALUagYLQI2Q1Yq1h4OC

[@biccsdev]

Thanks to you, i understand recursive algorithms now... THANKS!!!!

[@varun9836]

This is cool. One can clearly understand recursion following your video and your book. Thanks.

[@muneebzubair5069]

This is not working for my problem: find any pair in array whose sum is equal to a key. bool pairSum(int key, int arr[], int s, int e) { for (int i = s; i < e; i++) { for (int j = i + 1; j

[@carroviejo80]

Kudos man, thank you very much. Im an spanish student and this is just what i need.

[@11am]

When is Think Like A Programmer, Python Edition : A Beginner's Guide to Programming and Problem Solving going to be available?

[@Akshaykumar-bl8ok]

That's the good way to think , whenever recursion comes into your mind.

[@mamo987]

followed along and finally had something click! thank you !!

[@petrnovota8238]

Thank you for this amazing video. Finally I am able to handle recursive problems. Well done Thank you!

[@vantonspraul]

Thanks! Glad it helped you out.

[@baburao1668]

hey man, does it way to do recursion a = [1, 10, 15, 16, 12] b = [2, 10, 14, 15, 11] r = [] t = 0 def A(): for i in range(len(a)): r.append(a[i] - b[i]) B() def B(): for q in range(len(r)): if r[q] < 0: r[q] = r[q] * (-1) C() def C(): global t for e in range(len(r)): t = t + r[e] print(t) A()

[@mog2182]

What an awesome approach.

[@vantonspraul]

Thanks! Glad you liked it.

[@shubhamdeshkar1685]

I was stunned at the end of this video! :0

[@vantonspraul]

Stunned in a good way?

[@shubhamdeshkar1685]

@@vantonspraul Absolutely.. This is the best explanation I have seen.

[@minhazulislam4682]

6:18 if you are new to C++ programming.... Meanwhile, I never wrote a line of C++. Ironically, I use python for competitive programming.

[@Freeze014]

i am like 7 years late to the party... but I am trying to understand how this works and maybe typing it out helps me organize my thoughts even if there is no reply :) I added a line that output the diff at every step and was at first surprised that it didnt start with the difference of the final position (5th reading of the sensors) and added the others as it went, but instead started with the difference of the first positions. So am I correct in thinking that when a recursive function is run, it goes until it runs into the statement that breaks the recursion (in this case if size == 0; return 0;) then it rewinds what it did and combines the total value as it would have done in a for loop?

[@benfrese3573]

Don't know if this is still relevant, but in order to understand recursive functions I would suggest you look at an explanation that includes the 'Stack' - it will make things clearer about what values are returned and how the recursive function calls are handled.

[@anthonyb1053]

although this video isn't great, the chapter of the book that this guy wrote is awesome!! Learned recursion in one night. Thank you for posting this chapter V.Anton Spraul !!!!!!!

[@vantonspraul]

Okay, I'm going to ignore the first part of that and take this 100% as a compliment :-). I'm glad the chapter was helpful!

[@Raging.Geekazoid]

If you want to understand recursion like a programmer, stop thinking about the function you're using and start thinking about the data you're analyzing or the problem you're solving. The important thing to take away from this video is the idea of looking at the whole problem from above (i.e. from the dispatcher's point of view). Getting stuck thinking about what's inside a recursive function is confusing, because then the environment outside the function (i.e. the actual problem itself) becomes a mystery. Analyzing linear data structures is exactly what you DON'T need recursion for, and doing two of them together doesn't really make the explanation any clearer. What you DO need recursion for is tree-shaped data structures and AI decision trees, because there is no iterative version of those programs. The loops would have to be nested, and in many cases there's no way to know ahead of time what the limits of the loops and the amount of nesting would be. The next step after watching this video is to learn what to do when the dispatcher function needs to call itself more than once from the same call. 😮 If you're trying to deal with tree-shaped data, you'll need to visit every node in the tree, and how are you going to do that? You have to visit the root node first, because that's the only one you have direct access to, so it's the only way to get to the inner nodes. Then you'll need to visit the children of the root, then the children of the children, and so on down to the end nodes of the tree (trees are always pictured upside down 🙄). And the easiest, simplest way to do that is to call a function to deal with each node. If you try to do it all with one call to some kind of mega-dispatcher function, you'll have to create a data structure called a "stack" (i.e. a trail of crumbs that shows you the way back home) to remember which nodes you went through to get to the current node, and now you're re-inventing the wheel. Every program already has a stack that's used for function calls. You might as well use that. And you might as well use the same function you used on the root node, because why not? You're performing more or less the same operations on each node, except for the leaf nodes, and you don't know ahead of time when you'll run into one. If you're working on an AI algorithm, you don't know ahead of time what steps the AI will have to take, and there will be multiple possibilities at each step. So the space of possible actions for the AI to take is shaped like a tree. Might as well write a function to deal with each step and have it make another call to itself when it's time to deal with the next step. That's recursion. You'll have to put some logic in the function to decide whether it's dealing with a leaf or a branch node, but that's easy. And remember: You make calls from the top down and return results from the bottom up. (1) The function's parameter list needs to contain whatever information the function needs to analyze the nodes of the tree, (2) the return value needs to contain whatever information you're trying to extract from the tree, and (3) in many cases you'll have to combine the results of the calls to a node's children before returning from that node (the parent of the children). That's all there is to it! 🙂

[@mohammedalhaythami2416]

Please. Design progam in C++ that contains a function that takes those characters and returns a string that contains only the upper case ! etters.. use recursion

[@jlee2905]

wtf... i finally understand recursion after 4 years of wasted tuition on my CS degree! :) I'm buying your book!!!

[@vantonspraul]

Thanks! Hopefully that degree wasn't a total waste!

[@PhuNguyen-yf5to]

The video helps me somehow! Thank you very much!! Wish you for the best luck ever!!

[@AnIndianify]

Hi Anton, I love your series and would like to buy your book, but it costs 2200 Rupees in India which is quite a lot not only for the students but also for working professionals and there is no economic editions available for your book like some others e.g. CLRS. Can you kindly ask your publisher to release an economic edition

[@viveksuman9600]

I will just write empty iterative functions and assume it solves the problem for my own satisfaction because I still can't trust recursion. lol. This video helped alot. Thanks!

[@beyondsingularity628]

I think you are a great programming teacher!

[@okereaforkelvin]

Still didn't get it...😒

[@syedwasay3087]

increase the playback speed to 1.25 will make it more easier to watch :D

[@azdinefx6545]

how can I do this whit the factorial example ?

[@Ea9Le]

Thanks for the great explanation. Looking at your sample, what exactly would be the advantage of the recursive version?

[@vantonspraul]

+Jeremy Ymerej Thanks, glad you liked it. There's no particular advantage of using recursion here. The method I use for teaching recursive problem solving works best when you start with problems that are relatively straightforward to solve using loops, but that also means they are the problems for which recursion is least beneficial. But once you get the idea you can use it on other problems where you just pretend to write the non-recursive solution first without really writing it.

[@cezarzbughin3362]

I like to think of Recursive function as being a squere with codelines inside. at the end, calling it we will get a square inside a squere inside a squere and so on, but at some point it will stop, no more squares, so the smaller square will get to its end, this will cause it to break and it breaking will cause the next one to break and the next one also. the function got to its end and now everything is breaking exactly like zuma balls.

[@mohitrai7896]

this will also help you kzbin.info/aero/PLawezQIZQjjtlQALUagYLQI2Q1Yq1h4OC

[@johnkeck]

This was very helpful--thanks!

[@misharuko1514]

Amazing!!! Thank you so much!

[@vantonspraul]

You're welcome!

[@provashadhikaryshoumma6795]

Your videos are great. I wish some more videos from you.

[@vantonspraul]

Thanks! I'm working on the next one...

[@tomyang7788]

where is the base case at 9:16 , will this cause an array index out of bound exception ?

[@vantonspraul]

It's the first line of totalDiffDispatcher. The base case is size == 0.

[@bismeetsingh352]

Unable to apply this to dynamic problem of fibonnaci numbers. You said to have last two values in dispatcher. But my array is empty from the end.

[@vantonspraul]

I have another video on dynamic programming, specifically including the Fibonacci sequence as an example: kzbin.info/www/bejne/n6fCqnugotCpaqs. Have you checked out that one yet? If you have and you still are having trouble, post again and let me know!

[@bismeetsingh352]

V. Anton Spraul I haven't checked that one out yet but even if we don't use DP here,we still won't be directly knowing the last two elements.

[@bismeetsingh352]

V. Anton Spraul probably I expected a response

[@amoghkulkarni3519]

Awesome explanation . Thank you sir.

[@asaadmaher1828]

but how does totalDiffDispatcher function terminate? It will keep sending 'size-1' each time it's called, or am I getting it wrong?

[@vantonspraul]

+Asaad Maher It will do that ALMOST every time it is called. The first line of the function checks if (size==0). If it is, the function returns 0, terminating at that point so that the statement with the recursive call is never executed. So, assuming size starts off >= 0, eventually the terminating condition will be reached and the recursion will start to unwind.

[@asaadmaher1828]

Oops! How blind I was not to see that line!! Thanks Mr. V. Anton Spraul. I'm number one follower of your videos. Please don't stop making such great series!

[@vantonspraul]

+Asaad Maher Don't worry, it happens to us all. Thanks for the encouragement. I've got a couple of other videos in progress, just been finishing up a different project first.

[@asaadmaher1828]

+V. Anton Spraul One more question Mr. Anton. Can you make a video about dynamic programming. I am really confusing it with recursion. Could you support the concept by one or 2 problems, and is every recursive programming problem can be solved by dynamic programming

[@IDK-kv8ob]

Love these videos.

[@yankumar5280]

thanks for sharing V. Anton Spraul

[@marrylo842]

Somehow it's starting make sense to me now... 😳

[@animeprofiles2077]

Damn it worked so well , you are a genius !!

[@biancacorbu9984]

where could I find the answers to the exercises in the book?

[@vantonspraul]

Hello Bianca! I don't provide an answer key to Think Like a Programmer, because the point of the book is figuring out how to solve problems, not the solutions themselves.

[@TechAsif24]

thank you before watch your video....now i am watching

[@saptarshibanerjee4757]

def absolutevalue(list1,list2,size): if size==0: return 0 dif=abs(list1[size-1]-list2[size-1]) return absolutevalue(list1,list2,size-1)+dif print absolutevalue([12,34,56,67],[45,56,78,90],4) this iterative code in python is not working why prof?

[@EmulatE42]

it works, but you have wrong indentation for return 0

[@warshon123]

You're missing a semicolon after the 'return' statement and the 'dif=abs' statement.

[@bismeetsingh352]

Warshon python doesn't know semicolons

[@BoomcoreIsLive]

Thank you so much, I see improvement in myself :)

[@vantonspraul]

Glad to hear it!

[@rahulsolankib]

Ohhhh let me try!

[@HA-jk6yi]

Great work. Thankyou

[@sravanthkumarchintalacheru1359]

Thanks, professor!

[@computersagain]

Your channel is so awesome!

[@mohitrai7896]

this channel will also help you kzbin.info/door/oEt3glB4rWSq5zEhSGhUWA

[@yashashav_dk3766]

Sir, you are AMAZING! FUCKING AMAZING. Love your book with all my heart!

[@vantonspraul]

Thank you for your kind (and not particularly kruel) words!

[@_withoutwax]

Wow this is gold 💯

[@e4e585]

Your voice sounds like sheldon 😆

[@BigOleHeals]

amazing. thank you so much

[@vantonspraul]

You're welcome, sir!

[@carlazacarias1810]

THANK YOU SOOOO MUCH!!!!!

[@jacksmollen9023]

Fantastic Video!

[@vantonspraul]

Thank you, sir! Glad you enjoyed it.

[@anikethdeshpande8336]

Thank you

[@saptarshibanerjee4757]

This is throwing error in the compiler

[@robotpanda6322]

nice i see a steam icon

[@mybigbeak]

If you already have an itterative answer why write a recursive?? this makes no sense. the secret trick is just to assume the function already works and the use it like it does.

[@saeedbaig4249]

"If you already have an itterative answer why write a recursive??" So u can learn how to write recursive programs, which is useful since some programs are easier to write recursively than iteratively (if u know how to program recursively, of course). Recursive code also tend 2 b shorter then iterative code.

[@mauricioxv]

Just because you have an itterative approach it doesnt mean you will have sufficient time to wait for the result. Some problems just can not be solved by itteration in practice even if you have a correct algorithm. You can calculate the cost of an itterative approach and find out that it would take million years to find the answear.

[@fahadahmad9881]

Recursive code tends to be more readable, shorter and thus easier to maintain. Write a depth first search algorithm in both iterative and recursive fashions. Compare the code between the two. You'll find the recursive solution is a lot easier to read and write in most cases because you don't have to explicitly manage the stack.

[@udaykadam5455]

Just google....( Hanoi Tower problem). U will get the idea.

[@monobinachattopadhyay9897]

your trick is gold

[@Midna81]

Brilliant.

[@AhmedAli-jx9ie]

not all problems could be solved with iteration

[@thesuperiorman8342]

That's why he said to start off with problems that can be solved through iteration. Then once the process comes naturally to you, you can apply it to problems that can only be solved recursively.

[@ngaihte]

Whoa! Mind blown

[@metalflames4]

I LOVE YOU!

[@siddharthmittal9355]

thanks teacher

[@vantonspraul]

You're welcome...

[@Anonymous-xj6ed]

This is fucking some sort of magic.. this always works 😲🤯

[@saidianas8284]

How can i get the pdf version of the book for free ?

[@vantonspraul]

Just follow the link in the description to No Starch's page for the book, and from there you'll see a link to download the PDF of the chapter.

[@moosegoose1282]

wait, so if the size reaches 0 and the recursion is done, the function will return 0 and not the final result...

[@Tanssive]

TrollBronze use an if condition

[@screentrailers1331]

main content starts at kzbin.info/www/bejne/pXzRlZyjapJ6b5Ym11s

[@virengadkari383]

was fine until you started doing this in c++ im a java kinda guy

[@sishubjoshi9144]

:eye_speech_bubble:

[@Bellenchia]

Bot

[@vantonspraul]

I don't understand this comment. Who is the bot? You? Me?