Show description

Writing a function that returns a pair of a vector and an index is harder to work with than just incrementing the index itself. 29 Chapter 2 ■ Pure Functional Programming When you write recursive functions on a sequence, the key abstractions you need will be checking if the sequence is empty, getting the first element, and getting the rest of the sequence. Using functions for these three operations doesn’t help unless these functions would let us work on different data types for sequences. It is possible to make such abstractions, but this is beyond the topics of this book, and we will not consider it more in this book.

For functions such as linear search, we would never program a solution as a recursive function in the first place. The for loop version is much easier to write and much more efficient. Other problems are much easier to solve with a recursive algorithm, and there the implementation is also easier by first thinking in terms of a recursive function. The binary search is an example of such a problem. It is inherently recursive since we solve the search by another search on a shorter string. It is also less likely to hit the allowed recursion limit since it will only call recursively a number of times that is logarithmic in the length of the input, but that is another issue.

We need to multiply the result we get from the recursive call with n: factorial <- function(n) { if (n == 1) 1 else n * factorial(n - 1) } Here I am assuming that is an integer and non-negative. If it is not, the recursion doesn’t move us closer to the basis case and we will (in principle) keep going forever. So here is another case where we need to be careful to make sure that when we call recursively, we are actually making progress on solving the problem. This function is only guaranteed for positive integers.