• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion - a question about terminology  RSS feed

 
T Dahl
Ranch Hand
Posts: 35
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:



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
Sheriff
Posts: 22816
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7961
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 35
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7961
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sun uses the terminology stack frames to represent a call in a sequence (recursive or not).
 
Stuart Poss
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agree that if you read Generalised Substitution Language, you find that a recursion and an iteration are identical in their effect.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!