Recursion in 100 Seconds

Key Takeaways

a recursive function is a function that calls itself inside of its own definition it's like having a dream inside of a dream when you have a recursive function that calls itself without anything to stop it you have created an infinite Loop the first function gets pushed onto the call stack the next one on top of it then another one on top of that and so on forever or until your runtime throws a stack Overflow error or the computer just runs out of memory so recursion is just another way to create a loop but infinite Loops aren't very useful in practice that's why recursive function have some sort of stopping point like some conditional logic that tells the function to stop calling itself when a condition has been met on an interview you might be asked to implement some code that finds a specific index in the Fibonacci sequence you'll notice a given index of the sequence is just the sum of the two previous values so how do we find index number 2023 your first thought might be to implement an iterative solution with a for Loop compute the Fibonacci value for each index until we get to the Target index of 2023 but then you're asked to implement a cursive solution we can do that by writing a function that starts with the index and then Works its way backwards until it gets to a base case of being less than or equal to one notice how we're calling the same function inside the function body and we're doing it twice there's a big problem here though it will Traverse down the entire sequence for every single index that's o to the N squ time complexity which is not good at all in the next video I'll explain how to improve this with memorization recursive functions are not the right choice in every situation but they are very good for tree and graph Travers rals this has been recursion in 100 seconds thanks for watching and I will see you in the next one