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.