1. Recursion in Functional Programming
Now we are going to look at a slightly more advanced topic in functional programming: recursion. Don't worry! We'll continue to keep this at a high level.
2. What is recursion?
So what is recursion? Recursion is an approach to programming a function where the function in question calls itself. Check out this Python code example to see the flow of a recursive function. In line 6, we can see that we call my_recursive_function within itself.
At first, it might seem that this would create a never-ending series of function calls. That is why recursive functions must always contain something called a termination condition, or a base case, in which the function will not call itself and will return instead. We can see the base case in our example on lines 2-3.
All recursive functions contain a base case and a recursive call, which is a call to itself with modified input that moves the process closer to the base case.
3. Why use recursion?
But why do we need to define recursive functions? Couldn't we achieve the same result some other, more direct way? In some cases, it's true: a recursive solution is unnecessary. But other problems lend themselves very naturally to recursion.
Take for example the sequence of Fibonacci numbers. Fibonacci numbers are defined such that the first Fibonacci number is zero, the second is one, and all subsequent Fibonacci numbers are equal to the sum of the previous two. We can see an example of the sequence here. This is a sequence that is recursively defined because in order to get the nth Fibonacci number, we would need to find first the previous two Fibonacci numbers. As a result, it makes sense to implement Fibonacci numbers recursively!
4. Some more examples of recursion
So we've seen one example of computing Fibonacci numbers using recursion. This is a fun example, but may not come up very often. So what are some more common uses of recursion that actually make sense in practice?
A good example is the process of searching through a file system on our computer: we would search the top directory first, then recursively search each subdirectory within that main folder.
5. Some more examples of recursion
Another classic use for recursion in programming is a recursive sorting algorithm that breaks a collection of items in half, recursively sorts each half, and then merges the two halves together.
6. Some more examples of recursion
Finally, some data structures are defined recursively, and so recursive methods work well for interacting with them. A detailed explanation of each of these examples is beyond the scope of this course, but hopefully this was a helpful, high-level view of the value of recursion.
7. Recursion versus iteration
Here's a fun fact about recursion: we can also write every recursive function iteratively. It's true: some problems are more easily understood recursively. But others are just as straightforward, and possibly more efficient, when computed iteratively. It's part of the job of a programmer to know which approach is best in which case.
Take the following example of computing factorial. In the slide, we can see the iterative solution in Python code. Notice that it uses a for loop rather than the base case and recursive call format we have seen in recursive functions. In the exercises, we will be implementing the recursive version of this function!
8. Let's practice!
Now it's your turn! In the following exercises, you'll get the opportunity to test your understanding of recursive functions and how to structure them.