## Reading

Recursion recursion is when a function calls itself lets look at the classic Factorial function.. its like the hello world of recursion factorial, in mathematics, the product of all positive integers less than or equal to a given positive integer and denoted by that integer and an exclamation point. Thus, factorial seven is written 7!, meaning 1 × 2 × 3 × 4 × 5 × 6 × 7. Factorial zero is defined as equal to 1. 5! = 1 x 2 x 3 x 4 x 5 5! = 120 4! = 1 x 2 x 3 x 4 4! = 24 3! = 1 x 2 x 3 3! = 6 2! = 1 x 2 2! = 2 1! = 1 we can write a standard iteravive function to acomplish this like so int Factorial ( int val ) { int fac =1; while (val > 0) { fac *= val; val --; } return fac; } but we can also do this with recusion consider this 5! = 5 x 4! 4! = 4 x 3! 3! = 3 x 2! and so on so a very simple recursive version is --------------------------------------------------- int Factorial (int val) { return val * Factorial(val - 1); } see how this matches what we have for 5!,4! and 3! above Our recursive Factorial function has a major flaw, it will just call itself forever .... if we call our factorial function with a value of 5 it will then inturn call itself with 4, then 3, then 2, then 1, then 0, then -1, then -2 it will never stop. so we need a terminating clause... when do we stop??? for the factorial function it is that 1! has an answer of 1 we dont need to call the factorial funtion again to get this answer. -------------------------------------------------- int Factorial (int val) { if (val == 1) return 1; return val * Factorial(val - 1); } now we have a complete recursive function. it has the MANDITORY terminating clause at some point val will finally == 1 and we will not call the function again and return an answer so lets walk through calling our function with 5 cout << Factorial(5); call to Factorial(5) return 5 * Factorial(4) return 4 * Factorial(3) return 3 * Factorial(2) return 2 * Factorial(1) (terminating clause this is the last time Factorial will be called then it steps backwards returning 2 * ( 1 ) return 3 * ( 2 ) return 4 * ( 6 ) return 5 * ( 24 ) recursion can be used in certain scenarios to create elegant solutions to some problems imagine someone asks you to search a toybox for an evil kenivel stunt cycle. you are supposed to search and say either yes I found it or no I did not. a recurive solution might be take a toy out of the box is it the stunt cycle ?? if yes return true is the toybox empty? if yes return false ( we didnt find it ) otherwise repeat process... (take out another toy) its simple logic. in this scenario we have two terminating clauses but it is basically the same thing do we know the answer to return? if not repeat the process. Recursion can use up a lot of memory. our iterative function has 2 integers val and fac so it will need 8 bytes of memory to calculate a value but our recursive function only has one varaible val requires 4 bytes but if we called Factorial(25) it would in turn call Factorial(24), Factorial(23)... and so on in total the function would need to be called 25 time, each one requires 4 bytes.. so it would need 100 bytes of memory to do the calculation and if we called Factorial(1000) it would take 4000 bytes and our iterative version would still have only needed 8 bytes that is a HUGE difference if you look at the lab for tonight we are going to traverse a maze start ████████████████████████████ █ █ █ █ █ ████ ████ █ █ ██████████ █ █ █ █ █ █ █ ████ █ ███████ █ ████ █ █ █ █ █ █ █ █ █ █ ██████████ █ █ ████ █ █ █ █ █ █ ██████████ ███████ ████ ████ █ █ █ █ ████ ███████ █████████████ █ █ █ █ █ █ █ █ █ ███████ ████ █ ████ █ █ █ █ █ █ █ █ █ ████ ████ █ ████ ████ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ ███████ █ █ █ █ █ █ █ █ █ █ █ █ ████ ████ █ ████ █ █ █ █ █ █ ████████████████████████████ finish as you traverse the maze you really have only a few options and some clear terminating clauses did you reach the finish?? if so return true are you at a dead end ?? if so return false we have clear cut termiating clauses so it might be a good candidate for recursion if we are not at a terminating clause then what do we do ... simple " take one step and then start the process again " its like the toy box example each time we pull out one toy. to traverse the maze we take one step at a time. eventually we will have moved to every position in the maze. we do need some logic but it is not complex try to go right try to go left try to go up try to go down and dont go somewhere you have already been regardless of the size of the maze our recusive solution should try every possible scenario in seach of the answer.