Recursion (Think Like a Programmer)
Vložit
- čas přidán 30. 06. 2024
- This episode is all about recursion. You can download a PDF of the chapter in the book at the No Starch Press site, nostarch.com/thinklikeaprogrammer.
(Btw, if you want more on recursion, check out my video on divide & conquer: • Divide & Conquer (Thin... ).
Your comments and suggestions for future videos are welcome.
"Think Like a Programmer" is a book I've written to help programmers with problem solving. If you've found that you are able to read programs and understand programming language syntax but aren't always confident writing programs from scratch, my book may be able to help.
For more information on the book head to one of these:
Amazon page for the book: amzn.to/1MZlmlY
My site: www.vantonspraul.com/TLAP
My publisher's site: nostarch.com/thinklikeaprogrammer
Connect with me:
My site: vantonspraul.com
Twitter: / vantonspraul
Facebook: / thinklikeaprog - Věda a technologie
If you liked this video, be sure to check out my other videos about recursion:
Divide and Conquer: czcams.com/video/11V7Ik0IBHU/video.html
Dynamic Programming: czcams.com/video/iv_yHjmkv4I/video.html
The Peg Puzzle: czcams.com/video/Yh2yUtPPHtE/video.html
hey provide your book free for people like me as have no proper sources
Youth Inititiative It is for free.
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.
Thanks for the kind words. Glad you liked it!
Finally someone who can teach recurrence without Fibonacci!! Good video 👍
Amen xD
Yess bro
Exactly!!
hahaha
🤣🤣🤣best
I think I finally understand recursion..
Normally when recursion is taught they simply say, "first create your base step, this ends the recursion, then create your recursive step here the function calls itself and solves the problem recursively". Most resources I have found don't really elaborate on the thought process rather they elaborate on what is happening at a lower level (stack, etc).
Through this video I have found that recursion can actually be broken down into three steps:
1. The base step (stops recursion)
2. The Minimization step (creates the smallest possible instance of a problem. Example: 500 element array turned into 1 or 2 element array)
3. The Solution step (This handles the solution for the 1 or 2 element array rather then the 500 elements)
Once the function arrives at the Solution step, the array has already been broken down to its smallest possible version. It then solves the smallest problem and works its way up solving and handling the rest of the array.
Thank you so much for making this video!
That's it exactly. Most discussion about recursion is about how recursion works, which in most cases isn't important. What's important is figuring out how to use recursion to solve problems.
this will also help you czcams.com/play/PLawezQIZQjjtlQALUagYLQI2Q1Yq1h4OC.html
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
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.
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!
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.
Thanks, Alek. I agree, problem solving is often the missing ingredient when programming is taught.
I have been stuck on the topic of recursion for several days, and now it has finally clicked.
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.
Good technique! we somehow always use it but you've put it into words so that we can embrace it. Thank you!
finally i get to know the big idea and baby steps to take while learning recursion. all thanks to you sir. 😄
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. ♥
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!
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.
Thanks! Recursion really is a difficult topic but this helped me with some difficulties, but now I got to test them out
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
Thanks! I'm glad it's continuing to help.
This is cool. One can clearly understand recursion following your video and your book. Thanks.
Step 3 blew my mind. So cool. Thank you for this video sir
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..
Kudos man, thank you very much. Im an spanish student and this is just what i need.
The video helps me somehow! Thank you very much!!
Wish you for the best luck ever!!
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 :)
Thanks, glad I could help. Believe me, lots of smart people are thrown off by recursion. It's a very different way of thinking.
Thank you for this amazing video. Finally I am able to handle recursive problems. Well done Thank you!
Thanks! Glad it helped you out.
Thanks to you, i understand recursive algorithms now... THANKS!!!!
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.
That's great! Glad my book was so helpful. Recursion can be pretty fun to play with once you get the hang of it.
True. I am getting this feeling after going through your tutorial. Thanks.
Nice video. I had dabbled in recursion before, and wrote a PHP program to read an XML file into a ragged array.
thank you very much sir ,only god knows how much i have struggled with reccursion before this video.
Glad to help!
Just found your channel. Thank you for putting amazing teaching content online for free, I would have killed for teachers like you in college.
Please don't
Best recursion video so far.
followed along and finally had something click! thank you !!
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.
Nice thx sir
This is quite nice explanation on recursive function. Thanks Sir.
You're welcome. I'm glad it was helpful!
this playlist will also help you in recursion czcams.com/play/PLawezQIZQjjtlQALUagYLQI2Q1Yq1h4OC.html
What an awesome approach.
Thanks! Glad you liked it.
Love these videos.
I think you are a great programming teacher!
Damn it worked so well , you are a genius !!
Awesome explanation . Thank you sir.
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.
Those are good analogies.
Wow this is gold 💯
Your channel is so awesome!
this channel will also help you czcams.com/channels/oEt3glB4rWSq5zEhSGhUWA.html
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 !!!!!!!
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!
This was very helpful--thanks!
Thanks, professor!
Your videos are great. I wish some more videos from you.
Thanks! I'm working on the next one...
Great work. Thankyou
I was stunned at the end of this video! :0
Stunned in a good way?
@@vantonspraul Absolutely.. This is the best explanation I have seen.
Amazing!!! Thank you so much!
You're welcome!
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.
That's the good way to think , whenever recursion comes into your mind.
thanks for sharing V. Anton Spraul
THANK YOU SOOOO MUCH!!!!!
Fantastic Video!
Thank you, sir! Glad you enjoyed it.
Thanks for the great explanation.
Looking at your sample, what exactly would be the advantage of the recursive version?
+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.
Thank you so much, I see improvement in myself :)
Glad to hear it!
Sir, you are AMAZING! FUCKING AMAZING. Love your book with all my heart!
Thank you for your kind (and not particularly kruel) words!
I LOVE YOU!
Ohhhh let me try!
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
amazing. thank you so much
You're welcome, sir!
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!
Whoa! Mind blown
wtf... i finally understand recursion after 4 years of wasted tuition on my CS degree! :) I'm buying your book!!!
Thanks! Hopefully that degree wasn't a total waste!
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. :)
When is Think Like A Programmer, Python Edition : A Beginner's Guide to Programming and Problem Solving going to be available?
Brilliant.
thank you before watch your video....now i am watching
Thank you
@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.
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?
Somehow it's starting make sense to me now... 😳
one liner:
base case;
return totalDiffDispatcher(SensorA,SensorB,size-1)+abs(SensorA[size-1]+SensorB[size-1]);
Btw good video.
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?
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.
where is the base case at 9:16 , will this cause an array index out of bound exception ?
It's the first line of totalDiffDispatcher. The base case is size == 0.
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()
how can I do this whit the factorial example ?
where could I find the answers to the exercises in the book?
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.
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
thanks teacher
You're welcome...
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.
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.
I have another video on dynamic programming, specifically including the Fibonacci sequence as an example: czcams.com/video/iv_yHjmkv4I/video.html. Have you checked out that one yet? If you have and you still are having trouble, post again and let me know!
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.
V. Anton Spraul probably I expected a response
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
but how does totalDiffDispatcher function terminate?
It will keep sending 'size-1' each time it's called, or am I getting it wrong?
+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.
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!
+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.
+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
This is fucking some sort of magic.. this always works 😲🤯
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.
this will also help you czcams.com/play/PLawezQIZQjjtlQALUagYLQI2Q1Yq1h4OC.html
nice i see a steam icon
increase the playback speed to 1.25 will make it more easier to watch :D
6:18 if you are new to C++ programming....
Meanwhile, I never wrote a line of C++.
Ironically, I use python for competitive programming.
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?
it works, but you have wrong indentation for return 0
You're missing a semicolon after the 'return' statement and the 'dif=abs' statement.
Warshon python doesn't know semicolons
Still didn't get it...😒
main content starts at czcams.com/video/oKndim5-G94/video.htmlm11s
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! 🙂
This is throwing error in the compiler
wait, so if the size reaches 0 and the recursion is done, the function will return 0 and not the final result...
TrollBronze use an if condition
How can i get the pdf version of the book for free ?
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.
Your voice sounds like sheldon 😆
not all problems could be solved with iteration
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.
:eye_speech_bubble:
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.
"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.
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.
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.
Just google....( Hanoi Tower problem).
U will get the idea.
your trick is gold
was fine until you started doing this in c++ im a java kinda guy
Those who are unlikilng video are fools
Bot
I don't understand this comment. Who is the bot? You? Me?
Disliked, verbose video made to induce you into buying the book. Am I wrong? Recursion is pretty simple, it takes thirty minutes of your life to figure it out yourself. What you are doing here is you are inducing confusion and then solving it poorly in order to create dependence, which you cash out
seriously can you explore it easier?
Really? He made this chapter of his book free in order to help people with recursion. He could have said "if you want to find out more you can purchase my book" but he didn't. Don't be ungrateful.
Okay, I will watch it again now, how about that? Here are the problems "The big recursive idea is to not think about recursion", and before that, the fact that a function calls itself but halts because it's reading other parts of the function this time. What I have said about the induction of dependence is correct. One minute after saying his "big recursive idea" I can refute him saying that recursion problems are solved with diagrams and understanding, it is like the video is just wrong, man. This guy is a horrible teacher. You can only be grateful if you lie to yourself about his mistakes.
you obviously didn't even watch the video. you obviously don't understand recursion at all. if you did you would know how great this video really is.
Leo Sousa Right on. Totally verbose.