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 favourite 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 eight
we would 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 "EvenNums"
which takes in a numeric value of our choice
and first, we will tackle the base case
with "if num == 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 2
we will need an "else" clause
where we return a call to the "EvenNums" function
and we pass our number - 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 "EvenNums" on the number 8
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 0
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 2 previous values
so for example: 0+1=1
1+1=2
1+2=3 and so on until infinity!
we can find this sequence in nature, in Pascals 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 0 we have the number 0
at index 3 we have the number 2
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 call
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 - 2
and of course, my head is probably blocking it!
and surprise surprise - our function is complete!
now 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 0
now as you guys have seen before, this would return the number 0
perfect! we are getting 0 in return!
so let's boost it to index 3
this should return the number 2
perfect! and just to be extra cautious - let's also call it on index 8
and this should return 21
ah! perfecto! bravo! (Italian)
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(idx):"
we will append a brand new value to our sequence
so we will type: seq.append()
where the value would be the sum of the last item in our sequence,
represented by index [-1] ,
plus the item in our second last index represented by -2
and then we can go ahead and exit the "for loop"
and we will return sequence in the index of [-1]
but note!
that since we've started with 2 values rather than 1
if we will call "fibonacci" on index 0
it will skip this "for loop" altogether
and will return the last value of our sequence which is 1 - while we're actually looking for 0!
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 re-factor the capital "F" into 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 it 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.time()
we can then assign it to a variable called "rec"
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 see if it turned out
so let's go ahead and click on "run"
and if your guess wat 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