Becoming Functional

Chapter 5. Recursion

Immutable variables have an obvious flaw: we cannot change them. This means that it’s more difficult to do things like changing a single element of a list, or implementing an if statement that sets a variable. Also, let’s think about immutability in terms of applications. How can our applications run if data is never allowed to change? This is where we must use recursion.

Math Warning

Let’s check out an example of a recursive function in mathematics. We can see that we have an end case: if x is less than or equal to 0. And we have the execution to do for every other case—this is our summation.

Here we are just summing up each number that we pass in, but what if we used our first-class functions? Let’s see what we could do.

Although it doesn’t seem like much has changed, what we’ve effectively done is create the summation operation.

Many people are afraid of recursion, mainly because they never learned how to write recursive functions effectively. People also assume that iterative algorithms are inherently better than recursive algorithms. Recursive algorithms are much simpler because they deal only with the input values. If we were to use a normal for loop in an iterative ...