hi everyone today we will talk about
recursion now so far we've been using
for loops to repeat the same action as
many times as we'd like but this is not
the only way we can also use something
called recursive functions now in
computer science recursion happens when
we call a function within itself
meaning the function call is not just
outside the function but it is also
inside it my favorite example of
recursion is matryoshka which is a
russian traditional doll that hides
smaller and smaller dolls inside it now
once we reach the very last doll the one
that can't be opened anymore we actually
reach something called the base case or
the base condition for example if we
want to recursively write all the
positive even numbers smaller or equal
to 8
we will get a list of 8 6 4 and 2 where
2 represents the base case now let's see
how it looks like in code we will define
a function called even nums
which takes in a numeric value of our
choice
and first we will tackle the base case
with if num equals 2
then it means that we've reached the end
of the sequence and we will simply
return our number
however if this is not the case and our
number is not equal to two we will need
an else clause
where we return a call to the even nums
function and we pass our number minus 2.
now additionally we also want to print
our number at the very top of our
function so print num and then once we
do it we can scroll all the way to the
bottom we can leave our function and we
will call even nums
on the number eight
let's go ahead and run this code
perfect so it looks like we're getting
the results we've expected where our
base case is printed last but we can
always go the extra mile
and we can tackle odd numbers as well so
if num
modulo 2
doesn't have the remainder of zero and
in this case we would like to print
a message of please
enter
an even number
and then additionally we will turn this
if statement into an else if statement
and now even if we call this function on
an odd number let's say 9 and we run
this code and then instead of getting an
error we're simply getting a message to
improve our input cool so we've seen how
recursive functions work but are they
really better than for loops for this we
will look at another code example using
the fibonacci sequence now fibonacci
numbers are a very special sequence
where the next value always equals the
sum of its two previous values so for
example zero plus one equals one
one plus one equals two one plus two
equals three and so on until infinity we
can find the sequence in nature in
pascal's triangle in sacred geometry and
pretty much
anywhere we look including the mona lisa
but how exactly do we compute it let's
consider a function that takes in a
positive numeric value this value
represents the index of the fibonacci
number we want to return so for example
at index zero we have the number zero at
index three we have the number two at
index 8 we have the number 21 and so on
and we will begin with the recursive
function and we will call it fibonacci
with a capital f we can then pass an
index value of our choice to this
function and as usual we will tackle the
base case first now if our index
is either smaller or equal to 1 we will
then simply return the index itself
which is exactly what we've done in our
previous example however if this is not
the case inside our else clause we will
return an instance of our fibonacci
function called where we pass our index
-1 and then this takes care of the
previous value now additionally we will
add another instance of the fibonacci
function but this time we will pass it
on index
minus two and of course my head is
probably blocking it and surprise
surprise our function is complete let's
go ahead and check if it works so at the
bottom we will print an instance of
fibonacci
and at least at first we will check it
on index zero now as you guys seen
before this should return the number
zero
perfect we are getting zero in return so
let's boost it to index three
this should return the number two
perfect and just to be extra cautious
let's also call it on the index eight
and this should return twenty one
ah perfecto bravo now in terms of
iteration we will define a brand new
function called fibonacci with a
lowercase f this time we will also pass
an index value to this function but in
order to start looping we need to
account for the first pair of fibonacci
numbers we will call this pair sequence
and we will assign it to a list with 0
and 1. and now we can go ahead and start
looping so
for i in range
index
we will append a brand new value to our
sequence so we will type sequence dot
append
where the value would be the sum of the
last item in our sequence represented by
index minus 1
plus the item in our second last
sequence represented by
minus two and then we can go ahead and
exit the for loop and we will return
sequence in the index of minus one but
note that since we've started with two
values rather than one if we will call
fibonacci on index 0 it will skip this
for loop all together and we'll return
the last value of our sequence which is
1 while we're actually looking for zero
so the way to fix it is quite simple
instead of returning the last value we
will simply return the second last value
and now our iteration function is
complete let's go ahead and call it at
the very bottom we will simply copy this
print statement
and we will refactor the capital f to a
lowercase f let's go ahead and run this
script
beautiful so both our functions return
the same value the correct value but
then how do we know which one of these
is more efficient for this we will first
import the time module and then we can
record the time that takes for both our
functions to run so right above our
function calls we will type
the kind of function we're dealing with
in the first case that would be
recursion
and right before we call it we will
record the current time with time dot
time
we can then assign it to a variable
called wreck
and then right after our function call
we will print an additional statement
speed
to which we will concatenate the string
instance of the current time
minus the time we have recorded earlier
inside a variable called rec and we will
of course do the same for our iteration
function
cool now let's run it and find out once
and for all which is faster iteration or
recursion and before we do this i want
you guys to make a guess and then we
will see if it turned out so let's go
ahead and click on run
and if your guess was iteration you got
it because it is actually twice as fast
as recursion
good job so why it is so important to us
then
recursion is a very basic computer
science concept it helps us divide a
very big problem into smaller
sub-problems which we can easily solve
one at a time we call this process
divide and conquer and you guys will
encounter it a lot in your computer
science studies now thank you so much
for watching if you enjoyed this
tutorial please leave me a like maybe
leave me a comment or subscribe to my
channel turn on the notification bell or
share this tutorial with so so many
people now thanks again and i will see
you guys very soon in a brand new
machine learning tutorial