How is recursion like a for loop?

People think recursion is hard but it's no harder than a for loop. In fact, it's got the same parts, they're just not laid out in the same way. In this episode, we look at how you can spot those three parts in any recursive function.

Transcript

Eric Normand: How is recursion like a for loop? By the end of this episode, you will learn the three parts to recursion — initialization, exit condition, and advancement.

Hi, my name is Eric Normand. I help people thrive with Functional Programming.

People often think that recursion is hard, but there really isn't that much more to it than a for loop. It's about as hard as a for loop. Let me put it that way.

Recursion is important because you're going to come across it if you're a functional programmer. People do recursive algorithms. Recursion, as I've talked about in a previous episode, is great for certain problems, better than a for loop.

Sometimes for loop is better, but recursion is better for some problems, particularly, if you have a recursive data structure. Let's see how recursion is like a for loop, and how it should be straightforward to translate most things into recursion.

To back up a second, recursion means a function that calls itself. That definition by itself doesn't tell you how to solve problems with it. I want to tell you how to solve those problems.

A for loop has three parts up at the top. You got the initialization, that's i=0. Let's say we want to count up to 10 with our for loop, something simple. That's the initialization, that's i=0. You're initializing i. It's going to have the exit condition. It's more like the continuing condition, the staying in the loop condition. That's i is less than 10.

In the exit condition, you can do the opposite of that, i is not less than 10. There's the advancement which is i++. It's a very common pattern to use, the i=0, i is less than 10, i++, or i is less than the length of an array. That's the for loop.

Recursion has those same three parts. It just doesn't put them up at the top in one neat package. When you're looking at a recursive solution, you've got to squint and see these parts. They're not going to be noted out. They're separated with semi-colons, and there's one, two, three. They're not going to be so clear, but they're in there.

The first part is initialization. Because when you're doing recursion, your variable is not some extra declaration like var i. The initialization, it's going to be when you call that recursive function for the first time. Your code might call it with zero, and the argument is called i. That's the initialization. That's the first call.

We're going to do count to 10 as a function. You'll call count to 10 zero. When you define count to 10, and the argument is i.

The exit condition. This is going to be the opposite of what you have in the for loop, but it's easy to translate to put a not, or we can say, exit when i is greater than or equal to 10. You're going to have an if. You're going to have a branch. You're going to say, if i is greater than or equal to 10, we're done. Don't recurs. Don't call yourself.

Then there is advancement. This is where you call yourself with a value that is a little bit closer to the exit condition. This is like in a for loop. I'm adding one that should be, if I start to 0, and I keep adding 1, I should get to 10 eventually. Same with advancement in recursion. I'm going to call myself with a value that is a little bit closer to my exit condition.

In recursion, in functional programming, we usually call the exit condition a base case. The base case is the case, usually it's like the easy case. The empty list is the base case, and your advancement is getting you closer to the base case.

You start with a big list. You do something with the first element. You recurs on the tail of the list, everything but the first element. You've removed one element from the list.

It's getting closer to your base case. It's getting closer to the empty list. You keep doing that over and over. It's getting smaller and smaller until it gets to the empty list, and then boom. You're in that branch, and you're done.

One of the differences between a for loop and recursion is that a for loop is a statement. It doesn't have a return value. You have to get a value out or you're building up a value in a variable somewhere.

A function call is an expression that has a return value, that has a value that when you evaluate it, you know the result of that expression. Your function call that's recursive, your recursive function is going to have to figure out the value to return in each case.

That base case, the exit condition case, that one is you'll have to figure it out. If it's counting the elements of a list, the base case, the empty list, what's the count of an empty list? Zero. What's the other case? The non-exit case.

I'm going to take one off. I'm going to recursively call itself on the rest of the list. I'm going to add one. What's the return value? I'm adding one to whatever I get from that recursive call. It might be zero. I might get zero out from the recursive call because it might be almost empty.

You have to think of the return value of that particular expression. You don't do that in a for loop. In a for loop, you're adding one to a variable.

Let me recap. Recursion means a function that calls itself, but it doesn't give you a clue on how to solve problems with it.

For loops have three parts — initialization, exit condition, and advancement. Recursion has the same three parts. They're just not all laid out in a nice little statement up at the top. In recursion, the exit condition is called the base case.

This is usually the easiest case; the case that doesn't have any work to do. Like the empty list, it doesn't have any work to do, but it's going to have some value to be returned. The last thing, for loops are statements so they don't return an expression or they don't return a value.

Whereas, recursive functions are called. They're an expression. They need to return a value. You need to have a return for every case. This is one of the things that get people a little mixed up.

Do yourselves a favor. If you've got some recursive functions in your code base or code base you're used to looking at, go through and identify the three parts.

Look at how it's being called. Where is the initialization? Where is the exit condition? Maybe there's more than one exit condition. Where is the advancement? You can sometimes see that there's two possible exit conditions in this recursive call. I could count down to zero, or I could hit the end of the list. Both of those are possible.

The advancement is I either decrement to get to zero or I remove something to get closer to the end of the list. It's interesting. You can start to play with it and do stuff that gets complicated in a for loop, although I still say for loops are great.

Please do me a favor. This is where I try to get you to help me out. Tell your friends about this. Recursion is an important concept. If I've explained it well, if you like my explanation, they might like it, too. Please subscribe because there's more like this to come. You can also get all my old episodes. They're all in there in the feed.

My email is eric@lispcast.com. I love to entertain questions. If you do email me about the podcast, I assume I can talk about it. If you don't want me to talk about your question or mention you in the podcast, please let me know.

You can reach me on Twitter, love to get into discussions on Twitter. I'm @ericnormand with a D. You can find me on LinkedIn. Awesome. See you later.