What is recursion and when should I use it?

Recursion is associated strongly with functional programming. We do use recursion more than imperative programmers do. But we also use iteration. In this episode, we talk about what recursion is, how to use it, when to use it, and when not to use it.

Transcript

Eric Normand: ...is recursion and when should I use it? By the end of this episode you will know what it is, how to use it, why to use it, and especially, when not to use it.

Hi, my name is Eric Normand. I help people thrive with functional programming.

Recursion is an important part of functional programming. It's possible in any paradigm but it's often associated with functional programming, usually by well-meaning professors who want to get people thinking in a different way when they're teaching functional programming.

They might say this language is functional, it doesn't have for loops. It doesn't have any kind of loops, any iteration. You're going to be doing recursion. I know they mean well. They want you to learn something, but it's often frustrating because there are loops in many functional languages.

In functional programming, I'm going to say we use both iteration and recursion. In this video, in this lesson, we're going to talk about when to use which.

What is recursion? Really an easy concept. It's when a function is defined in terms of itself. Basically, if a function inside of its definition calls itself, that is recursion. Very easy.

Now, there's this other thing called mutual recursion, because that's just one function. What if you have two functions that call each other? That's mutual recursion. Function A calls Function B, and Function B calls Function A.

Why do we use it? We do it in the real world. It's whenever you have a problem that's too big to do just by yourself. To tackle the problem, you're going to divide the problem up. You might say, "Look, we've got to build this huge building. It's a big, rectangular building out of bricks." How are we going to start? I can't just start laying bricks.

You're going to get your friends, get your other construction workers. You're going to say, "You do the north wall. You do the south wall, east wall, west wall." You're breaking up the problem. They're probably going to have a little crew. You say, "You start on that side. I'll start on this side. We're going to break the problem up."

We do this all the time. "Hey, can you help me count these things? Break the stack in two? You take that half. I'll take this half." If it's still too big, you can break it in half again. You can send it to someone else.

This is something very natural to us. We do it all the time. That's why we do it, because some problems are much more natural to solve recursively than to start at the beginning and iterate through.

You can still do it. They're actually the same. At the end of the day, if you count a stack of papers, one at a time, starting at the top, you're going to get the same answer as if you break the problem in two, and count them separately and then add it up. You get the same answer.

Very often, the machine code that's generated is very similar. Recursion and iteration — you can always convert between them. That's another thing that is sometimes misunderstood.

When do we do it? Like I said before, if a problem is naturally recursive...I'm referring to my notes here.

If a problem is naturally something that you can break down, something that is easy. When is it natural to break down? When it's easy to break it apart.

If you have a stack of papers and you're just counting them, it doesn't matter where you break it, you can cut it roughly in half. That's a nice property of the problem. If you have four walls, it's easy to divide it into four separate pieces of work. It's easy to break it up.

The other thing is you know when to stop. If I keep breaking up this problem of counting papers in half, and half, and half, at some point, I'm just going to have one paper left. There's no more breaking up. I know when to stop. That's one. It's easy to solve that small problem.

You got those two things. It's easy to break up the problem, and it's easy to know the answer and when to stop. Those are the things that make recursion really natural.

The other way is very similar, but it's worth pointing out separately, is when your data structure is recursive. If you have a tree, trees are recursive. You have a node and it has children nodes. Those children nodes have more nodes, and those have more nodes.

Most work you do on a tree is going to be some kind of traversal down the tree into the children and then the answer is going to come back up to the top. That's most of it, and that is a naturally recursive problem.

The data structure's recursive and so recursion is probably the answer to that. If you try to do that with iteration, it's going to be less natural, let's say. You're probably going to have to kind of fake recursion.

With recursion, what you get out of it is a nice stack, automatically, because you're getting the call stack. A is calling itself on A, and so you're getting a new call stack. A is calling itself again. A is calling itself again. Each time, you're getting a call stack and they roll back when you return from the functions up to the top, so you get that stack naturally.

If you have to traverse a directory structure on your hard drive using a for loop, you're probably going to be making a stack. You're going to make a little stack of, "I need to visit this thing again, but I'm going to put it on the stack and then visit this directory." You're constantly saying, "Oh, there's more work to do but I'm not there yet, so I'm just going to put it on a stack."

Whether you use a stack or a queue is going to depend on breadth first, depth first, etc.

Then that comes to the question of when not. Functional programming and recursion have had this relationship, I think, because — this is in my experience — professors, they're trying to teach you something new. They're in the functional programming unit.

They're like, "Oh, this is the perfect time to teach recursion, because functional programming, the students have been doing for loops their whole lives. Finally, they get to do all the stuff in functional. Let's teach them recursion. Get them out of this for loop mindset."

