Recursion and Is It Better Than For Loops? - Python for Beginners

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

Channel: Python Simplified

Views: 3,486

Rating: 4.980907 out of 5

Keywords: fibonacci, fibonachi, fibbonachi, fibbonacci, recursion, python recursion, recursive functions, recurssive, recurssive functions

Id: m1Fjdnj_Mds

Length: 9min 7sec (547 seconds)

Published: Tue Oct 05 2021