Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is it called "open (or closed) recursion?

I found some explanations of open/closed recursion, but I do not understand why the definition contains the word "recursion", or how it compares with dynamic/static dispatching. Among the explanations I found, there are:

Open recursion. Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some languages, this. The special behavior of self is that it is late-bound, allowing a method defined in one class to invoke another method that is defined later, in some subclass of the first. [Ralf Hinze]

... or in Wikipedia :

The dispatch semantics of this, namely that method calls on this are dynamically dispatched, is known as open recursion, and means that these methods can be overridden by derived classes or objects. By contrast, direct named recursion or anonymous recursion of a function uses closed recursion, with early binding.

I also read the StackOverflow question: What is open recursion?

But I do not understand why the word "recursion" is used for the definition. Of course, it can lead to interesting (or dangerous) side-effect if one uses "open recursion" by doing... a method recursion call. But the definitions do not take method/function recursive call directly into account (appart the "closed recursion" in the Wikipedia definition, but it sounds strange since "open recursion" does not refer to recursive call).

Do you know why there is the word "recursion" in the definition? Is it because it is based on another computer science definition that I am not aware of? Should simply saying "dynamic dispatch" not be enough?

like image 386
Vincent Hiribarren Avatar asked Jul 23 '13 07:07

Vincent Hiribarren


People also ask

What is open recursion?

Open recursion. Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some langauges, this.

How do you explain recursion?

Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function. The C programming language supports recursion, i.e., a function to call itself.

What allows open recursion?

To enable open recursion, the call-graph of the method functions cannot be hard-wired, but needs to be implemented indirectly, via object self-reference.

Who came up with recursive design approach?

The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of natural number.


1 Answers

I tried to start writing an answer here and then ended up writing an entire blog post about it. The TL;DR is:

So, if you compare a real object-oriented language to a simpler language with just structures and functions, the differences are:

  • All of the methods can see and call each other. The order they are defined doesn’t matter since their definitions are “simultaneous” or mutually recursive.
  • The base methods have access to the derived receiver object (i.e. this or self in other languages) so they don’t close over just each other. They are open to overridden methods.

Thus: open recursion.

like image 124
munificent Avatar answered Nov 07 '22 16:11

munificent