Recursion (Think Like a Programmer)

hello again this is V Anton sprawl talking about how you can learn to think like a programmer in this episode I'm going to talk a a bit about recursion there's a chapter in my book about this topic and the cool thing is that you can download and read it for free by going to my publishers website if I've set this up correctly in YouTube you should be able to see the link in the video right now and it should also be below the video on the YouTube page in this video I'm going to be explaining the concept in a slightly different way and using an example not in the book so I would recommend watching this video first reading the chapter from the website and then trying a few programs on your own to apply the ideas real quick just to make sure we're on the same page what is recursion it's when a function or some other sub program calls itself most of the time this means direct recursion that's when a call to a function occurs in that same function it can also refer to indirect recursion where two or more functions call each other in the loop but that's quite rare and we won't be discussing that kind here here's the thing about recursion depending on the area of programming you're working with you can go a long long time without needing to do any recursion so why did I put a chapter about recursion in my book about problem solving I did it because so many of the students I've had over the years have really struggled with recursive programming and by that I mean with recursive problem solving there are a few people who come into this world as natural recursive thinkers but for the rest of us it's a skill that has to be learned and it's a different way of thinking than what we're used to even different from other types of programming so most people have a very hard time with it but when I showed students the technique that I'm about to show you they were able to do it so that's why I like this topic because it shows that the right technique and the right approach makes all the difference there is a methodology to solving problems using recursion and if you use that methodology you can go from someone who is frustrated by recursion to someone who can tackle any recursive problem and building that kind of confidence will help you no matter what kind of problem-solving you're doing in the future okay so what is the proper technique for solving a recursive programming problem in the book I call it the big recursive idea and I don't actually reveal it until about halfway through the chapter so I guess we should say that this is a spoiler alert but the big recursive idea is to avoid thinking about recursion at all and most books that explain recursion you'll see a lot of diagrams that look something like this for functions that linearly process arrays or lists or maybe something like this if they're processing a binary tree and the implication is that you should be thinking about all the recursive calls that will be spawned in the course of processing a particular set of data figuring out how those calls are going to fit together to produce the desired result and at some point yes it would be great to think about recursion that way but that doesn't help you solve recursive problems at all to solve a recursive problem the last thing you should think about is an elaborate diagram of function calls or what's happening on the system stack with all the activation records or anything like that let me give you an example the three-step process I show in the chapter I should say that to actually do all these three steps you have to start with a problem that you already know how to solve without using recursion but once you get good at this technique you can use the concept without explicitly following all the steps to derive a recursive solution to any problem so here's the problem we're going to try to solve recursively we've got two integer arrays of the same length representing sensor data the second sensor is intended to be redundant so in fact the two arrays should have identical values but for practical reasons there are going to be small differences so the function we're writing is computing the total absolute differences and the values so for example if sensor a sub 3 is 10 and sensor B sub 3 is 14 that's a difference of 4 and it doesn't matter which value is higher than the other it's the absolute difference that we need so we're summing the total absolute differences among the values in the same locations in the arrays here we go step 1 write an iterative that is non recursive function to solve the problem you'll see exactly why we need to do this in the next step but it also helps us get straight all the issues in the problem that have nothing to do with recursion among other things it helps us get the parameter list correct I can't say how many times I've seen students go off in the wrong direction on the parameter list and a recursive problem the simple rule is your parameter list will most likely look exactly the same whether you are writing the function recursively or iteratively in this problem we'll have three parameters the two arrays and a third parameter indicating the size of the arrays the function will return the sum my function for this step looks like this the ABS function in C++ returns the absolute value of its argument as you can see there's nothing exceptional about this code but if you're still fairly new to C++ programming you might want to pause here and make sure that everything is clear and you can see I've got simple test code in the main function step two right a second function that I call a dispatcher it does two things first it solves the problem for some minimal data set it's not always clear what the minimal data set is but in this case it's going to be when the science parameter is zero you can't get a data set smaller than an empty data set so if there is no sensor data we can just say that the total difference in the sensor values is zero the second thing the function has to do is call the first function to handle situations where the data set is not minimal the trick is the dispatcher is required to give the iterative function a smaller data set than it was given since the size of our data set is specified by the size parameter we will effectively reduce the size of the data set by subtracting 1 from that parameter in the call to the iterative function this means we have to handle the last value in the array in the dispatcher function so let's compute the difference of the last values in the arrays like this and then add this result to the value returned by the iterative function so if our original size parameter was 5 meaning in C++ values from location 0 to location for the iterative function would compute the differences from locations 0 through 3 then the dispatcher function would compute the difference at location 4 in each array and those values together would cover the entire original array and as you can see I've changed the test code to call the dispatcher rather than the iterative function you'll notice that to this point we have not thought in recursive terms at all we have not made any recursive calls haven't even used the word recursion this is the big recursive idea in action because now we are ready for step 3 and step 3 in our dispatcher we replace the call to the iterative function with a call to the dispatcher at this point we can get rid of the iterative function altogether so now we have a recursive solution to the original problem as in the previous version the function works by either handling the minimal data set or handling one small piece of the data set and then making a call that solves the problem for the reduced data set putting those results together to make the correct result for the entire data set this is the key we don't have to think about the fact that our function call is a recursive call if we don't want to we can just assume that the call we're making will return the correct result for the arguments it is given and then figure out a way to solve the entire problem based on that result if you give this idea try start as I did with a problem that you already know how to solve without using recursion so that you can explicitly go through the three steps I've shown once you've done this a few times you'll find that you can apply the technique without actually going through all three steps just by trusting the result of the recursive call at that point you can use this technique on problems that cannot easily be solved iteratively which really are the problems you should be using recursion for anyway as I stated at the beginning of this episode the recursion chapter is available at my publishers website so go check it out if you want a complete explanation of what I'm saying here I hope this helps you out and as always thanks for listening please do subscribe or hit the like button if you'd like to see more videos like this and let me know if you have any suggestions for future episodes thanks

Channel: V. Anton Spraul

Views: 130,094

Rating: 4.8864775 out of 5

Keywords: programming, C++, beginning programming, problem solving, Recursion, head recursion, how to think like a programmer, Computer Science (Field Of Study), Programmer (Profession), recursive problem solving, recursion explained, think like a programmer

Id: oKndim5-G94

Length: 10min 42sec (642 seconds)

Published: Fri May 17 2013