in this video we discuss recursion how it can be used and how it compares to an iterative approach [Music] it's important you've got a solid understanding of the basic programming concepts and different data types before you watch these videos we covered those in slr playlist 8 and 13. although you could learn the theory independently it makes much more sense if you're able to work through these videos and their examples by implementing their concepts in real programmed code these videos are therefore designed to reinforce and consolidate the understanding of programming techniques you will need for the exam rather than teach you these concepts from scratch remember the way to become a good programmer is by programming little and often you don't become a good programmer simply by watching videos and studying theory so let's start with the obvious question what is recursion well recursion is when a subroutine often a function calls itself within its own subroutine a recursive subroutine should exhibit these three characteristics it should contain a stopping condition sometimes known as a base case second for any input value other than the stopping condition the subroutine should call itself this is the act of recursion and finally the stopping condition should be reachable within a finite number of times without these characteristics a recursive subroutine may call itself indefinitely resulting in a stack overflow and you'll see what we mean by this later on so to fully examine the concept of recursion let's write some code that produces the factorial of a number supplied by a user so the factor of a non-negative integer n is the product of all positive integers less than or equal to n in mathematics we donate this as n explanation mark so for example 3 factorial would be 3 times 2 times 1 equals 6 and so on and so forth okay as this problem will perform the same operation that's a multiplication again and again to produce an answer your first thought might be to use an iteration construct and we've written a function here for producing the factor of an integer using iteration and it's on the screen here we can see a function called factor underscore it is taking a single integer n as a parameter let's imagine the users called this function and passed it the value three we start by declaring two variables counter and answer both are currently null we then initialize both these variables to one we now enter a for loop and we say for counter equals 1 to n so n is 3 so this loop will execute 3 times there's a single line of code inside the for loop answer equals the current answer times counter so that means currently answer equals one times one we've reached the next statement which causes the counter incremented two back inside the for loop the single line of code executes again answer equals answer times counter so now answer equals one times two we reach the next statement again so counter increments to three back inside the for loop we run the single line of code now we've got answer equals two times three we hit the next statement which increments the counter to four this means when we check the condition for entering the for loop they're no longer being met we skip past the for loop to the function's return statement which then outputs the value currently held in the variable answer which is 6 and the function ends we successfully calculated the factor of 3 using an iterative approach in this case a for loop now here's the function we've written using recursion the first thing to notice is there are fewer lines of code remember this code performs exactly the same functions before except now it's going to use recursion instead of iteration as before we have a function this time called factor underscore rec which takes a single integer n as a parameter so let's call this function again passing it in the initial value of three we start with an if statement if n equals zero well n doesn't equal zero it equals three the value that was passed in when the function was called so we jump to the else section of the if statement at this point we hit an interesting line of code we've got factor wreck equals n times factor wreck open brackets n minus one close brackets now this is where the magic happens the return value of factor underscore rec is going to become equal to n multiplied by the value returned from a brand new call to the function factor rec but this time passing in n minus one the function has just recursively called itself the original copy of the function is paused and we're now executing a new copy of it now don't worry if you're finding this a little confusing at the moment we're going to step through it so you really get to understand what's going on so this is a valid recursive function as it meets all three of the conditions we outlined at the start of the video it contains what we call a stopping condition a base case a terminating condition and it's here it's when n equals zero for any input value other than the stopping condition the subroutine should call itself recursively and indeed it does in the else part and the stopping condition should be reachable within a finite number of times well it is and we'll prove that to you so let's work through this recursive function in detail so you fully understand how it works so here's the entire program this time we've included an extra subroutine called main and that's going to be responsible for passing in the integer value 4 and then it's going to output the result of calling factor rec with the value 4. so it should end up outputting to the screen 24 which is 4 times 3 times 2 times 1. on the right is an abstraction of the stacks in memory we're going to use this to keep track of two important details the first column is going to hold the contents of the variable n and the second column keeps track of which line of code to return to as the algorithm recursively calls itself and then starts to unwind currently the stacks are both empty the program starts at line nine and proceeds to line ten here we call factor underscore rec and we pass in the value four we now jump to line one of that function and at the same time we push the value 4 onto the n stack to show that variable n has taken on this initial value we push 10 onto the call stack as that's the line of the program we'll need to return to when this current function exits we hit an if statement if n equals zero well n is not equal to zero so we skip to the l section on line 5. we hit a recursive call that calls the factor rec function again this time passing in the value of n minus 1 which is going to be three we're now executing a brand new copy of the function factor rec we've passed in the value 3 and pushed it onto the stack once this new copy of the function exits we'll need to return to the original copy so we've also pushed five onto the call stack we reach the if statement again if n equals zero or n is not equal to zero so we skip to the else section on line five next we hit another recursive function call so once again we call the function factor rec and pass it the value of n minus one well n minus one now is currently two three minus one is two we're now executing another new copy of the function factor rec we've passed in the value 2 and pushed it onto the end stack once this copy of the function exits we'll need to return to the original copy so we've also pushed another 5 onto the call stack we reach the if statement if n is zero well it's not it's two so we skip to the l section and we hit yet another recursive call once again we call the function factor rec and passing the value of n minus one or n is currently two so n minus one two minus one is one we're now executing yet another new copy of the function factor rec we've passed it in the value 1 and pushed it on to the n stack once this copy of the function exits we're going to need to return to the previous copy so we also have pushed another five onto the stack we reach the if statement again if n equals zero well n isn't zero it's one so we skip to the else part on line five and we hit yet another recursive call once again we simply call the function factor rec and this time pass it n minus one well n is one so one minus one is zero okay so we're one two three four five levels deep into this recursive function call so watch what happened happens carefully now finally we have a situation where n does equal zero we've hit the terminating or stopping condition the stack of recursive functions will now begin to unwind so as we've reached line three we have factor underscore rec equals one this is the return clause of this function and we will need to return this value to the previous copy but how do we know to return to well when we hit the end of a function or its return statement we pop the values off the top of the stack these values tell us to return to line five of the previous copy of the factor rec function passing it the value one and you can see we've shown that on the screen having returned to the previous copy of the function and passed it the return value of 1 we can finally evaluate this expression and complete the assignment statement so we have n which if we look at the top of the stack is one multiplied by one so one times one is one so factor rec is assigned the value of one we've hit a return clause of this function and we also need to return this value to the previous copy again as we've hit a return statement we pop the values off the top of the stack these values tell us to return to line five of the previous copy of actual wreck and pass it the value one we're starting to unwind the stack okay so having returned to the previous copy of the function and passed it the return value of one we can finally evaluate this expression and complete its assignment statement so we have n again which if we look at the top of the stack is two multiplied by one or two times one equals two so factor wreck is assigned the value two we have hit a return clause of this function and we also need to return this value to the previous copy again as we've hit a return statement we pop the values of the top of the stack these values tell us to return to line 5 of the previous copy of factor rec and pass in the value 2. we are continuing to unwind the stack having returned to the previous copy of the function and passed it the value 2 this time we can finally evaluate this expression and complete the assignment so once again we've got n which if we look at the top of the stack is currently 3 multiplied by 2 which was returned so 3 times 2 equals six so factor rec is assigned a value six we're here to return clause again and as before we pop the values off the top of the stack these tell us once more to return to line 5 of the previous copy of factorial rec and pass in the value 6. we continue to unwind the stack having returned to the previous copy of the function and passed in the return value of 6 we can once again evaluate this expression and complete the assignment statement so we have n which if we look at the top of the stack is currently 4 multiplied by the returned value of six so four times six equals twenty four so factor rec is assigned the value twenty four we reach the final return clause as before we pop the values at the top of the stack these tell us to return to line 10 of the subroutine sub main in this case and pass the value 24. this gets written out to the screen we have finished fully unwinding the recursive function the stacks are now empty and we write the value 24 to the screen which of course is the factor of four four times three times two times one is twenty-four so here are both approaches to solving the factorial problem the first using iteration and the second using recursion so which one do you think is more efficient in terms of memory usage well in this situation the better option is using iteration and the for loop recursion is actually not very memory efficient every time a recursive function calls itself the processor needs to remember where it was before it jumps to the new copy so it knows to where to return to later the processor also needs to remember the values of all the previous variables as they're local to those copies of the recursive function and this is done using stacks which take up space in memory remember if you have a recursive subroutine that calls itself too many times before reaching its terminating condition you could run out of memory and cause the program to crash and this is known as a stack overflow generally therefore recursion should be avoided but there are situations where it is the best or sometimes the only way to solve a problem a good example is tree traversal algorithms which we look at in another video of performing a flood fill in a graphics application having watched this video you should be able to answer the following key questions what is recursion and when might you want to use recursion over iteration [Music] you