I don’t know anything about programming, but I have decided to try to learn Python. One of the lessons I’m reading deals with recursion. Apparently, you can write a function that calls another function. The function calls itself until it reaches a base case, at which point everything unwinds from something called a stack and a value is returned. My questions are these: how does Python know to unwind, and how does Python know to unwind in the correct order?
The short answer is that it’s magic.
The longer answer is that every time you call a function, there’s a lot that goes on to save values like “where I should return to” or “what the variables were before this call”. When you return from a function, all that stuff basically happens in reverse to get you back to the context you were in. The details aren’t terribly important for a high-level language like Python, and you could safely spend the rest of your programming career never worrying about this again.
I am not at all versed in Python, but this is how it works in most computer languages:
The stack takes care of it. At a minimum the stack contains a list of return addresses, so the returns go back to the calling function in the reverse of the order they were called in. In many language implementations the stack will also contain the variables that are used by each instance of the recursive function…but sometimes they are maintained separately from the return address stack.
If the recursion does not terminate at some point, then all the allocated memory for the stack will be used up, and the stack will overflow. Stack overflow is a common symptom of badly done (or accidental) recursion.
A stack is, literally, a stack. You put things on top of it, and then take things back off.
Every time you enter a function, the language puts all of the local variables, the parameters you called the function with on top of the stack, the location where you were before you called the function, and the size of all of this data on top of the stack. When you return from a function, it looks at the size of all of this data, throws away that much information from the top of the stack, and goes back to where you were before. Where you were before doesn’t know that its local variables were buried for a while, since everything’s been cleaned.
You have to know what a stack is first. Fortunately, programmers are lazy so a stack is easy to understand; it’s just like a stack of plates, like at a buffet.
You can do two things with a stack of plates: Pop one off and push one on. The one you pop off is always the last one you pushed on; all of the others are covered up by that one, and get pushed down by it. (The technical term for this is LIFO, for “Last-In First-Out”, like a really cowardly military unit.) That’s all a stack is.
Now, apply this concept to function calls. When a function is called, something called a ‘stack frame’ (or ‘activation record’) is pushed onto a single, central stack, often just called ‘the stack’, which exists for the lifetime of the program. This stack frame contains two things: Local variables (variables that only exist in one function) and the return address (what gets executed next when this function returns). It knows what the correct return address is because it gets computed when the function is called. Precisely how doesn’t need to concern you, frankly; this is why you’re programming in Python instead of assembly. (In fact, it doesn’t usually concern assembly programmers, either.)
When the function returns, the stack frame is popped off and examined to figure out where we should return to. Then the stack frame is gone and that function call is over.
(‘Unwinding’ is just a technical term for popping things off the stack, usually a lot of them at once.)
I can go more detailed, including oddball topics like Stackless Python, if you want.
The first part of your question is “how does Python know to unwind”. It unwinds when you return from the function. When you enter a recursive function you can think of two possible directions, call itself again, or return to the previous call. Somewhere in your recursive function you have to decide which to do. In Python you return from a function with a ‘return’ command. You can also return by simply reaching the end of the function.
The previous posts have covered the stack.
Also old register values (which often, but not always, correspond to local variables).
We’re talking about Python, not C.
(Also, calling conventions vary. On a SPARC it’s entirely possible to call functions without saving any registers, due to the register window, which I can explain if anyone actually cares.)
The stack can also contain called-function arguments, depending on the calling convention.
Right. I actually forgot this; I’m pretty sure it’s how Python works.
The stack can work in all sorts of ways. It provides a context for each calling level, and from that context passed and returned arguments, and the previous context have to be derived. How that is done is rarely integral to high level languages.
I care!
Here’s a general overviewof the system.
Alrighty then. If I use any terms you don’t understand, or concepts you don’t grasp, ask away.
The basic idea is that RISC chips spend most of their transistor budget on local storage, such as cache and (especially) registers, having been designed at the beginning of the era when CPU speed really began to outstrip RAM speed. (CPUs are still faster than RAM, BTW.) This is great when you’re in the middle of a function and have 64 32-bit general-purpose registers all to yourself: You can compute all kinds of temporary values and hold them in the fastest storage available. It’s less great when you need to call a function that also expects to have 64 32-bit general-purpose registers all to itself: The obvious way to do that is to push all of your temporary values onto the stack, likely blowing your cache and forcing the CPU to actually touch RAM. Not good.
The SPARC solution was to have a huge number of registers on-die, but rig it so that you could only see an eighth or a sixteenth or something of them at any one time. This was the ‘register window’: Something in the hardware that the software finagled to change which registers out of the block would be visible. Imagine it like a huge array of boxes covered by a piece of plywood with a hole cut out of it; the hole shows you eight of the 64 boxes (say), and you can move the plywood to vary which eight you can see.
Thus, when a function is called, the window gets moved and the new function effectively has its own register file. When the function returns, the window is moved back. No fuss, no muss. Further, when you finally overrun your entire register file, you can limit the number of registers spilled to RAM to the ones you actually need for the new function; you never need to save and restore the entire register file. (That last bit might be wrong when you bring operating systems into the picture. I don’t know.)
The thing is, the idea was born on SPARC and it looks like it will die there. Apparently it isn’t worth copying; I don’t know why.
Simple: When the prey stops breathing, it knows to unwind and eat it.
More seriously, I think the OP is asking how Python knows whether it should recurse again, or stop recursing and start unwinding. The answer to this is that the programmer tells it. Making sure that there’s an end to the recursion is the job of the programmer who wrote the recursive function.
The textbook example for recursive functions is a function that calculates the factorial of a number. I don’t know Python, so I’ll just show pseudocode here:
function factorial(x)
if x = 0 return 1
else return x*factorial(x-1)
This is calculating x! using the fact that x! = x*(x-1)! . That relationship is true, but it doesn’t help unless we also have some place to start building the tower from: We also need to know that 0! = 1 .
So let’s say we use that factorial function, and we want to know what 4! is. So we put in a call for factorial(4). Our function executes, and it looks at the argument and sees that it’s 4, not 0, so it skips past the first line. Then it goes to the next line, and says “OK, so we need 4factorial(3)". So it calls the factorial function again, putting the new copy on the stack on top of the old one. The second copy looks at its argument, and again sees that it’s not 0 (it’s 3), so again skips past the first line and onto the second. It then says "OK, we need 3factorial(2)”. It calls the factorial function again, putting a third copy of the factorial function on the stack. This third copy again looks at its argument, sees that 2 is not 0 and skips past that line, and then says “Now I need 2factorial(1)". So it puts yet a fourth copy of the factorial function on the stack. The fourth copy sees “1 is not 0”, skips past that line, and says "I need 1factorial(0)”. And so it creates a fifth copy of the factorial function, and puts that on top of the stack.
Now, when the fifth copy of the factorial function executes, it goes through and compares its argument to 0, just like all the previous copies did. But now it sees that its argument is, in fact, 0, and so it returns, with the value of 1. It tells the function that called it “OK, that number you asked me for? It’s 1”, and takes itself off the stack. Since it’s off the stack, the fourth copy is back on top. The fourth copy says “All right, factorial(0) is 1, so 1factorial(0) is 1. That’s what I’m supposed to return.". So the fourth copy reports back to the function that called it “The number you asked for is 1”, and then takes itself off the stack. Then the third copy (which is now top of the stack) says "OK, now that I know that factorial(1) is 1, I can do my calculation, which is 2factorial(1), or 2. That’s the thing I’m supposed to return.”. So it does: It tells the function which called it “The number you asked for is 2”, and takes itself off the stack. Now copy 2 is on top of the stack, it calculates 3factorial(2) and gets 6, and returns that (telling its answer to the function that called it, and removing itself from the stack. Finally, the first copy of the factorial function is back on top, it knows that factorial(3) is 6, and so it can calculate 4factorial(3) is 4*6, or 24, so it returns 24. And now whatever called the factorial function in the first place has its answer: 4! is 24.
Note that the recursion only stopped because of that if statement I put in, telling it when to stop. If that if statement weren’t there, the program would just keep on calling more and more copies of the function, until something broke, and never actually getting an answer, just more and more questions.
And now that I look at that, it looks like an impenetrable wall of text. I knew I should have used 3! for my example, not 4! .
Just be careful the top of the stack doesn’t meet the bottom of the heap. Or is it vice-versa?
A friend of mine claims, when he is confused and discombobulated, that he is “operating in interrupt mode with no stack.”
Depends on the system, but the concept is sound: If you recurse too deeply, you’ll run out of stack, at which point your program dies.
Ha! (The implication there is, “If one more thing demands my time, I’m gonna explode!”)
That can take a long time if the stack is virtual. Any non-simple recursive [del]algorithm[/del] implementation should include safety checks. Usually a simple recursion level counter is all that’s needed.
I explode several times a day. Like the garbage pickup men say, you get used to it after a while.
Fast huge L2 caches, in my opinion.