0
$\begingroup$

What are the open activation records of a recursive algorithm ?

Edit:

Activation records are the number of times that we call a function that is not finished yet. Correct?

So we can find the number of activation records only when we are given a specific input array and we cannot say something for a general array with dimension n. Or can we?

$\endgroup$
  • 1
    $\begingroup$ What research have you done? Where you have you looked? Hint: odds are that this is covered in a compilers textbook. $\endgroup$ – D.W. Oct 13 '14 at 9:03
  • $\begingroup$ Did you look e.g. here? This is covered in the dragon book as well. $\endgroup$ – Juho Oct 13 '14 at 9:04
  • $\begingroup$ So it is the number of times that the recursive function is called and it is not finished yet. Correct? $\endgroup$ – Mary Star Oct 13 '14 at 9:09
  • $\begingroup$ So we can find the number of activation records only when we know the dimension of the input array. Correct? So we can not have a general formula for a given recursive algorithm. Or can we? $\endgroup$ – Mary Star Oct 13 '14 at 9:12
6
$\begingroup$

Your question is very poorly stated, except for the title. There is not a single sentence that is really correct or meaningful semantically.

So I will stick to the title, and explain what is wrongt with the text.

Activation records are a programming language implementation concept. Programming languages can be used to implement algorithms in programs, but the concept of an algorithm is an abstract notion, rather than a concrete realization in a specific programming language.

An activation record is a chunk of memory containing usually the local data necessary to execute a subprogram call (the name vary with languages, such as function, procedure, method, subroutine ...), as well as memory and code control flow. More dynamic parts of the data used may be stored in other places (heap).

Thus an activation record is not the number of whatever. But the number activation records in use do, in general, correspond to the number of calls that have not been returned ... though that is not necessarily true in some languages (see below).

In simpler programming languages, subprogram calls are well nested so that the first subprogram to be returned from is the last one that was called. Hence activation records can be stored on a pushdown stack. That will not apply to such control structures as coroutines.

Also, it may be that data in activation records can still be used by the program after the subprogram has been returned. This happens for example when the result of a subprogram can be another subprogram to be executed later (I skip the details).

So, in such a case, one may have to keep in memory more activation records than there are unfinished calls. And the pushdown stack no longer works properly without specific techniques to handle the problem.

Last, this is a general concept. I have no idea what your input array is for or what it does in your program. So that I cannot answer you. Many programs do not have arrays at all, but do have activation records.

$\endgroup$
  • $\begingroup$ I think what OP asked is related to your 7th paragraph -- essentially, "how does the compiler writer know how if variables/constants in the caller are needed in the callee?". This answer to this, in algorithm form, would answer their underlying question, the way I read it. $\endgroup$ – ryanwebjackson Jan 4 at 23:09
  • $\begingroup$ @ryanwebjackson I am not sure I understand your comment. In many languages, it may not be essential to know whether "variables/constants in the caller are needed in the callee?" The reason is that the pushdown stack management of activation records will preserve everything about the caller, whether needed or not, while the callee executes. The problem is usually when the callers uses entities from the callee after the callee has returned. Then some activation record related to the callee has to be preserved. Full discussion is much more complex. $\endgroup$ – babou Jan 5 at 20:25
  • $\begingroup$ I assume that in a recursive algorithm, many entities would be shared between the caller and the callee, because they are the same code (at least the part that is recursive). Though not worded well, I think that is the target of their question -- can it be assumed that each recursive call to a function leaves an activation record open? $\endgroup$ – ryanwebjackson Jan 6 at 3:32
  • $\begingroup$ In a naive implementation of recursion (assuming the caller need not access variables created by the callee), you can assume that the number of live activation record is equal to the number of calls that have not yet returned. But it may be less in many cases when you have good recursion optimization. Actually, the recursion may be even be completely optimized out by a compiler in some cases. But I cannot try to guess further as to the precise (?) motivation of the question. $\endgroup$ – babou Jan 6 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.