Recursion in software development

suppose you're digging through your grandma's attic and come across a mysterious locked suitcase grandma tells you that the key for the suitcase is probably in this other box this box contains more boxes with more boxes inside those boxes the key is in a box somewhere what's your algorithm to search for the key in this unit you'll learn about recursion recursion is used in many algorithms and is a building block for understanding later units in this course recursion can be used to solve the previous problem of searching for a key in nested boxes you will also learn to break down a problem into a base case and a recursive case i will be showing you a lot of code examples i highly recommend trying to run the code for yourself also at least once you should try to step through a recursive function with pen and paper to get a better sense of how recursive functions work this unit also includes a lot of pseudo code pseudocode is a high level description of the problem you're trying to solve in code it's written like code but it's meant to be closer to human speech let's get back to searching for a key in a box that contains boxes which contain other boxes first i'll show you a method to solve this problem that uses while loops then i'll show you a method that uses recursion here's the first method one make a pile of boxes to look through two while the pile isn't empty grab a box and look through it three if you find a key you're done four if you find a box add it to the pile of boxes to look through later five repeat here's the second method one look through the box two if you find a key you're done three if you find a box go to step one which approach seems easier to you the first way uses a while loop here's the first method using pseudocode first we make a pile of boxes to look through from the boxes in the main box while the pile is not empty choose a box to look through for each item in the box check if the item is another box if it is another box append or add it to the pile boxes we still have to look through if the item we found is a key then yell to everyone excitedly found the key keep checking the boxes until the pile is empty the second way uses recursion recursion is where a function calls itself here's the second way in pseudocode first we check the box passed into the function and go through each item in the box if the item is a box then we pass the box into the function again if the item is a key then yell to everyone excitedly found the key both approaches accomplish the same thing but the second approach seems cleaner a recursion is used when it makes the solution clearer there's actually no performance benefit to using recursion in fact loops are sometimes better for performance however people still use recursion since it often makes code easier to understand and look cleaner many important algorithms use recursion so it's important to understand because a recursive function calls itself it's easy to write a function incorrectly that ends up in an infinite loop for example suppose you want to write a function that prints a countdown you could write it recursively like this however if you run this code there's a problem the function will run forever if your code is in an infinite loop press ctrl c to kill the script when you write a recursive function you have to tell it when to stop recursing that's why every recursive function has two parts the base case and the recursive case the recursive case is when the function calls itself the base case is when the function doesn't call itself again so it doesn't go into an infinite loop here is the function from before with the addition of a base case the if i is less than or equal to 1 is the base case that is when the function will not call itself anymore in the else section is the recursive case that is what will keep happening if the base case has not yet been reached so unlike the last example this function will actually end