Hey, can you please explain the calculation at 5.20min Fibonacci(idx-1)+Fibonacci(idx-2), as I understand if our index is 8, then ((8-1)+(8-2)), which equals 13, how did you get 21. I know that the Fibonacci number at index 8 is 21, but I don't understand this from calculation point.... Thank you!
Hi Maksims! This is a really good question, thank you for your comment! 😃 When it comes to implementing recursion in programming - we need to consider something called a "call stack", which is responsible for managing function calls. Every time a function is called - all its variables and arguments are being inserted into a "stack frame" which is a location in memory inside the call stack. The stack frame remains there until the function terminates (a certain value is returned). The Fibonacci example is a bit complex, so here's a better starting point (also recursive): def my_sum(n): if n == 0: return n #base case else: return n + my_sum(n-1) my_sum(3) STEP 1: the function returns 3 + my_sum(2) so we push it to the stack frame. STEP 2: since the return statement above includes another call to my_sum(n-1) - we create a new stack frame, but this time passing (n-1) as an argument instead of n. so then our call stack receives a stack frame of 2 + my_sum(1) and it's placed now at the top of the stack. STEP 3: because the return statement in STEP 2 also includes a call to my_sum(n-1) - we again push a new stack frame but this time of 1 + my_sum(0) STEP 4: we finally reach the base case where n==0, so we return 0. Since there are no more calls to my_sum and we reached the end of the recursion - the stack frames will now start popping one after the other and returning their values to their "parent" function. So the first function we called my_sum(3) will receive the values of its return statement LAST! The first function that receives its return values is my_sum(0), only then my_sum(1) can receive its return values, and only then my_sum(2) can receive its return values. So the outcome of one function depends on the outcome of all its previous functions, and we can only calculate it after we calculate all the previous outcomes 😊 It's more complex with the Fibonacci function as it involves 2 function calls in the return statement so it makes things much harder to follow 😵But I did find a very handy tutorial explaining the call stack in a relation to Fibonacci: realpython.com/fibonacci-sequence-python/#visualizing-the-memoized-fibonacci-sequence-algorithm I hope it helps! 😀
@@PythonSimplified Thank you so much! I've been doing online and app courses in Python, and I just couldn't grasp recursion. This helped immensely! Thank you!
"((8-1)+(8-2)), which equals 13, how did you get 21" - It is not (8-1)+(8-2), it is F(8-1)+F(8-2). ie. the Fibonacci function of those index values. See 3:40 for the chart showing the Fibonacci sequence. F(8-1) = F(7) = 13 F(8-2) = F(6) = 8
If you don't already you should consider doing Udemy courses. Your ability to explain things clearly while also preemptively understanding potential questions and answering them in your trainings is extremely good. Kudos to you!
8:15 iteration is not twice as fast as recursion, it is thousands, if not millions of times faster as you add higher numbers because recursive is O(2n), meaning that every item makes it quadratically slower. Another downside of the recursive approach is that there is a pretty low upper bound limit until you hit a maximum recursion depth limit, which will happen even when using memoization
hahahaha me too!!! I remember how my university instructors were encouraging to use it all the time so I assumed it's applicable to Python as well! 😅 In other programming languages, recursion might actually save you both time and resources. However with Python - it's the other way around! 😉 Another important detail is when it comes to reliability - recursion always wins! so complex software will ALWAYS prefer it over iteration even in the case of Python! 😃
it's worth to add that the iterative method is less cpu consumming but is more memmory consuming as you calculate each number until you get the desired one, when in recursion you directly calculate the number you are looking for. recursion is pretty good to use along with threads, that way you can take a complex operation (something that would require quite a buch of proccesing power or computations and time) and rather than running it all straight forward you divide it in parts and make several threads (that will run concurrently) to compute each part making it way faster.
You can easily cut down on the memory usage of the iterative approach, in this example the new value is appended at the end of the list, for the next calculation though you only need the last two numbers, not the whole list. So all you really need to store is the last two values, then in the loop you set the second last value to the current last value and set the last value to the calculated value, then you repeat. So all you really need to store is 3 integers plus the index. This ends up being more memory efficient than the recursive version since the recursive version needs to store values on the stack for each function called. The iterative version also has a massive benefit over recursion in that the recursive version would cause a stack overflow if you entered too high a number as it calls lots of functions, whereas the iterative approach when optimised for memory usage only needs to store 3 values plus the index, regardless of the input number, it could continue on as high as the max size of the integer allows. This may not be much of an issue when using a desktop computer and a relatively small example like this but using anything with a small stack like embedded systems would have issues with stack overflows, hence recursion is mostly avoided in embedded systems.
it might be a very basic concept but it doesn't mean it's easy to understand. i liked your video because it's not recursion explanation with factorial, thxs
You can see a major difference between the iterative and recursive example. The iterative examples works its way through the loop continuing the calculation each time, the recursive example in its return statement calls two other copies of the function, so the program calculates Fibonacci(idx - 1), then it also calculates Fibonacci(idx - 2), the big issue here is that when it calculated Fibonacci(idx - 1) it also had to calculate Fibonacci(idx - 2) and then it calculates it again, so it had to calculate Fibonacci(idx - 2) twice, this happens for every level of recursion, which is what makes it significantly slower than iteration since it is repeating the same calculations many times. If you manually expanded the recursion this would be easy to see. With the iterative example it calculates one value and then moves directly onto the next, it doesnt repeat any calculations and onto has to deal with jumps, not function calls or putting values on the stack, this is another reason it is significantly faster. The difference in speed was relatively small (only 3x) in your example here using small numbers but I ran the code myself, I ran it with an input of 40 and the iterative approach took 0.0 seconds, whilst the recursive approach took 30.17 seconds, so as the input increases so does the speed difference, I am not 100 % sure but I think the time increase of the recursive approach is exponential whereas for the iterative approach it is linear. Partly confirmed by the fact that running it with an input of 41 makes iterative still take 0.0 seconds whilst recursive takes 48.88, so it doesnt double every time but it is a large increase, around 1.5x per 1 that the input increases by. I know others in the comments have mentioned that the iterative approach uses more memory but it doesnt have to, for the current calculation all you really need are the last two numbers in the sequence, so all you need to store is the last two numbers in the sequence plus a temporary variable for the calculation, not the whole sequence like shown in this example, so you could get the memory usage down to 3 integers and the index plus whatever variable you use for iteration. Another benefit of the memory optimisation is that it decreases the time that it takes drastically, when it stores the whole sequence it has to append the list every time, this takes time since it needs to allocate memory, using the memory optimised version it doesnt need to do this so is faster, when run with an input of 100000, the example given here needs to store 100002 values, whereas the memory optimised one stores 2 values, this lead to the example given here taking 0.31 seconds and the memory optimised version taking 0.12 seconds, this difference increases as the input size increases. Increasing the input to 300000 the iterative example given here used multiple gigabytes of memory whereas the memory optimised example just used the same amount of memory it always uses, also the speed of the given example was 26.08 seconds compared to 1.57 seconds for the memory optimised example. Increasing the input to 1,000,000 created a memory error, on a system with 32 GB of ram. One way to decrease the speed whilst also storing the whole sequence would be to allocate an array the size of the index right at the start, then you dont need to worry about expanding the array or list later, this doesnt get rid of the fact that it uses lots of memory though. A big problem with recursion is that as the input gets bigger the number of functions that need to be called increases drastically, you are pretty much doubling it for every time you increase the input by 1, so this can quickly end up with thousands of function calls and ending up with a stack overflow, with the iterative approach when memory optimised and only storing the last two values, the memory usage of the function is the same regardless of the input. This may not be much of an issue with small examples and systems with large-ish stacks, like desktop PCs but once you get into systems with small stacks then recursion becomes a problem, this is especially relevant in embedded systems and microcontrollers which typically have very small stacks and very low RAM and flash storage, where having a MB of RAM is a lot. This is also where you will see big difference in speed too since the processors are slower and often dont have all the functions a desktop computer would, like floating point units. Hence recursion is for the most part to be avoided in embedded systems. It would be very interesting to see what kind of optimisations could be done to the recursive version of this algorithm to speed it up and potentially reduce the number of function calls. Maybe it could be done with calling a single function per recursion rather than branching into 2.
"One way to decrease the speed whilst also storing the whole sequence would be to allocate an array the size of the index right at the start, then you dont need to worry about expanding the array or list later, this doesnt get rid of the fact that it uses lots of memory though" Are you speaking about preallocation? Btw, thanks for this beautiful analysis, your comment is full of interesting wisdom :)
@@Gladiator15 yes I was. Allocating the array at its needed size once at the start rather than appending every iteration. It still uses lots of memory this way though.
If you want to improve the performance of the fibonacci function or something similar (factorials for example) you may want to use momoization to store previously computed numbers and use them rater than recomputing them.
Thats the iterative way, well, sort of. In the iterative approach you calculate each Fibonacci number (for this example) until you get to the index you want and return it, now you have an array or collection of indexed Fibonacci numbers that you will reuse the next time the function is invoked, so if you call it with and index for which it has already calculated the value then it would simply return it from the array..
Nice subject! My view is that it depends. If you need too much nested loops, or you cannot know in advance how many nested loops you will need, recursion is the best (file system searching, user interface controls, trees in general...). If you need one or two nested loops (maybe three or four), then loops is good enough (and runs faster!)
I absolutely agree Jonny! 😀 In some cases it's more important for the app to be reliable than fast! I'm not a big fan of nested loops in general, I always try using a zip() function to parse over 2 lists at once... otherwise the code gets so convoluted and my OCD gets under my skin😅 hahahahaha
@@PythonSimplified Yes, agreed! And the more time elaps, the more computers get faster, and then that advantage of for loops will became less and less important.
omg that was such a concise and each to understand explanation about recursion! I didn't totally get the fibonacci part but your examples have given me confidence about the basics of writing a recursive function!
Good explanation BUT - why does everyone use Fibonacci numbers to explain recursion? Aren't there any other examples in all of computer science that can effectively demonstrate recursion?
Sounds quite complex! it's kind of a pyramid structure, no? 😀 You recruit new people and then you get a percentage of their sales, then if your people recruit new people - you get a smaller percentage of the new peoples' sales... right? I've been offered to join these type of ventures many times in the past... but I was always wondering if the only people who buy their products are the new recruits 😆 hahahaha it's usually the case 😅
Great video but there's some extra information about recursion limitation. The biggest problem of recursion is related to call stack recursion deep level. Each time a function is called, their parameters, return variables and the next instruction address (the next address after the called function), are stored on stack (maybe some extra information too), so a lot of memory is needed to be stored on stack to call a function (now try to imagine call a function recursively several times). Well, the stack is limited at compile time if you're using a code managed by a virtual machine, interpreters or even a native code, so if you are calling a function recursively you'll reach this limit faster depending on architecture your software was written or running (x64, ARM....). Some C or C++ compilers limits, by default, this deep level of stack to something between 360~400 recursion levels. In Python I think this level is something up to 997.....so try to run your example (recursive function) passing a 998 index number or even a higher value. I think that Python runtime will complain something like (stack overflow) or even a recursion error. Changing this stack size is possible but the new limit can be reached in future scenarios, so using recursion is something unsafe for cases where recursion limits are higher. Regards
I've been seeing your videos pop up on my feed quite a bit lately, and this is my first time watching one, and I have a mix of compliments and criticisms. First, the compliments. Your presentation skills are quite good; you speak clearly, confidently, and concisely, as opposed to a number of other creators who tend to ramble a bit and then fail to edit those ramblings out. Your editing is also quite visually engaging, and it supports the points you're making quite well. However, I can't overstate what a massive L take it is to come to the blanket conclusion, based on a single test comparing two functions that are written very differently from each other, that iteration is faster than recursion. Even ignoring the fact that the functions are written so differently, a single test using only a single input is not very illuminating; you would need to run each function with a variety of inputs, and do multiple tests, in order to come to any kind of conclusion. But let's come back to the fact that the functions are written so differently from each other, because a brief examination makes it obvious that the recursive example is extremely disadvantaged because it has to run far more computations because it's doubly recursive, meaning it calls itself twice at the end of each call, so that's at least twice as much computation right there. This is in stark contrast to the iterative example, which holds previously computed values in a list, which takes a massive load off the CPU at the expense of some RAM, and that RAM cost might get significant when called with a large index (though in practice, a list of integers is quite unlikely to cause memory issues; this would be a bigger concern when holding a list of more complex objects) but in the example shown here, the iterative example is at a huge advantage, which is definitely majorly skewing the results of your test. Also, my understanding is that time.perfcounter() is better to use for measuring performance than time.time(). I don't know why that is, but that's the advice I've always heard. On a much less serious note, I'm simply SHOCKED and APPALLED at your use of PascalCase for a function name.
Might be worth mentioning that you can include recursive functions within for loops and, to overcome timing issues in recursion you can use lru_cache from the functions library.
Thank you so much Eyal!!! 😁😁😁I'm always super happy to read your comments! Unfortunately, I'm not coming for a visit anytime soon... I'm waiting for the Covid madness to end! as it seems now, I'm stuck in Canada for years to come... well at least it's a nice place to be stuck in! 😵 אגב היה קצת מוזר בצ'אט היום חחחחחחח יש תמיד שתיקה מביכה אחרי שאני כותבת שגדלתי בישראל 😅 זה לא נעים לשמוע שאנשים שופטים אנשים אחרים על סמך מוצאם... אבל בסוף כולם הסכימו לא לערב פוליטיקה אז זה היה דווקא נחמד 😁 (סתם מעדכנת אותך למקרה שיצאת מהפרימיירה חחחחחחח)
@@davidcalebpaterson7101 Hebrew is a tough one to learn, everything is upside down! (or right side down? maybe right side left?? hahahaha 😅) Russian is probably even tougher but nothing is easier than Python 😉 that I guarantee!
When i use the time module (like your example) in spyder my time results are both 0, when I use timeit with timeit.default_timer() the time is correct, I don't get it?
Thanks for the workaround with timeit.default_timer(). Yeah I couldn't get the time.time() to give a difference in time. Result is always 0. I know the time module is imported as normal because it is giving me a time read out when I use it by itself, but just returns the same time when used twice in same instance.
Do you happen to have any other videos discussing recursion? This is what I’m learning for college next week and I’m trying to get a head start. Thank you regardless.
Potter is my second favourite magician in the world!! (Gendalf is first of course! but I couldn't find any fancy Gendalf shirts 😅 hahahaha) And no worries about the premieres - school is always more important!!! I'll try to premiere vids on Saturdays too so I don't mess with your teachers hahahaha
@@PythonSimplified Hahahaha no way, I just saw, hackers stole 1.5B data from the Facebook with web scraping xDDD. I bet they watched your tutorials HAHA.
Yikes! I'll have to watch this one a couple more times. I guess I struggled because I don't really see a practical, real-world use for this... yet. Can you give me a situation where using recursion might actually be applied outside of science or advanced math? This would help a lot. Thanks.
very nice, thanks a lot . something new for me .......... when i run code EvenNums(8) in debugging mode. return base value num=2, but now conde run continue and again start value num=4 then num=6 then num=8 then finish .. ........................... my question is why run code when base value comes 2 ?
Great question, AMA! 😃 The EvenNums() function is actually not useful at all if we're just printing the output. However, if instead of printing, we append the values to a list - it makes much more sense because it will return lists of a different length when you change the argument from "8" to "20" or "200" or "2000000". I've used it as an example just to demonstrate how to create a recursive function... it seemed like a good starting point 🙂
Thank you! I was born in Crimea so it comes natural! 😉 I'll definitely check out KivyMD's new builder! I had no idea it came out! thanks for letting me know 😃
@@PythonSimplified ofcourse mariya I like every tutorial of yours❤️... I'm a beginner and I would like to have skills like you😂😂... don't know how much time it will take to learn
@@backrank3264 the more apps you build - the more experience you gain! 😀 I think the best way to learn is to create your own projects and combine them with topics that you find interesting. When you go through the process of planning, designing and programming your own app - it is so rewarding in the end! it's definitely worth every minute of debugging! 😉 And the best part is - once you're done, you can use this project as part of your resume! it will show your supreme Python skills to potential employers and you might be able to apply them in a professional environment! 😀😀😀 I truly think that learning Python (or other programming languages) is the best hobby anyone can have! one day this hobby can turn into a successful career, especially if you're interested in AI and ML! 😊 Best of luck on your Python journey!
@@PythonSimplified yeahhh...mariya You finally got my dream vision of my career in AI and ML...And I'm an Automobile engineer but I like coding...that is is why I'm learning Python...and thank you very much for your valuable time of your replies for my comments...thanks Again ❤️..love from India 🇮🇳...
Awesomeeeeeeee Mariya!!! Thankyou so much, I am non CS final year student I tried many videos few days back and I thought to give up learning programming but today I am thorough with this concept through your video, you had really broke it down in a way that I can understand it very easily and clearly, all your videos' are giving me more confidence to learn every topics . Thankyou soo much you are doing a great Job.... Thankyou so much once again. I'm editing to write this 😉😉 by the way you are beautiful 🤣🤣🤣🤣🤣🤣
So basically you want to recall the same function, but if the parameter you put in is the same, nothing is going to change right? So since we want even numbers, and given that the parameter (num) is an even number than it’s given that you want to subtract to eight for example, 2 so you get 4 which is what you want the function to print and so on until the base case when the function stops.
Thank you so much Matias! I'm happy to hear that! 😁😁😁 We'll definitely have many more computer science concept tutorials in the near future! I find that combining code example with illustrations is a great way to learn! 😀
Hi, thanks for the detailed video! however i have a question. in the function nowhere we have defined that fibo (idx) = Fibo(idx-1) + fibo(idx-2). How come the function is working then?
Awesome, thanks for another great lesson. Sorry I missed the live lesson today. This is useful for the next stage in making my programming language, the compiler has to break down statements into small parts to evaluate them. I have to keep things simple.
Hey Heeeeey Tobs, great to see you! we missed you indeed in the live-chat! 😀 (we almost got into politics! I was a bit scared for a moment hahaha 😅) Complex programs definitely work much better with recursion! it's substantially slower but there's a much lower chance for unexpected things to happen! With simple apps it's still a bit of an overkill, but the bigger the task - the more it makes sense to switch to recursion 😉
@@Tobs_ I always try to avoid politics, but unfortunately in the past 2 years it became an impossible task! 😂 I used to think that all politicians are liars... now I think they're all control thirsty psychopat liars and judging by what's going on in the world - it's only getting worse! 🤪
@@Tobs_ hahahahaha it's too big of a responsibility for someone who so far was only responsible for a cat! 😅 Plus, I would push for Python to become the official language of the world and it's hard to speak with colons and curly brakets hahahahaha 🤣🤣🤣 the world is just not ready for my powers yet!!!! otherwise I'd already be flying my dragon all over the place! hahahaha XD
I've been watching few of your vids.... very well presented, great content, timings good you will do well as time goes on. I've spotted many youtubers early on sub 10K with now over 500K+. You will be one of those, hitting 100K early 2022 and +300K 2023 if you keep vids coming.
By definition, is a local variable local to one call, or available to all calls in the recursion? The last definition is what I’m gathering here, or was there globally defined variables, for example, in there recursive fibonacci code. Very good explanation of recursion in python, thanks.
That's a REALLY good question, Carlos! 😃😃😃 Python has a default recursion limit of 1000, however - you can always increase it if needed with: sys.setrecursionlimit(2000) or any other value you require 🙂 If you're curious, you can find more information on this thread: stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it
iteration was faster because in recursion it had to also do the conditionals + the sum of last two, but in iteration it only takes last two from the list. This is at least how I make the correct guess , so I may be wrong
### i was practicing on w3schools and i'm still confused on the output of this sample when you type this in def tri_recursion(k): if(k > 0): result = k + tri_recursion(k - 1) print(result) else: result = 0 return result print("Recursion Example Results:") tri_recursion(6) ### I dont see how the output values is this Recursion Example Results: 1 3 6 10 15 21 ### i understand that it's going to out put 6 values because it started with 6 and ends at 0, but how are the output values calculated? maybe this was just a confusing example.
Think she explained it well enough to comprehend idk about you tho lol All her videos is well explained with detailed examples a kid could comprehend. As a tutorial should be from someone with no knowledge of topic. You don't want to explain to advanced so noobs can't understand. She's a lovely teacher
You always get that hater with no videos no subscribers trying to troll on an accomplished video 💀 🤣. So you make a video of you explaining the definition then.
@@flipinfin Really? Are you sure you understood recursion by watching this? There's way better videos explaining it on youtube. And I am not hating her. Why should I? I honestly can't see why people are so impressed by the 'explanation' that doesn't explain anything. She just wrote a few basic recursive functions on her computer and showed us their respective outputs, that's it. But she didn't show what was REALLY going under the hood, how we ACTUALLY got those outputs.
@@ithinkthereforeitalk935 actually yes and its mostly used for computer science solving problems in slices 1 at a time ya bot lol. Her channel called python simplified hope off her d dude. Go troll somewhere else
Hey, can you please explain the calculation at 5.20min
Fibonacci(idx-1)+Fibonacci(idx-2), as I understand if our index is 8, then ((8-1)+(8-2)), which equals 13, how did you get 21. I know that the Fibonacci number at index 8 is 21, but I don't understand this from calculation point....
Thank you!
Hi Maksims! This is a really good question, thank you for your comment! 😃
When it comes to implementing recursion in programming - we need to consider something called a "call stack", which is responsible for managing function calls.
Every time a function is called - all its variables and arguments are being inserted into a "stack frame" which is a location in memory inside the call stack. The stack frame remains there until the function terminates (a certain value is returned).
The Fibonacci example is a bit complex, so here's a better starting point (also recursive):
def my_sum(n):
if n == 0:
return n #base case
else:
return n + my_sum(n-1)
my_sum(3)
STEP 1: the function returns 3 + my_sum(2) so we push it to the stack frame.
STEP 2: since the return statement above includes another call to my_sum(n-1) - we create a new stack frame, but this time passing (n-1) as an argument instead of n. so then our call stack receives a stack frame of 2 + my_sum(1) and it's placed now at the top of the stack.
STEP 3: because the return statement in STEP 2 also includes a call to my_sum(n-1) - we again push a new stack frame but this time of 1 + my_sum(0)
STEP 4: we finally reach the base case where n==0, so we return 0. Since there are no more calls to my_sum and we reached the end of the recursion - the stack frames will now start popping one after the other and returning their values to their "parent" function.
So the first function we called my_sum(3) will receive the values of its return statement LAST!
The first function that receives its return values is my_sum(0), only then my_sum(1) can receive its return values, and only then my_sum(2) can receive its return values.
So the outcome of one function depends on the outcome of all its previous functions, and we can only calculate it after we calculate all the previous outcomes 😊
It's more complex with the Fibonacci function as it involves 2 function calls in the return statement so it makes things much harder to follow 😵But I did find a very handy tutorial explaining the call stack in a relation to Fibonacci:
realpython.com/fibonacci-sequence-python/#visualizing-the-memoized-fibonacci-sequence-algorithm
I hope it helps! 😀
@@PythonSimplified Thank you very much for your help!
@@PythonSimplified Thank you so much! I've been doing online and app courses in Python, and I just couldn't grasp recursion. This helped immensely! Thank you!
"((8-1)+(8-2)), which equals 13, how did you get 21" - It is not (8-1)+(8-2), it is F(8-1)+F(8-2). ie. the Fibonacci function of those index values. See 3:40 for the chart showing the Fibonacci sequence.
F(8-1) = F(7) = 13
F(8-2) = F(6) = 8
@@PythonSimplified excellent reply
If you don't already you should consider doing Udemy courses. Your ability to explain things clearly while also preemptively understanding potential questions and answering them in your trainings is extremely good. Kudos to you!
Thanks! Super awesome tutorials. Helping me to connect dots and feel like I can do this.
8:15 iteration is not twice as fast as recursion, it is thousands, if not millions of times faster as you add higher numbers because recursive is O(2n), meaning that every item makes it quadratically slower. Another downside of the recursive approach is that there is a pretty low upper bound limit until you hit a maximum recursion depth limit, which will happen even when using memoization
You know she's a badass when the computer warned her about battery levels less than 3% and she was like .... *meh*
I was head faked, I totally thought recursion was going to win 😂 thanks for the explanation
hahahaha me too!!! I remember how my university instructors were encouraging to use it all the time so I assumed it's applicable to Python as well! 😅
In other programming languages, recursion might actually save you both time and resources. However with Python - it's the other way around! 😉
Another important detail is when it comes to reliability - recursion always wins! so complex software will ALWAYS prefer it over iteration even in the case of Python! 😃
@@PythonSimplified Always such great info. Thank you!
it's worth to add that the iterative method is less cpu consumming but is more memmory consuming as you calculate each number until you get the desired one, when in recursion you directly calculate the number you are looking for.
recursion is pretty good to use along with threads, that way you can take a complex operation (something that would require quite a buch of proccesing power or computations and time) and rather than running it all straight forward you divide it in parts and make several threads (that will run concurrently) to compute each part making it way faster.
You can easily cut down on the memory usage of the iterative approach, in this example the new value is appended at the end of the list, for the next calculation though you only need the last two numbers, not the whole list. So all you really need to store is the last two values, then in the loop you set the second last value to the current last value and set the last value to the calculated value, then you repeat. So all you really need to store is 3 integers plus the index. This ends up being more memory efficient than the recursive version since the recursive version needs to store values on the stack for each function called.
The iterative version also has a massive benefit over recursion in that the recursive version would cause a stack overflow if you entered too high a number as it calls lots of functions, whereas the iterative approach when optimised for memory usage only needs to store 3 values plus the index, regardless of the input number, it could continue on as high as the max size of the integer allows. This may not be much of an issue when using a desktop computer and a relatively small example like this but using anything with a small stack like embedded systems would have issues with stack overflows, hence recursion is mostly avoided in embedded systems.
it might be a very basic concept but it doesn't mean it's easy to understand. i liked your video because it's not recursion explanation with factorial, thxs
you really have created one of the most high value concise channels on compSCI and python, thank you !
You can see a major difference between the iterative and recursive example. The iterative examples works its way through the loop continuing the calculation each time, the recursive example in its return statement calls two other copies of the function, so the program calculates Fibonacci(idx - 1), then it also calculates Fibonacci(idx - 2), the big issue here is that when it calculated Fibonacci(idx - 1) it also had to calculate Fibonacci(idx - 2) and then it calculates it again, so it had to calculate Fibonacci(idx - 2) twice, this happens for every level of recursion, which is what makes it significantly slower than iteration since it is repeating the same calculations many times. If you manually expanded the recursion this would be easy to see.
With the iterative example it calculates one value and then moves directly onto the next, it doesnt repeat any calculations and onto has to deal with jumps, not function calls or putting values on the stack, this is another reason it is significantly faster.
The difference in speed was relatively small (only 3x) in your example here using small numbers but I ran the code myself, I ran it with an input of 40 and the iterative approach took 0.0 seconds, whilst the recursive approach took 30.17 seconds, so as the input increases so does the speed difference, I am not 100 % sure but I think the time increase of the recursive approach is exponential whereas for the iterative approach it is linear. Partly confirmed by the fact that running it with an input of 41 makes iterative still take 0.0 seconds whilst recursive takes 48.88, so it doesnt double every time but it is a large increase, around 1.5x per 1 that the input increases by.
I know others in the comments have mentioned that the iterative approach uses more memory but it doesnt have to, for the current calculation all you really need are the last two numbers in the sequence, so all you need to store is the last two numbers in the sequence plus a temporary variable for the calculation, not the whole sequence like shown in this example, so you could get the memory usage down to 3 integers and the index plus whatever variable you use for iteration. Another benefit of the memory optimisation is that it decreases the time that it takes drastically, when it stores the whole sequence it has to append the list every time, this takes time since it needs to allocate memory, using the memory optimised version it doesnt need to do this so is faster, when run with an input of 100000, the example given here needs to store 100002 values, whereas the memory optimised one stores 2 values, this lead to the example given here taking 0.31 seconds and the memory optimised version taking 0.12 seconds, this difference increases as the input size increases.
Increasing the input to 300000 the iterative example given here used multiple gigabytes of memory whereas the memory optimised example just used the same amount of memory it always uses, also the speed of the given example was 26.08 seconds compared to 1.57 seconds for the memory optimised example. Increasing the input to 1,000,000 created a memory error, on a system with 32 GB of ram.
One way to decrease the speed whilst also storing the whole sequence would be to allocate an array the size of the index right at the start, then you dont need to worry about expanding the array or list later, this doesnt get rid of the fact that it uses lots of memory though.
A big problem with recursion is that as the input gets bigger the number of functions that need to be called increases drastically, you are pretty much doubling it for every time you increase the input by 1, so this can quickly end up with thousands of function calls and ending up with a stack overflow, with the iterative approach when memory optimised and only storing the last two values, the memory usage of the function is the same regardless of the input. This may not be much of an issue with small examples and systems with large-ish stacks, like desktop PCs but once you get into systems with small stacks then recursion becomes a problem, this is especially relevant in embedded systems and microcontrollers which typically have very small stacks and very low RAM and flash storage, where having a MB of RAM is a lot. This is also where you will see big difference in speed too since the processors are slower and often dont have all the functions a desktop computer would, like floating point units. Hence recursion is for the most part to be avoided in embedded systems.
It would be very interesting to see what kind of optimisations could be done to the recursive version of this algorithm to speed it up and potentially reduce the number of function calls. Maybe it could be done with calling a single function per recursion rather than branching into 2.
"One way to decrease the speed whilst also storing the whole sequence would be to allocate an array the size of the index right at the start, then you dont need to worry about expanding the array or list later, this doesnt get rid of the fact that it uses lots of memory though"
Are you speaking about preallocation? Btw, thanks for this beautiful analysis, your comment is full of interesting wisdom :)
@@Gladiator15 yes I was. Allocating the array at its needed size once at the start rather than appending every iteration. It still uses lots of memory this way though.
If you want to improve the performance of the fibonacci function or something similar (factorials for example) you may want to use momoization to store previously computed numbers and use them rater than recomputing them.
Thats the iterative way, well, sort of. In the iterative approach you calculate each Fibonacci number (for this example) until you get to the index you want and return it, now you have an array or collection of indexed Fibonacci numbers that you will reuse the next time the function is invoked, so if you call it with and index for which it has already calculated the value then it would simply return it from the array..
Best teacher in the world hand down
Nice subject! My view is that it depends. If you need too much nested loops, or you cannot know in advance how many nested loops you will need, recursion is the best (file system searching, user interface controls, trees in general...). If you need one or two nested loops (maybe three or four), then loops is good enough (and runs faster!)
I absolutely agree Jonny! 😀 In some cases it's more important for the app to be reliable than fast! I'm not a big fan of nested loops in general, I always try using a zip() function to parse over 2 lists at once... otherwise the code gets so convoluted and my OCD gets under my skin😅 hahahahaha
@@PythonSimplified Yes, agreed! And the more time elaps, the more computers get faster, and then that advantage of for loops will became less and less important.
I need that voice, I want my navigation, Siri, audiobooks and therapists to have that voice
def tail_rec_fibonacci(idx, a=0, b=1):
if idx == 0:
return a
return tail_rec_fibonacci(idx-1, b, a+b)
I am taking the Coursera course and you explain things way better than the instructor on there
omg that was such a concise and each to understand explanation about recursion! I didn't totally get the fibonacci part but your examples have given me confidence about the basics of writing a recursive function!
Good explanation BUT - why does everyone use Fibonacci numbers to explain recursion? Aren't there any other examples in all of computer science that can effectively demonstrate recursion?
Ny most recent use of recursion was to print MLM trees. Basically feeding the deeply nested JSON data into the recursive function.
Sounds quite complex! it's kind of a pyramid structure, no? 😀
You recruit new people and then you get a percentage of their sales, then if your people recruit new people - you get a smaller percentage of the new peoples' sales... right?
I've been offered to join these type of ventures many times in the past... but I was always wondering if the only people who buy their products are the new recruits 😆 hahahaha it's usually the case 😅
I love the visual aids, I really makes a world of difference
It's a fact I didn't know. I'm so thankful.
I hope there will be a day when it can be applied.
Great video but there's some extra information about recursion limitation.
The biggest problem of recursion is related to call stack recursion deep level. Each time a function is called, their parameters, return variables and the next instruction address (the next address after the called function), are stored on stack (maybe some extra information too), so a lot of memory is needed to be stored on stack to call a function (now try to imagine call a function recursively several times).
Well, the stack is limited at compile time if you're using a code managed by a virtual machine, interpreters or even a native code, so if you are calling a function recursively you'll reach this limit faster depending on architecture your software was written or running (x64, ARM....).
Some C or C++ compilers limits, by default, this deep level of stack to something between 360~400 recursion levels.
In Python I think this level is something up to 997.....so try to run your example (recursive function) passing a 998 index number or even a higher value.
I think that Python runtime will complain something like (stack overflow) or even a recursion error.
Changing this stack size is possible but the new limit can be reached in future scenarios, so using recursion is something unsafe for cases where recursion limits are higher.
Regards
@@noomade I think stack is a resource "more finite" than others, so is something that happens on Haskell or Rust too.
Wow your subs have doubled since the last time I checked in. Finally people are seeing the effort and excellent teaching of yours, well done!
Finally I understand recursion, Thank you
I've been seeing your videos pop up on my feed quite a bit lately, and this is my first time watching one, and I have a mix of compliments and criticisms.
First, the compliments. Your presentation skills are quite good; you speak clearly, confidently, and concisely, as opposed to a number of other creators who tend to ramble a bit and then fail to edit those ramblings out. Your editing is also quite visually engaging, and it supports the points you're making quite well.
However, I can't overstate what a massive L take it is to come to the blanket conclusion, based on a single test comparing two functions that are written very differently from each other, that iteration is faster than recursion. Even ignoring the fact that the functions are written so differently, a single test using only a single input is not very illuminating; you would need to run each function with a variety of inputs, and do multiple tests, in order to come to any kind of conclusion.
But let's come back to the fact that the functions are written so differently from each other, because a brief examination makes it obvious that the recursive example is extremely disadvantaged because it has to run far more computations because it's doubly recursive, meaning it calls itself twice at the end of each call, so that's at least twice as much computation right there. This is in stark contrast to the iterative example, which holds previously computed values in a list, which takes a massive load off the CPU at the expense of some RAM, and that RAM cost might get significant when called with a large index (though in practice, a list of integers is quite unlikely to cause memory issues; this would be a bigger concern when holding a list of more complex objects) but in the example shown here, the iterative example is at a huge advantage, which is definitely majorly skewing the results of your test.
Also, my understanding is that time.perfcounter() is better to use for measuring performance than time.time(). I don't know why that is, but that's the advice I've always heard.
On a much less serious note, I'm simply SHOCKED and APPALLED at your use of PascalCase for a function name.
This was the best explanation I coud find.
I will have to watch this a least one more time to fully comprehend this recursion thing. Great video as always!!!!!!!!!!!!
the editing level increased, i like it 💞
Thank you so much! I got a fancy new camera so everything looks extra crisp 😉
Might be worth mentioning that you can include recursive functions within for loops and, to overcome timing issues in recursion you can use lru_cache from the functions library.
Can't believe just when i search for recursion you just happen to upload a video 5 hours ago Hahaha, great vid! thanks as always great content. :D
hahahaha that's awesome! so happy I was right on time! 😃😃😃
Thank you so much for the lovely comment! 🙂
I wish i had a gorgeous teacher like this lol
I Have Been Waiting For This one, sweetie; Love You and This Fantastic Channel ~
Thank you so much! 😀😀😀
‘To understand recursion, you must first understand recursion’ - Recursion Explained ;-P
hahahahahahaha this is the best definition of recursion I've seen so far! 🤣🤣🤣
Very useful for user validation
Running tasks in parallel 😎
Thumbs up for the t-shirt 😁
Great work as always 👍
5:25 "perfetto, bravo!" Ahahaha glad to hear you speaking italian!
Grazie iVoz! I've said "Fibonacci" so many times that it woke up the Italian in me! 😄 hahahaha
Having fun while learning python and programming. The best teacher 🙂
Thank you so much Eyal!!! 😁😁😁I'm always super happy to read your comments!
Unfortunately, I'm not coming for a visit anytime soon... I'm waiting for the Covid madness to end! as it seems now, I'm stuck in Canada for years to come... well at least it's a nice place to be stuck in! 😵
אגב היה קצת מוזר בצ'אט היום חחחחחחח יש תמיד שתיקה מביכה אחרי שאני כותבת שגדלתי בישראל 😅 זה לא נעים לשמוע שאנשים שופטים אנשים אחרים על סמך מוצאם... אבל בסוף כולם הסכימו לא לערב פוליטיקה אז זה היה דווקא נחמד 😁
(סתם מעדכנת אותך למקרה שיצאת מהפרימיירה חחחחחחח)
@@PythonSimplified חחח כן תיארתי לעצמי,אני מניח שתמיד יהיו מקרים כאלה שמדובר בפלטפורמה בין-לאומית, העיקר שאת נהנת ממה שאת עושה. kapara aleih😉
@@PythonSimplified hebrew wow, I didn't see that coming. I know how to read and some words. I am constantly learning new languages including python 😁.
@@eyal4 חחחחח וואלה אין תלונות בינתיים! גם לא היו הרבה מקרים של "אוי ואבוי את מישראל!", זה בדרך כלל הפוך - אנשים מהמזרח התיכון דווקא מבסוטים מזה! 😊
@@davidcalebpaterson7101 Hebrew is a tough one to learn, everything is upside down! (or right side down? maybe right side left?? hahahaha 😅)
Russian is probably even tougher but nothing is easier than Python 😉 that I guarantee!
Nice video. I was working on solving a Fibonacci algorithm problem recently so it was good to see this video. Nice t-shirt too!
That's awesome! Sounds like it's a great timing! 😃
And thank you, Harry Potter rocks! 😁
When i use the time module (like your example) in spyder my time results are both 0, when I use timeit with timeit.default_timer() the time is correct, I don't get it?
Thanks for the workaround with timeit.default_timer(). Yeah I couldn't get the time.time() to give a difference in time. Result is always 0. I know the time module is imported as normal because it is giving me a time read out when I use it by itself, but just returns the same time when used twice in same instance.
just by watching ur videos....i love you !!!
5:17 As an Italian I didn't expect it
Do you happen to have any other videos discussing recursion? This is what I’m learning for college next week and I’m trying to get a head start. Thank you regardless.
Thanks a lot.. .. It helps me than Mark Lutz's book. ....
I love your Harry Potter t-shirt!. Our teacher make us stay longer at school so I wasn't able to come to the premiere ://. However, amazing video.
Potter is my second favourite magician in the world!! (Gendalf is first of course! but I couldn't find any fancy Gendalf shirts 😅 hahahaha)
And no worries about the premieres - school is always more important!!! I'll try to premiere vids on Saturdays too so I don't mess with your teachers hahahaha
@@PythonSimplified Hahahaha no way, I just saw, hackers stole 1.5B data from the Facebook with web scraping xDDD. I bet they watched your tutorials HAHA.
Yikes! I'll have to watch this one a couple more times. I guess I struggled because I don't really see a practical, real-world use for this... yet. Can you give me a situation where using recursion might actually be applied outside of science or advanced math? This would help a lot. Thanks.
5:18 perfetto, brava!
Many thanks, You have simplified my life.
very nice, thanks a lot . something new for me .......... when i run code EvenNums(8) in debugging mode. return base value num=2, but now conde run continue and again start value num=4 then num=6 then num=8 then finish .. ........................... my question is why run code when base value comes 2 ?
Great question, AMA! 😃
The EvenNums() function is actually not useful at all if we're just printing the output. However, if instead of printing, we append the values to a list - it makes much more sense because it will return lists of a different length when you change the argument from "8" to "20" or "200" or "2000000".
I've used it as an example just to demonstrate how to create a recursive function... it seemed like a good starting point 🙂
@@PythonSimplified thank again for your reply ..........
beauty and brains at work. good job
I wished you have a twitter account , theer's a very good tech community there
Awesome explanation. Thank you for making these videos! Very, Very Helpful!!!
Thank you so much Chris! Super happy to help! 🙂🙂🙂
Please have a live Q&A session after this so that we could clarify our doubts.
Hi Kejin, sounds good! I'll try to go live soon 😊
@@PythonSimplified That would be awesome. And try to give a some time so that everyone can be ready with our doubts and clarifications.
I love your explanations !!
Thank you so much Gabriel! 😃
Thanks 🙏 , I have been confused for a long time. What a way of explanation with your examples.
why am I getting different results for print(EvenNums(8)) and EvenNums(8) ? @ 1:54
Fantastic! You made this topic crystal clear and very easy to grasp..thank you
very good explanation ... and 😱 wow i love when you speak italian 😍
Grazie Luca!! Super glad you liked it! 😃😃😃
good pronunciation: матрёшка)).
subscribed when the video about kivyMD came out. they have a new kivyMD builder. like!!!
Thank you! I was born in Crimea so it comes natural! 😉
I'll definitely check out KivyMD's new builder! I had no idea it came out! thanks for letting me know 😃
Great lesson... Mariya ..I am a big fan of your classes and accent ❤️❤️
Thank you so much! I'm glad you like everything! 😁
@@PythonSimplified ofcourse mariya I like every tutorial of yours❤️... I'm a beginner and I would like to have skills like you😂😂... don't know how much time it will take to learn
@@backrank3264 the more apps you build - the more experience you gain! 😀 I think the best way to learn is to create your own projects and combine them with topics that you find interesting.
When you go through the process of planning, designing and programming your own app - it is so rewarding in the end! it's definitely worth every minute of debugging! 😉
And the best part is - once you're done, you can use this project as part of your resume! it will show your supreme Python skills to potential employers and you might be able to apply them in a professional environment! 😀😀😀
I truly think that learning Python (or other programming languages) is the best hobby anyone can have! one day this hobby can turn into a successful career, especially if you're interested in AI and ML! 😊
Best of luck on your Python journey!
@@PythonSimplified yeahhh...mariya You finally got my dream vision of my career in AI and ML...And I'm an Automobile engineer but I like coding...that is is why I'm learning Python...and thank you very much for your valuable time of your replies for my comments...thanks Again ❤️..love from India 🇮🇳...
Nice job with this video young lady. Perfecto! Bravo! in spanish. Love it!
Thank you so much Cantillano! 😀
I was actually aiming for Italian! (I've said Fibonacci too many times and it seemed appropriate 😁 hahahha)
I see 😊😊😊. The Italian language is almost the same as Spanish, my native language. Perfecto!!!
Awesomeeeeeeee Mariya!!! Thankyou so much, I am non CS final year student I tried many videos few days back and I thought to give up learning programming but today I am thorough with this concept through your video, you had really broke it down in a way that I can understand it very easily and clearly, all your videos' are giving me more confidence to learn every topics . Thankyou soo much you are doing a great Job.... Thankyou so much once again.
I'm editing to write this 😉😉 by the way you are beautiful 🤣🤣🤣🤣🤣🤣
Good simple explanation❤.....you just gained a subscriber
Superb! Well illustrated.
can we write recursive inside the object of a class?
You can watch mine too. The channel has both Python and R playlists.
my main issue is that im just stupid. i didnt even understand what EvenNums(num-2) is supposed to be. why -2? whats -2
So basically you want to recall the same function, but if the parameter you put in is the same, nothing is going to change right? So since we want even numbers, and given that the parameter (num) is an even number than it’s given that you want to subtract to eight for example, 2 so you get 4 which is what you want the function to print and so on until the base case when the function stops.
by the way i don’t think you’re stupid
i like very much this kind of tutorial!!
Thank you so much Matias! I'm happy to hear that! 😁😁😁
We'll definitely have many more computer science concept tutorials in the near future! I find that combining code example with illustrations is a great way to learn! 😀
Hi, thanks for the detailed video!
however i have a question. in the function nowhere we have defined that fibo (idx) = Fibo(idx-1) + fibo(idx-2). How come the function is working then?
Awesome, thanks for another great lesson. Sorry I missed the live lesson today. This is useful for the next stage in making my programming language, the compiler has to break down statements into small parts to evaluate them. I have to keep things simple.
Hey Heeeeey Tobs, great to see you! we missed you indeed in the live-chat! 😀
(we almost got into politics! I was a bit scared for a moment hahaha 😅)
Complex programs definitely work much better with recursion! it's substantially slower but there's a much lower chance for unexpected things to happen!
With simple apps it's still a bit of an overkill, but the bigger the task - the more it makes sense to switch to recursion 😉
@@PythonSimplified I have a family member who always talks politics, and it only ever causes division.. best avoided unless you are a politician.
@@Tobs_ I always try to avoid politics, but unfortunately in the past 2 years it became an impossible task! 😂
I used to think that all politicians are liars... now I think they're all control thirsty psychopat liars and judging by what's going on in the world - it's only getting worse! 🤪
@@PythonSimplified you would make a great world leader, you already supply me with an education and a job 👍
@@Tobs_ hahahahaha it's too big of a responsibility for someone who so far was only responsible for a cat! 😅
Plus, I would push for Python to become the official language of the world and it's hard to speak with colons and curly brakets hahahahaha 🤣🤣🤣 the world is just not ready for my powers yet!!!! otherwise I'd already be flying my dragon all over the place! hahahaha XD
Love your videos and charisma. God bless you 🙏🙌
I've been watching few of your vids.... very well presented, great content, timings good you will do well as time goes on. I've spotted many youtubers early on sub 10K with now over 500K+. You will be one of those, hitting 100K early 2022 and +300K 2023 if you keep vids coming.
By definition, is a local variable local to one call, or available to all calls in the recursion? The last definition is what I’m gathering here, or was there globally defined variables, for example, in there recursive fibonacci code.
Very good explanation of recursion in python, thanks.
Good. Love from india!
Love back from Canada! Namaste! 😀
Super helpful! Thank you!
Interesting, however that makes me wonder what is the stack size of python?
That's a REALLY good question, Carlos! 😃😃😃
Python has a default recursion limit of 1000, however - you can always increase it if needed with:
sys.setrecursionlimit(2000) or any other value you require 🙂
If you're curious, you can find more information on this thread:
stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it
@@PythonSimplified that is an awesome feature.
thanks very much for the explanation. I was having issues understanding recursion. Isn`t python convention snake case, though? thanks
Hey.... I liked your T-Shirt.!
Thank you! 😃
I have the opposite under Linux:
Recursion
21
3.0517578125e-05
Iteration
21
3.814697265625e-05
Cool! like at pure functional language
Hey Mariya, good subject for Today, Keep going, Waiting to see a lot more from your side.💪👍
Thank you so much, super happy you liked it! 😃😃😃
I heard that mesuring is best with perf counter, but i also just use time and i don't see much difference
Masha, do you do algorithmic trading?
This is fantastic, you are awesome!
thank you this helped so much! subbed :D
You help me a lot with my studies, thank you so much, the way you explain is perfect. Women in stem yas
Hey, isn’t time.perf_counter() used as a better alternative for time.time() ?
I really love your shirt 😍😎
Wonderful lesson; thanks.
Grazie for the this beautiful class!!
Thank you for this great explanation❤️
Great video. Thanks!
iteration was faster because in recursion it had to also do the conditionals + the sum of last two, but in iteration it only takes last two from the list. This is at least how I make the correct guess , so I may be wrong
thank you! you are great at explaning!
### i was practicing on w3schools and i'm still confused on the output of this sample
when you type this in
def tri_recursion(k):
if(k > 0):
result = k + tri_recursion(k - 1)
print(result)
else:
result = 0
return result
print("Recursion Example Results:")
tri_recursion(6)
### I dont see how the output values is this
Recursion Example Results:
1
3
6
10
15
21
### i understand that it's going to out put 6 values because it started with 6 and ends at 0, but how are the output values calculated? maybe this was just a confusing example.
thank you for your videos, you have a new sub.
Why in the else clause EvenNums(num-2) , why -2 ?
very good bueaitufl video
Recursion is great 👌
I agree, it's a really nice concept! 😊
She actually did not explain anything, don't understand why everybody is so pleased with the explanation.
Think she explained it well enough to comprehend idk about you tho lol All her videos is well explained with detailed examples a kid could comprehend. As a tutorial should be from someone with no knowledge of topic. You don't want to explain to advanced so noobs can't understand. She's a lovely teacher
You always get that hater with no videos no subscribers trying to troll on an accomplished video 💀 🤣. So you make a video of you explaining the definition then.
@@flipinfin Really? Are you sure you understood recursion by watching this? There's way better videos explaining it on youtube. And I am not hating her. Why should I?
I honestly can't see why people are so impressed by the 'explanation' that doesn't explain anything. She just wrote a few basic recursive functions on her computer and showed us their respective outputs, that's it. But she didn't show what was REALLY going under the hood, how we ACTUALLY got those outputs.
@@ithinkthereforeitalk935 actually yes and its mostly used for computer science solving problems in slices 1 at a time ya bot lol. Her channel called python simplified hope off her d dude. Go troll somewhere else
@@ithinkthereforeitalk935 if you can give a better explanation make your own tutorials. Why is you even here then ya bot 🤔 to troll
You are so great and its a réal pleaisure to ear you and to se you
Gond job 👍
Great explanations! Thank you.