What are the open activation records of a recursive algorithm ?


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?

  • 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

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.


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.