Calling same method on different object - Recursion?

Question

I have an object that contains a reference to another object of the same type. Example in PHP:

class A {
    protected $child;
    public function __construct(A $child = null) {
        $this->child = $child;
    }

    public function go() {
        if($this->child) {
            $this->child->go();
        }
    }
}

$a = new A(new A());
$a->go();

Is the go method considered a recursive method? I can see it both ways myself, and I'm not sure if there is a 'correct' answer or not, but I assume that there is.

Answer 1

It is recursive, since the call stack needs to grow. A new call frame has to be pushed (to the same function).

If the go method called another foo method (even on an unrelated class) which itself calls again go on the same class, you would have a mutual recursion ...

Another way to look at that is noticing that method invocation is just a dispatch phase (computing which function should really be called depending upon the receiver), followed by a function call (whose first argument is the reciever).

However, read about tail calls (or tail recursion). It enables to replace the current call frame with the newly called one (without growing the call stack).

So good compilers implement a tail call as a "jump with arguments"; read also about continuation passing style

Answer 2

The instance on which the method is invoked (the receiver of the message, in Smalltalk terms) is typically treated as an implicit, zeroth parameter to the method.

So a method like

public function go()

that takes no arguments can be thought of as actually taking one argument, named $this, of type A:

public function go(A $this)

And a call to that method, dispatched on some particular instance of A, could then be thought of, not as being written

$this->child->go()

but rather written like this:

go($this->child)

When looked at in these terms, it clearly becomes a recursive call. (The Cfront C++ compiler, in the very early days of C++, translated C++ into C code like this, which was then compiled with a C compiler.)