We introduce the topic of recursion and show the basic concepts of how to implement it in your code. We discuss how to prevent infinite recursion and then use the concept to create a few simple recursive functions.
- [Instructor] The next advanced concept I'll introduce you to is called recursion. This is a concept that you've probably heard of before, but maybe you've never seen it in action. Recursion is when a function calls itself. While doing this can very easily lead to an infinite loop, if we're not careful, it can also be used to solve certain problems very easily. Let's take a look at a very simple example using recursion. We're going to create a function that behaves like a for-loop without actually using a for-loop. What it'll do is start at whatever number we give it, and use recursion to count down from that number to zero, printing the results along the way.
So, let's call our function, countdown. Function, countdown. And our function is going to take an argument that specifies what number we want it to start at. We'll call our argument, start. And it will be an integer. So now, all we have to do is print the number. Print, start. And then call our function again, with our original argument minus one. So, countdown, start, start minus one. Now, if we run our function now, our coder will recurse infinitely because we forgot one important thing.
In recursion, we always have to tell our function when to stop. Without a stop condition, any recursive function will go on infinitely. Our stop condition in this case will be when the argument that the function receives is less than zero. At which point, we want it to return instead of calling itself again. So, what that will look like is this. If start is less than zero, return. Now, if we call our function, it will behave exactly as we want it to. Count down from 10.
And we see that our function counted down from 10 to zero. What if we wanted to count up instead? Well, this is going to be very similar to counting down, with a few small changes. First let's comment out our code, next let's call our function count up. Function, count up. And for this function, we're going to have to pass an argument to specify what number we want it to start at, and what number we want it to count up to. So let's call our arguments from, which is an integer, and two, which is an integer.
So we want our function to print our from argument and then call itself with from, plus one. And then two, won't change at all. It will be the same. And last but not least, we needed to find our stop condition. We want our function to stop when our first argument is greater than our second argument. So if from is greater than two, return. Now if we call our function with the numbers zero and 10.
Count up from zero to 10. We see that it counts up from zero to 10. Now the examples we covered here are really just the tip of the iceberg in what could be done with recursion. But while recursive programs can get very complex, nearly all of them are built on the same basic concepts we've covered here.
- What is functional programming?
- Keeping functions and data separate
- First-class functions
- Working with arrays functionally
- Filtering and reducing
- Partial-application and recursion