Recursion - a question about terminology

[T Dahl]

Recursion is when a method calls itself. So far so good, but I need a better vocabulary for discussing the details of recursion. There probably is one. Could you help me learn?

E.g. when a method has been called recursivly a few times there will be several - eh- instances(?) of that method active? Or what would you call such an instance? An invocation?

Let's say for now invocation is the word. Say I am talking about a specific invocation and want to talk about the invocation that called this one, or the invocation this one called. How do I refer to these other invocations relative to this one? Parent and child? Higher or lower level? Prior or following? Time for an example:

int myFactorial( int integer)
{
if( integer == 1)
     return 1;
else
       {
       return(integer*(myFactorial(integer-1);
       }
} 

Say myFactorial is first invoked with the parameter 5. The next invocation will be 4, the following 3 and so on. So, relative to the invocation that has 3 as a parameter, how do you refer to the invocations with 2 and 4 as parameters respectivly? (of course, not all examples of recursion are as straight forward as this).

[Paul Clapham]

I haven't ever had to have names for those things. Usually when one method calls another method in Java, the first is referred to as "the calling method" and the second is referred to as "the called method". If you think you need a different naming convention because the two methods are the same, then you aren't thinking about it in the right way.

[Stephan van Hulst]

I think I would call them iterations, or steps. The 'parent' is simply the caller, the 'child' is the invocation. These are not hard and fast rules, this is what I would use.

[T Dahl]

Thank you both!

What I learn is that there is no well established terminology (and may be not even a need for one). Your suggestions are fine with me. Except I feel a tiny bit of reluctance to using "iteration", basically because that term has a well established meaning in loops (for, while etc.).

[Stephan van Hulst]

Well iteration is just a fancy word for 'step', so in my opinion it would be perfectly legal for both cases.

[edit]

From wikipedia:

Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration", and the results of one iteration are used as the starting point for the next iteration.

In my opinion, perfectly applicable.

[Campbell Ritchie]

Not convinced. Most people use "iteration" to mean non-recursive repetition.

Agree there isn't a well-known name for it. How about method calls, or method invocations?

[Gerard Charles]

Sun uses the terminology stack frames to represent a call in a sequence (recursive or not).

[Stuart Poss]

In mathematics literature on recursion relations, authors often refer to the levels or depth of a particular recursion algorithm (number of different, typically sequential, instances of self-invocation) to address the concept you seem to be describing. If I understand how Java manages memory and function calls, this information is kept in on the stack so the concept of stack frames is relevant to this issue, just as it would be for any instance invocation of any method and thus distinguishable, except perhaps for algorithms that point to or refer to particular values at specific locations on the heap.

For what it is worth Wikipedia says "In computer science, iterated functions occur as a special case of recursive functions, which in turn anchor the study of such broad topics as lambda calculus, or narrower ones, such as the denotational semantics of computer programs." The concepts of iteration and recursion do not appear to be necessarily mutually exclusive. Obviously, context is important.

[Campbell Ritchie]

Agree that if you read Generalised Substitution Language, you find that a recursion and an iteration are identical in their effect.