PHP recursive break

Question

I'm not so used to recursive functions, and I don't understand how to exit properly the function.

I try to identify a list of children (grand-children, and so on) from a parent item in a database (with Laravel).

public function getChildren($parentId, $allChildrenArray = Array()){
 $children = DB::table('myTable')->where('parent',$parentId)->get();
 if (sizeof($children)>0){
 foreach ($children as $child) {
 array_push($allChildrenArray,array($child->slug, $child->id));
 MyController::getChildren($child->id, $allChildrenArray);
 } 
 }else{
 // var_dump($allChildrenArray); displays a proper array
 return $allChildrenArray;
 }
}

I have two questions on this.

1. As I understand my script, it would stop propagating as soon as a dead-end is met. But what if there are other pathes to explore?

2. If I display a var_dump($allChildrenArray), an array is displayed which seems ok. However, if I try to display it from an other function, I get null...

   public function doStuff($itemId){
    $allChildrenArray = MyController::getChildren($itemId);
    var_dump($allChildrenArray); // displays null
   }
   

• zerkms: The easiest way to understand it is to go through all the steps manually on the piece of paper. "I get null" --- because you're not returning anything in case if sizeof($children)>0. You're not using the result of MyController::getChildren call as well.
• Yako: But if sizeof($children)>0, if there are children, I update the value of the $allChildrenArray. And then I just restart the same thing with an updated value of the children array, and an updated reference item. What should I return?
• zerkms: "I update the value of the $allChildrenArray" --- and do nothing with it. You've modified a variable, then what? It's not magically modified in the place you've passed it originally from.

Answer 1

First, you should put your helpers outside of your controllers :)

More to the point: to understand recursion it helps to go through to process step by step and when you get to the recursion, say let's assume that's doing what it should then go back there later.

Let's start like this:

 /**
 * Returns the children for a given parent
 * @param int $parentId
 * @return array
 */
 public function getChildren($parentId){
 $allChildrenArray = array();
 $children = DB::table('myTable')->where('parent',$parentId)->get();
 foreach ($children as $child) {
 array_push($allChildrenArray, array($child->slug, $child->id));
 // Here should be the recursion later
 } 
 // var_dump($allChildrenArray); displays a proper array
 return $allChildrenArray;
 }

Now if you look at this function you'll see that it works for the first level. It's quite easy to tell, that when going through the children of the given parent you'll need to get those descendants if you want to add the recursion.

 /**
 * Returns the children recursively for a given parent
 * @param int $parentId
 * @return array
 */
 public function getChildren($parentId){
 $allChildrenArray = array();
 $children = DB::table('myTable')->where('parent',$parentId)->get();
 foreach ($children as $child) {
 array_push($allChildrenArray, array($child->slug, $child->id));
 // get descendants of child
 $furtherDescendants = $this->getChildren($child->id);
 // add them to current list
 foreach ($furtherDescendants as $desc) {
 $allChildrenArray[] = $desc; // or use arraypush or merge or whatever
 }
 } 
 // var_dump($allChildrenArray); displays a proper array
 return $allChildrenArray;
 }

Now what happens is that when you reach the first child a new run of the getChildren function will start for the id of that child as the parent id. If there are no children of it then it will return an empty array, otherwise it'll add the information for that child and then start a new run for the id of the grandchild as parent id and ...

You can probably save some memory if you pass the array along but in that case you need to do it as a reference. Also then when you'll call this method in the first place you'll need to pass a variable as an input that will be populated.

 /**
 * Returns the children recursively for a given parent
 * @param int $parentId
 * @param &array $children
 */
 public function getChildren($parentId, &$allChildrenArray) {
 $children = DB::table('myTable')->where('parent',$parentId)->get();
 foreach ($children as $child) {
 array_push($allChildrenArray, array($child->slug, $child->id));
 // get descendants of child
 $this->getChildren($child->id, $allChildrenArray);
 } 
 // var_dump($allChildrenArray); displays a proper array
 return; // nothing to return, children info added to variable passed by reference
 }
 ...
 $kids=array();
 $this->getChildren($parentId, $kids);
 var_dump($kids)

Just make sure that you don't mix up the two different solution.

The exit condition will be the case when a given parent has no children. In this case the foreach won't start so no further recursive calls will be made. However that only means exiting on that branch.

• Yako: Thank you so much for this very comprehensive answer!