Should recursive methods store their interim data in $this?

[NotionCommotion]

I have the following method.  As you can see at the bottom, it calls itself and is recursive.

 

Question is whether I should pass the current scope when I recursively call the method, or in the interim, store them in $this.  I am assuming that I shouldn't use a static variable, right?

 

Currently, I am storing the interim data in $this and adding to it every time the method is executed (for instance $this->realPoints[$point->id]=$point;),  I have two concerns.  First, it would make more sense to me if it returns the values instead of setting something which would later need to be requested (Reference http://forums.phpfreaks.com/topic/301316-should-methods-typically-return-multiple-objects/).  Also, if the method is called twice outside itself, it gets doubled which is not my intent.

 

Or should recursive functions explicitly have earlier data passed to them?  For this case, I require realPointIDs, realPoints, cacheReal, aggrPoints, aggrPointIDs, cacheAggr, custPointIDs, and custPoints.

 

Or should this single method have it's own class?  I am thinking this might make the most sense.

 

Any thoughts?

 

Thank you

    private function _setPoints(array $items, $byName=false)
    {
        $model=$this->getModel();
        $custPoints=[];
        $points=$model->getPoints($items, false, $byName);
        foreach($points as $point){
            if($point->type=="real" && !isset($this->realPoints[$point->id])){
                $this->realPointIDs[]=$point->id;
                $this->realPoints[$point->id]=$point;
                if($this->cacheReal && $point->timestamp < $this->time-$this->cacheTimes['real_points']) {
                    $this->cacheReal=false;
                }
            }
            if($point->type=="aggr" && !isset($this->aggrPoints[$point->id])){
                $this->aggrPointIDs[]=$point->id;
                $this->aggrPoints[$point->id]=$point;                
                if(!isset($this->cacheAggr[$point->duration.'~'.$point->offset]) && $point->timestamp < $this->time-$this->cacheTimes['aggr_points']) {
                    $this->cacheAggr[$point->duration.'~'.$point->offset]=true;
                }
            }
            if($point->type=="cust" && !isset($this->custPoints[$point->id])){
                $this->custPointIDs[]=$point->id;
                $custPoints[]=$point->id;
            }
        }
        if(!empty($custPoints)){
            $customNew=[];
            while($custPoint=$model->getCustomPoints($custPoints)){
                //$this->custPointIDs[] already set
                $id=$custPoint->points_custom_id;
                unset($custPoint->points_custom_id);
                $this->custPoints[$id][]=$custPoint;
                $customNew[]=$custPoint->points_id;
            }
            $this->_setPoints($customNew);
        }
    }

Edited June 10, 2016 by NotionCommotion

[ginerjm]

You must remember that args always instantiate their own chunk of memory. Just because the names are the same as you drill down a recursive process, the vars themselves point to different parts of memory and will not / do not impact each other.

[requinix]

I am assuming that I shouldn't use a static variable, right?

Why not? I would have mentioned it. As long as you manage its state and value correctly - eg, adding to it when going deeper and removing from it when returning - you should be fine. But see my fourth thing below.

 

Or should recursive functions explicitly have earlier data passed to them?  For this case, I require realPointIDs, realPoints, cacheReal, aggrPoints, aggrPointIDs, cacheAggr, custPointIDs, and custPoints.

I wouldn't do it for a public or protected method, but for a private method that can only be called from within this class it's not that bad an option. Use defaults so the caller doesn't have to care.

 

Or should this single method have it's own class?  I am thinking this might make the most sense.

I wouldn't want to do that for myself: I don't like the idea of a class specifically designed to have only one (external) method. However if it turns out to be the most reasonable solution, considering things like clarity and maintainability, then... eh.

 

Any thoughts?

Without me going through the code to confirm, it may be possible to implement this non-recursively. The basic approach to that is to use a loop with an array as a state stack: add state onto it for the next iteration to process, remove when finished. For example... I don't know, I'm blanking on a simple example of a situation where the average person uses recursion that could instead be implemented with a stack.

[Jacques1]

Do you even need to repeatedly resolve those custom points? In other words, can getCustomPoints() again return points of type “cust” which again have points of type “cust” ...?

 

Because otherwise the whole complexity is just pointless.

 

It's also odd that you keep separate arrays of the IDs when you already have them as array keys. Why not simply extract them from the main data with array_keys()?

 

Last but not least, the whole method is way, way too complex to be a setter. A setter is a primitive method which does nothing but set an attribute. It doesn't execute dozens of lines of business logic. So I strongly recommend you choose a more appropriate name like “load” to stress the heavy lifting done by the method.

[NotionCommotion]

You must remember that args always instantiate their own chunk of memory. Just because the names are the same as you drill down a recursive process, the vars themselves point to different parts of memory and will not / do not impact each other.

 

I was thinking of something like the following.  Or maybe putting each in an array or object, and then just passing that back.

    private function _setPoints(array $items, $realPointIDs=[], $realPoints=[], $cacheReal=[], $aggrPoints=[], $aggrPointIDs=[], $cacheAggr=[], $custPointIDs=[], $custPoints=[])
    {
            // bla bla bla
            $this->_setPoints($customNew, $realPointIDs, $realPoints, $cacheReal, $aggrPoints, $aggrPointIDs, $cacheAggr, $custPointIDs, $custPoints );
        }
    }

[NotionCommotion]

Thanks Requinix

 

