As others have mentioned, each level of recursion (or, more generally, each function down from the top-level) has something called a stack frame, which records information.

This isn't just to support caller, it's a very common feature of most languages. If nothing else, it generally contains the information of where to jump to when you return from the current subroutine and the values of the lexical variables which are in that scope but not in the current scope 1.

It's not to everyone's taste, and it uses a different language, called scheme, but the online textbook "Structure and Interpretation of Computer Languages" or SICP covers this, in this section (and related pages).

Recursion is a powerful tool, and like all such it can be mis-used. In particular, note that the amount of stack space is limited on different platforms. Some Win2k systems give you 2mb of stack (by default). If you have a recursive routine which has a 64k variable in the stack frame, you'll die after 30 recursions or so. (This was a real-world bug in a C program).

1: OK, so lexicals may be stored seperately from the call stack, since you can have intermediate scopes. The same principle applies though.

In reply to Re: Misunderstanding Recursion by jbert
in thread Misunderstanding Recursion by Andrew_Levenson

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.