47
The stack
Notice that each call to
fact
has its own
copy of
x
. You can’t access a
different function’s copy of
x
.
The stack plays a big part in recursion. In the opening example, there
were two approaches to find the key. Here’s the first way again.
This way, you make a pile of boxes to search through, so you always
know what boxes you still need to search.
48
Chapter 3
I
Recursion
But
in the recursive approach, there’s no pile.
If there’s no pile, how does your algorithm know what boxes you still
have to look through? Here’s an example.
49
The stack
At this point, the call stack looks like this.
The “pile of boxes” is saved on the stack! This is a stack of half-
completed
function calls, each with its own half-complete list of boxes
to look through. Using the stack is convenient because you don’t have to
keep track of a pile of boxes yourself—the stack does it for you.
Using the stack is convenient, but there’s a cost:
saving all that info can
take up a lot of memory. Each of those function calls takes up some
memory, and when your stack is too tall, that means your computer is
saving information for many function calls.
At that point, you have two
options:
• You can rewrite your code to use a loop instead.
• You can use something called
tail recursion
. That’s an advanced
recursion topic that is out of the scope of this book. It’s also only
supported
by some languages, not all.
Dostları ilə paylaş: