Stack Frames & Memory Limits

[00:00:00]
>> Kyle Simpson: So let's talk about recursion in the practical sense. We can get a sense of the theoretical way that this works. But in the practical sense many of you probably know that recursion often doesn't make its way into production applications for one particularly sticky reason. Which is that range error that we get thrown whenever recursion has been running for too long and we get a range error thrown, stack overflow exceeded, okay?

[00:00:26]
That's the major problem that I think, for the last 50 or 60 years, has essentially limited the utility of recursion from being a general programming thing that everybody has to learn and everybody has to use. Is because a lot of people basically think in the back of their mind that sort of nagging feeling like, yeah it sounds good in theory, but in practice it would probably blow up so I'm not gonna use it.

[00:00:49]
And so I want to talk about that because there are ways of addressing this problem. In theory your computer could just run forever, and you'd have infinite memory and infinite CPU. But in practice we know that's not the case, and so we do need to actually step in.

[00:01:04]
A little bit ago I said, try not to think too much from a computer science perspective about what's happening in memory. But to get an intuition for why there is a practical limitation problem, we do need to think just a little bit about the implementation side of it, okay?

[00:01:19]
I don't want you thinking about implementation as your authoring this code. But it's just to get us a sense of the problem of the range error, of the stack overflow problem. So if we think about when a function gets called, when one function is running and it calls off to another function.

[00:01:36]
It doesn't have to be it's own function, it doesn't have to be recursion. It's just the general problem that when one function calls out to another function, at that moment, everything that was currently happening in that function needs to get saved somehow. So that all the stuff that happens in the other function doesn't mess up what was happening in the first one.

[00:01:55]
So if you are in the middle of function A and you call off the function B, you kinda have to have somewhere where all of A's in-progress work is saved so that there's some place, a scratch pad if you will, for the work for B to happen. And in computer science terms, we call these stack frames.

[00:02:13]
Every time a function gets executed, an area of memory is reserved and it's called a stack frame. And we call it a stack frame, we actually call it a memory frame. We call it a stack frame because when one function calls another and then that one calls another, and that one calls another, what we have is a stack that's growing.

[00:02:29]
You have at the bottom level the initial function that called off to B. And B called off to C and C called off to D, you're building up a stack. And we use the stack data structure idea because when this final-most, this top-most function if you will, finishes running, and its work is done, we can get rid of that memory.

[00:02:49]
And we pop the stack back to the previous one and it picks up where it left off. And then we pop the stack back to the previous one, and it might call another and another, and keep coming back. So we have this stack data structure. Whether or not the computer actually uses the stack, conceptually, it usually a stack to manage all of the work as it builds up and goes back down, and builds up and goes back down.

[00:03:11]
So what kinds of things are in these stack frames? Well, you have all of the local variables that have been assigned, any memory that's being assigned for those. You have the program counter which is basically what line of code it's on, or what part of an expression it's on, or something like that.

[00:03:28]
So basic things like that, very low-level things that the computer needs to track what's happening inside of a function. And it doesn't take up a lot of memory, we are not talking about megabytes worth of memory. The stack frame is probably like a few hundred bytes or a K or something.

[00:03:43]
It's probably like a couple hundred bytes at most for each stack frame. And if you're calling a hundred functions in a chain, which almost never happens by the way. Probably at the most you probably go 5, 10 maybe 15 deep. But if you've called even 100 of those functions and you've still only used up a fraction of a megabyte of memory, it's not a big deal.

[00:04:02]
You never see any sort of a problem with that. But as soon as we get into programming practices like recursion, it becomes dramatically more likely that that stack frame, that might grow to thousands, tens of thousands, hundreds of thousands, millions and even beyond. And that does start to chew up some non-trivial amount of memory.

[00:04:22]
Now, this is not a new thought, this is not a new occurrence. Almost the day that recursion was invented back in the, whatever, 60s, the very next day, somebody thought, we only have 4K of RAM on this computer. [LAUGH] We can't do very many function calls in 4K of RAM, right?

[00:04:39]
So back then they had much more of a pronounced limitation than we even do with our fancy gigabytes worth of memory. They had way less memory, so this was a very present problem for them. The math predicted that recursion was this great way of doing things. But in practice we're limited by the amount of memory that we can run.

[00:04:59]
So, they immediately had to confront, is recursion something that should just be filed away as a nice great theory but not something that can be used? Or is there some way to address it?