That's a valiant thing, but the problem is they think that's all you get to do in functional programming. That's the students think that.

I have a friend who would say, "Well, I don't like Lisp because there's no loops. You have to do everything with recursion." It's not true. There is a lot of loops in Lisp.

Clojure has a lot of loops. Common Lisp has like six or seven different kinds of loops. There is a while loop, there is a thing called Loop that's like a for loop. There's looping through a list. There's looping a number of times. There's all sorts of different loops, more loops than you would get in Java or JavaScript.

Java and JavaScript, they basically have a for loop. You have now a for each, and there's a while loop, and that's it.

When do you not use it? Let's get back to that. The overall rule is when it is more natural, more clear, easier to implement in iteration using a for loop or something. When it's easier to iterate than to recurs, you should definitely use iteration. When it's easier to do with iteration, you should use a loop.

Recursion is not always the best answer. I just want to put that out there. I like functional programming. I believe in it, but I want you to hear this from someone who really loves functional programming. Recursion is not everything. It's not always the answer.

Also, sometimes depending on the virtual machine you are on or the runtime you've got, the way it's compiled, you might have a problem with recursion. It might use up your stack. You get a stack overflow because they don't optimize what are called tail calls properly.

Tail call is if I do a recursion and I call any function at the end. Like I'm A, and the last thing I do is call B, that's called a tail call. I don't actually have to add to the stack, because I'm done. I'm A. I'm done. There is nothing more to do. I'm going to call B, so you can reuse that stack frame.

What that lets you do is call yourself over and over. If I call myself over, and over, and over, and over again, I don't need a new stack frame if it's the last thing I do. If I'm remembering something that I'm going to come back to, I need the stack frame but very often, you don't.

Languages that don't emphasize recursion often don't have this thing, so when you try to do recursion, it's just not going to work. You're going to hit a problem that's too big and you're going to get a stack overflow.

That's it. That's all I have to say about recursion. One more thing. I just also want to emphasize that you can always switch between them. A recursive implementation can be rewritten as iteration, and an iterative thing can be written as an equivalent recursion. They're totally equivalent.

You can always experiment to see which one feels more natural, feels more normal. I would say if you're into functional programming, you should be doing that. If your natural inclination is to try iteration, give it a shot. Try recursion.

Just to recap. Recursion is a function defined in terms of itself or a function calling itself. It's recursion. A lot of problems are naturally recursive, and so mathematicians and programmers have found that defining the solution recursively is also very natural, but it's not always natural. Sometimes iteration is way clearer.

Humor me for a bit. Because you can implement anything that's iteration in terms of recursion, I'm going to challenge you to look at some of the code that you have that's got a nasty piece of iteration, like a nasty for loop or something. See if you can write it recursively. See if you can find a better, more natural recursive implementation.

Just give it a shot. You can always throw the code away, but just try it out.

I'm just checking my notes to see if I missed anything. I try to keep these natural and flowing, so sometimes I'll be referring to notes in here. I want to know what's in there.

You know what? I forgot to talk about how so I'm just going to bring that up right now. With recursion, there's really...Oh, no, I talked about that. I talked about that. I'll just mention it again.

The how is you've got to know when to end. Usually you're talking about what is the easiest, smallest case. If I'm adding numbers in a list, the easiest, smallest case is going to be...Just think about it for a second. It's going to be the empty list. Empty list is easy. It's going to be zero.

That's the one that you find at the end. That's the easy one to define. Then you have to define how do I break up the problem so that it gets to be that small, even with one thing in it. It's easy. It's just the number that you're adding up. It's just that one thing.

You have those two cases. The empty list, the single list, very easy also, then you have a list of many. You just have to define how to break it up. Once you break it up, it calls itself on that broken up piece, so you split the array in two or whatever. Then, eventually, it's going to be either zero or one. Then it's very easy to define.

That's it. Know when to end, know how to break up the problem, and then what you need done on the thing each time if it's not a functional thing. Sometimes you have to do something like print it out or something.

Please try to find something that you think is not that natural and write it recursively, just to try it. Just practice that muscle of using some recursion.

Here's another favor that you can do me. If you like this, please comment, subscribe, or share with someone that you think might use this. We work in teams and if you think someone on your team needs to learn about recursion, just share this thing with them. Thank you.

If you need to disagree with me, [laughs] if you don't think recursion is more natural, if you think it is, but I got the explanation wrong, comment. Get in touch with me.

You can reach me by email, eric@lispcast.com. I'm also on Twitter @ericnormand, and I'm also trying to get into LinkedIn, so please find me on there and we'll connect.

Awesome. See you later.