Recursion: Motivation

Before getting into the motivation to use recursion, a great question is, “What is recursion?”

Simply stated, a recursive function is a function that calls itself. That’s it.

As you’ll see in this lesson, a common use of recursive functions is to iterate over the elements in a list.

The next question that usually comes up right about now is, “Why do I need to write recursive functions? Why can’t I use for loops to iterate over lists?”

The short answer is that algorithms that use for loops require the use of var fields, and as you know from our rules, functional programmers don’t use var fields.

(Read on for the longer answer.)

Of course if you could use mutable variables in your programming language, you might write a “sum the integers in a list” algorithm like this:

def sum(xs: List[Int]): Int = {
    var sum = 0
    for (x <- xs) {
        sum += x
    }
    sum
}

That algorithm uses a var field named sum and a for loop to iterate through every element in the given list to calculate the sum of those integers. From an imperative programming standpoint, there’s nothing wrong with this code. I wrote imperative code like this in Java for more than fifteen years.

But from a functional programmer’s point of view, there are several problems with this code.

One problem is that reading a lot of custom for loops dulls your brain.

As an OOP/imperative programmer I never noticed it, but if you think about the way you thought when you read that function, one of the first things you thought is, “Hmm, here’s a var field named sum, so Al is probably going to modify that field in the rest of the algorithm.” Then you thought, “Okay, here’s a for loop … he’s looping over xs … ah, yes, he’s using +=, so this really is a ‘sum’ loop, so that variable name makes sense.” Once you learn FP — or even if you just learn the methods available on Scala collections classes — you realize that’s a lot of thinking about a little custom for loop.

If you’re like me a few years ago, you may be thinking that what I just wrote is overkill. You probably look at mutable variables and for loops all the time. But studies show that we can only keep just so much information in our brains at one time, therefore:

• The less information we have to keep in there is a win, and

• Boilerplate for loop code is a waste of our brain’s RAM

Maybe this seems like a small, subtle win at the moment, but speaking from my own experience, anything I can do to keep my brain’s RAM free for important things is a win.

See the Wikipedia article, The Magical Number 7 (Plus or Minus 2) for a good discussion on how much information we humans can keep in our brains at any one time.

Another problem is that this code doesn’t look or feel like algebra. I discussed this in the “Functional Programming is Like Algebra” lesson, so I won’t repeat that discussion here.

Of course from our perspective as functional programmers, the huge problem with this code is that it requires a var field, and Scala/FP developers don’t use those. A var field is a crutch, and the best thing you can do to expedite your FP education is to completely forget that they exist.

In my own FP experience, I learned that there’s a different way to solve iterative problems once I let go of var fields and for loops.

Because we can’t use var fields, we need to look at a different tool to solve problems like this. That tool is recursion.

If you’re like me, at first you’ll need to write recursive functions (because that’s all you can do), but after a while you’ll want to write recursive functions.