Recursion
Because of functional programming's deep connection to mathematics, recursion, which plays a huge role in mathematics, plays a huge role in functional programming. Indeed, recursion is so central and powerful to functional programming that it replaces the need for iterative loops (the kind we saw in the previous section). So what exactly is recursion?
Recursion occurs when a function calls itself in its definition. For those unfamiliar with recursion, this seems strange. I mean, if a function needs to call itself, when do we stop? Don't we just loop infinitely? Yup, this is totally possible!
Recursion occurs when a function calls itself in its definition. For those unfamiliar with recursion, this seems strange. I mean, if a function needs to call itself, when do we stop? Don't we just loop infinitely? Yup, this is totally possible!
let rec infinite_recurse (n : int) = 1 + infinite_recurse n;;
infinite_recurse 1;;
Stack overflow during evaluation (looping recursion?).
And OCaml is sometimes nice enough to let us know when we've done this infinite recursion and we'll try to avoid the resulting crashing or stalling by writing recursive functions that aren't infinite. Let's take some examples from mathematics. I'm a big fan of the factorial function. For those unaware, the factorial function is simply the product of all positive integers less than or equal to the number we want to find the factorial of. So the factorial of 4 is 4 * 3 * 2 * 1 = 24. As a result we can define the factorial function like this.
The factorial of 1 is 1.
The factorial of 2 is 2 * factorial of 1. The factorial of 1 is 1.
The factorial of 3 is 3 * the factorial of 2. We said the factorial of 2 is 2 * factorial of 1. The factorial of 1 is 1.
So on and so forth.
What we notice is that the factorial function has two components. The first component is a base case. A base case is a case where we no longer have to call the function again to evaluate it. In the case of the factorial function, it is when our argument is 1. We simply output 1. The second component is our recursive definition. In the factorial case, our recursive definition is the argument multiplied by factorial of 1 minus the argument (n * factorial (n - 1)). Let's see how we would write this factorial function in OCaml.
The factorial of 1 is 1.
The factorial of 2 is 2 * factorial of 1. The factorial of 1 is 1.
The factorial of 3 is 3 * the factorial of 2. We said the factorial of 2 is 2 * factorial of 1. The factorial of 1 is 1.
So on and so forth.
What we notice is that the factorial function has two components. The first component is a base case. A base case is a case where we no longer have to call the function again to evaluate it. In the case of the factorial function, it is when our argument is 1. We simply output 1. The second component is our recursive definition. In the factorial case, our recursive definition is the argument multiplied by factorial of 1 minus the argument (n * factorial (n - 1)). Let's see how we would write this factorial function in OCaml.
let rec factorial : int -> int = fun n ->
if n <= 1 then 1
else n * factorial (n - 1)
;;
Notice that in order to have a function be able to call itself, we need to add the rec keyword to the function's definition.
Let's see what we can do with recursion and lists! Let's add up all of the numbers together in an int list!
First, let's identify a base case. If the list is empty, then we output 0.
Second, let's identify the recursive case. Well, we want the sum. So we can take the first element and add it to the sum of the rest of the list.
In order to implement these cases, we'll be using pattern matching!
First, let's identify a base case. If the list is empty, then we output 0.
Second, let's identify the recursive case. Well, we want the sum. So we can take the first element and add it to the sum of the rest of the list.
In order to implement these cases, we'll be using pattern matching!
let rec list_sum : int list -> int = fun lst ->
match lst with
| [] -> 0
| hd :: tl -> hd + list_sum tl
;;
list_sum [1;2;3;4;5];;
- : int = 15
What we've done here is matched on the list. We then implement the base case, matching on the empty list. Then we match on our recursive case, splitting up the list into the head (the first element in the list) and the tl (the rest of the list). We then add the hd to the sum of the rest of the list.
Let's try finding the product of all of the elements in an int list.
So our base case is the empty list. There are no elements, so we can make the product 0.
Our recursive function is the multiplication, we so should multiply the head of the list with the product of the rest of the list. Let's try this.
Let's try finding the product of all of the elements in an int list.
So our base case is the empty list. There are no elements, so we can make the product 0.
Our recursive function is the multiplication, we so should multiply the head of the list with the product of the rest of the list. Let's try this.
let rec list_product : int list -> int = fun lst ->
match lst with
| [] -> 0
| hd :: tl -> hd * list_product tl
;;
list_product [1;2;3;4;5];;
- : int = 0
That's not what we expected. Well let's go through what happens step by step in our function.
The first step is 1 * list_product [2;3;4;5].
The second step is 1 * 2 * list_product [3;4;5].
The third step is 1 * 2 * 3 * list_product [4;5].
The fourth step is 1 * 2 * 3 * 4 * list_product [5].
The first step is 1 * 2 * 3 * 4 * 5 * list_product [].
The last step is 1 * 2 * 3 * 4 * 5 * 0.
And there's the issue. Our base case defaults to 0, which messes up our multiplication. How can we solve this? One solution is that we can change the base case. Instead of the empty list being 0, we can make it 1. That would work. Another solution is to add a base case! We need a case that would occur before we hit the empty list case. How about the base case of a list with only 1 element? We would simply output the element. That would work! Here are both of those solutions.
The first step is 1 * list_product [2;3;4;5].
The second step is 1 * 2 * list_product [3;4;5].
The third step is 1 * 2 * 3 * list_product [4;5].
The fourth step is 1 * 2 * 3 * 4 * list_product [5].
The first step is 1 * 2 * 3 * 4 * 5 * list_product [].
The last step is 1 * 2 * 3 * 4 * 5 * 0.
And there's the issue. Our base case defaults to 0, which messes up our multiplication. How can we solve this? One solution is that we can change the base case. Instead of the empty list being 0, we can make it 1. That would work. Another solution is to add a base case! We need a case that would occur before we hit the empty list case. How about the base case of a list with only 1 element? We would simply output the element. That would work! Here are both of those solutions.
let rec list_product = fun lst -> - : int = 120 list_product [];; - : int = 1 |
let rec list_product = fun lst -> - : int = 120 list_product [];; - : int = 0 |
As we can see, the only difference between the two in terms of evaluation is the result of the empty list.
Let's take a look at one more reduction of a list. Let's a have a function that combines all of the strings in a string list.
Our base case is the empty list. We would output the empty string ("").
The recursive case is a list with more than 1 element which we can concatenate onto the concatenation of the rest of the list.
Let's take a look at one more reduction of a list. Let's a have a function that combines all of the strings in a string list.
Our base case is the empty list. We would output the empty string ("").
The recursive case is a list with more than 1 element which we can concatenate onto the concatenation of the rest of the list.
let rec list_concatenate : string list -> string = fun lst ->
match lst with
| [] -> ""
| hd :: tl -> hd ^ list_concatenate tl
;;
list_concatenate ["hello";"world"];;
- : string = "helloworld"
The process of reducing these lists down to a single element occurs frequently in functional languages--so much so that there's a name for it: Reduce. There is a standard library function that does this called List.reduce. We have quite a few things that we can do with lists: List.rev, etc. which are awesome because we work with lists a bunch. Again, check out the Core List library for prewritten functions list append, head, etc.
Ultimately, the coolest recursive List function is the fold command. Here is additional information for folding. So what does folding do? Folding takes a function, a list, and a default output as its arguments. The default output is the output that is given for the empty list. The list is the list to be folded over. And the function is the recursive function. Notice that in list_concatenate, our second case is hd ^ list_concatenate tl. ^ would be our recursive function. It takes in an element and the result of folding over the rest of the list. Here is Wikipedia's much clearer explanation:fo
Ultimately, the coolest recursive List function is the fold command. Here is additional information for folding. So what does folding do? Folding takes a function, a list, and a default output as its arguments. The default output is the output that is given for the empty list. The list is the list to be folded over. And the function is the recursive function. Notice that in list_concatenate, our second case is hd ^ list_concatenate tl. ^ would be our recursive function. It takes in an element and the result of folding over the rest of the list. Here is Wikipedia's much clearer explanation:fo
"The folding of the list [1,2,3,4,5] with the addition operator would result in 15, the sum of the elements of the list [1,2,3,4,5]. To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving 1 + 2 + 3 + 4 + 5."
List.fold should take a function and apply it to an element in the list and the rest of the list folded. It should also take an output for the base case. Let's write this fold function.
The function we take in should take in 2 arguments, the first being the first element of the list, and the second argument is the result of the fold function on the list. It should output the type of the second argument. So our function should be ('a -> 'b -> 'b). Our list should be the type of the first argument ('a list). Our base case should be the type of the second argument ('b). And the output of our reduction function is also that type ('b). This gives us a function type of ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b. Let's write this!
The function we take in should take in 2 arguments, the first being the first element of the list, and the second argument is the result of the fold function on the list. It should output the type of the second argument. So our function should be ('a -> 'b -> 'b). Our list should be the type of the first argument ('a list). Our base case should be the type of the second argument ('b). And the output of our reduction function is also that type ('b). This gives us a function type of ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b. Let's write this!
let rec list_fold : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = fun f lst base ->
match f with
| [] -> base
| hd :: tl -> f hd (list_reduce f tl base)
;;
So we can take this function and add up all of the values in a list, concatenate strings, etc.
list_fold (+) [1;2;3;4;5] 0;;
- : int = 15
list_fold (^) ["hello";"world"] "";;
- : string = "helloworld"
Not only is list_fold an awesome function, but it's also a great example of factoring out common code. For instance, thanks to partial application/currying, we can define the previous functions in terms of list_reduce.
let list_sum lst = list_fold (+) lst 0;;
let list_product lst = list_fold (*) lst 1;;
let list_concatenate lst = list_fold (^) lst "";;
Let's use list_reduce to see if all of the values in a list are even.
let all_even lst =
list_fold
(fun hd tl ->
if (mod) hd 2 = 0
then true && tl
else false)
lst
true
;;
all_even [0;2;4;6];;
- : bool = true
Not only can we fold over lists using recursion, we can also do a ton more cool things with recursion and lists. For instance, we can add 1 to all of the arguments in an int list, in a process called map. List.map takes a function and applies that function to every element of the list. Let's write our own.
let rec list_map : ('a -> 'b) -> 'a list -> 'b list = fun f lst ->
match lst with
| [] -> []
| hd :: tl -> f hd :: list_map f tl
;;
let add_1 lst = list_map (fun a -> a + 1) lst;;
add_1 [1;2;3;4;5];;
- : int list = [2; 3; 4; 5; 6]
If mapping is awesome, folding is completely awesomer: So awesome that we can implement map as a specific instance of folding. Let's do that now.
let list_map f lst =
list_fold (fun a b -> f a :: b) lst [];;
list_map (fun a -> a + 1) [1;2;3;4;5];;
- : int list = [2; 3; 4; 5; 6]
We'll see in the next section that we should be using fold_left instead of fold_right which has been shown. fold_left is slightly more complicated in its use.
These are some of the principle ideas behind recursion. Recursion is an amazingly powerful tool and learning it completely is difficult. Consider Joel Spolsky's (CEO of StackExchange) assertion: “If
I may be so brash, it has been my humble experience that there are two things
traditionally taught in universities as a part of a computer science curriculum
which many people just never really fully comprehend: pointers and recursion.” (Source). We'll cover tail recursion next, but we can't possibly cover the entire List module or recursion. Go out and explore to find out more.