3

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.

2 Answers 2

2

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

3
  • 2
    Isn't a new call frame pushed for every function call, recursive or not? I'm not disagreeing, just wondering how the fact that the call stack growing alone makes a method 'recursive'. I guess you could make the argument that, regardless what object I'm in, the return address coming off the call stack in both instances is the same Commented Jul 17, 2014 at 15:13
  • Agreed. I improved my answer. Commented Jul 17, 2014 at 15:14
  • 2
    For the sake of completeness, a function doesn't need to call itself directly to be considered recursive; see mutual recursion (e.g. f calls g and g calls f).
    – Doval
    Commented Jul 17, 2014 at 16:41
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.)

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.