The prof and TAs had their own go-to metaphors, but (unsuprisingly) the authors of the textbook came up with my favorite: the stack is pieces of paper. Every recursive call just adds a fresh page on top of the pile!
One of my homework problems was a recursive fibonacci method! Guess that means I'm ready for entry-level programming gigs, huh? (That was a joke. Also I don't want an entry-level programming gig.)
No matter what computational magic you put into software, it must run on actual hardware. There's this long running debate between software and hardware engineers. Hardware without software is worthless, software without hardware is fiction.
So, the stack is a set of registers or memory addresses that you can use to store a temporary value, like a program counter. When you recurse, you push the current program counter onto the stack and calls the function again. Eventually, you get to the bottom of the recursion and start popping the stack, retrieving the various call points in the program and executing. If you push on one too many, you overflow the stack and your program becomes irretrievably lost.
Or something like that, depending on your CPU, OS, etc. Embedded systems may have a 8 or 16 entry stack. I'm not sure what x86 would have but they're finite.
(The comment has been removed)
Reply
(The comment has been removed)
One of my homework problems was a recursive fibonacci method! Guess that means I'm ready for entry-level programming gigs, huh? (That was a joke. Also I don't want an entry-level programming gig.)
Reply
So, the stack is a set of registers or memory addresses that you can use to store a temporary value, like a program counter. When you recurse, you push the current program counter onto the stack and calls the function again. Eventually, you get to the bottom of the recursion and start popping the stack, retrieving the various call points in the program and executing. If you push on one too many, you overflow the stack and your program becomes irretrievably lost.
Or something like that, depending on your CPU, OS, etc. Embedded systems may have a 8 or 16 entry stack. I'm not sure what x86 would have but they're finite.
Reply
Leave a comment