Why not a static variable?  Everyone says the're evil for one.  Secondly, does it make unit testing difficult?  Would the method still be normal and not static?

 

Agree the properties would definitely be public, but it still seems a bit shady.  I see your point about a class with a single method being a little overboard.

 

For the non-recursive idea, something like:

 

while(!empty($stack)){

   //do stuff which adds and removes from the stack until empty...

}

[NotionCommotion]

Thanks Jacques1,

 

Wow, bet you didn't think I was capable of a non-hypothetical question

 

Yes, a custom point can contain other custom points.

 

Agree, array_keys() is better suited, and will do so.

 

Getters, Setters, and now Loaders....  Sure, I like it!

[requinix]

Why not a static variable?  Everyone says the're evil for one.

Yeah, but do they have any reasons other than "because they can be misused"? Not really. Static variables, global variables, singletons... They can also be used badly, and sometimes they kinda lend themselves to it, but there are good uses for them too.

 

Secondly, does it make unit testing difficult?

Not if you consider the variable to be part of the "unit". And in this case, before and after the first non-recursive call to that method the static variable should be the same; now it's a bit harder to test that specific aspect, but testing the method as a whole (or other units which use that method) covers it too.

 

Would the method still be normal and not static?

The method is unaffected. The "static" in the term "static variable" (in this context) has nothing to do with the "static" that comes with static methods. It just means that the variable persists between calls to the function.

 

For the non-recursive idea, something like:

 

while(!empty($stack)){
   //do stuff which adds and removes from the stack until empty...
}

 

Basically, yeah. Here's how the code looks the way I do it:

$stack = array(array(/* initial state */));
while ($stack) {
	$state = array_shift($stack); // pop off $stack[0]

	// do whatever $state tells you to do
	// if you need to add more states to the stack then
	$stack = array_merge($array_of_new_states, $stack); // prepend
}

Having had my morning coffee* I realized this isn't hard to do this to implement a linear version of the recursive Fibonacci algorithm. $accum is equivalent to a return value from a recursive call and $stack represents the nth Fibonacci numbers that need to be calculated.

You can see the recursive structure represented here: the check for $n is the base case and the merging into $stack is the recursion.

function fibonacci($n) {
	$accum = 0;
	$stack = array($n);
	echo "stack = ", json_encode($stack), "\n";
	while ($stack) {
		$n = array_shift($stack);
		if ($n <= 2) {
			$accum += 1;
			echo "accum = {$accum}\n";
		} else {
			$stack = array_merge(array($n - 1, $n - 2), $stack);
			echo "stack = ", json_encode($stack), "\n";
		}
	}
	echo "final result: accum = {$accum}\n";
}

fibonacci(7);

stack = [7]
stack = [6,5]
stack = [5,4,5]
stack = [4,3,4,5]
stack = [3,2,3,4,5]
stack = [2,1,2,3,4,5]
accum = 1
accum = 2
accum = 3
stack = [2,1,4,5]
accum = 4
accum = 5
stack = [3,2,5]
stack = [2,1,2,5]
accum = 6
accum = 7
accum = 8
stack = [4,3]
stack = [3,2,3]
stack = [2,1,2,3]
accum = 9
accum = 10
accum = 11
stack = [2,1]
accum = 12
accum = 13
final result: accum = 13

* Hot chocolate.

[NotionCommotion]

Dang, that must be some good hot chocolate!

 

Does the Fibonacci algorithm have anything to do with what I am trying to accomplish, or is it just an example of recursive linear implementation?

[requinix]

Just an example.

 

It just clicked with me what the code is doing and that it has to do with those point whatever things the two types and the composite/custom one stuff. Looking up the custom stuff probably involves a database hit, in which case there's no real point making the procedure more complicated just to make the PHP code non-recursive. So forget all that stuff I said.

[kicken]

While using a static variable or a class member to track things isn't bad, I generally find it best to avoid those solutions unless there is a compelling reason to use one. Not using them helps keep the method isolated and helps with debugging through multiple levels of recursion.

 

Generally I find it easiest to write separate public and private functions that handle the recursion. The public function serves as the entry point and then calls the private implementation. The private implementation then can have additional parameters needed to make the recursion work. Once the recursion stops and returns the result, the public method then can assign that to the class member or return it to the caller.

 

If you need your recursive function to return multiple things, you can either return an array or use by-reference parameters.

 

Without more details about what your specific needs are it's hard to make recommendations, but for example something like this for recursively finding files/directories separated by type:

class Filesystem {
    public function getListing($root){
        $this->getListingRecursive($root, $files, $directories);
        return ['files' => $files, 'directories' => $directories];
    }

    private function getListingRecursive($root, &$files, &$directories){
        $iter = new FilesystemIterator($root);
        foreach ($iter as $item){
            if ($item->isDir()){
                $directories[] = $item->getPathname();
                $this->getListingRecursive($item->getPathname(), $files, $directories);
            } else {
                $files[] = $item->getPathname();
            }
        }
    }

    // Bonus iterative implementation
    private function getListingIterative($root, &$files, &$directories){
        $stack = [$root];
        while (null !== ($root = array_shift($stack))){
            $iter = new FilesystemIterator($root);
            foreach ($iter as $item){
                if ($item->isDir()){
                    $stack[] = $directories[] = $item->getPathname();
                } else {
                    $files[] = $item->getPathname();
                }
            }
        }
    }
}

I used separate pass-by-reference variables there for the output, but one could just have easily returned an array (like the public method does) and merged the results instead.