CODEWITHSUNDEEP
phprecursiontree
Ihor Vorotnov
Ihor Vorotnov

Reputation: 1797

Recursive list of items in PHP, unknown depth and nodes

gurus! First of all, I've spent half a day googlin'n'stackoverflowing but couldn't find a solution. This is my first time working with recursions. Hope someone can help.

I have a MySQL table, this is kind of referal system:

Table 'users'

ID   SPONSORID
---------
1    2         
2    1         
3    1         
4    1         
...  ...

There are several things to keep in mind:

  1. Users 1 and 2 are sponsors/referals of each other.
  2. Each user can have unlimited number of referals.
  3. Each user's referal becomes a sponsor as well and can also have unlimited number of referals
  4. Depth is unlimited.

The task is to recursively build a tree of a single "team", like:

User 1
    User 2
        User 1
        User 5
             ...
                 ....
    User 3
        User 295
             User 356
                 ....
    User 4

and so on...

Here's what I'm trying to do:

$team = Array();
function build_team( $userID, $team ){
    if ( !in_array($userID, $team ) :
        // get 1st level of referals
        // returns associative array ('id', 'login', 'sponsorid')
        $referals = get_user_referals( $userID );
        for ( $i=0; $i<count($referals); $i++ ) :
            $team[] = $referals[$i];
            build_team( $referals[$i]['id'] );
        endfor;
    endif;
}

And also tried putting that IF inside the FOR block, but it still goes in infinite loop. As I understand I need a condition to quit recursion when there's no depth level but I can't understand how to calculate/determine it. Any suggestions?

Upvotes: 1

Views: 351

Answers (1)

egis
egis

Reputation: 1412

Keep users ids, whom are already "built", somewhere. As you said yourself - "Users 1 and 2 are sponsors/referals of each other.", so there is your infinite loop.

Something like

if (!in_array($userId, $already_looped_users){

  //continue loop...

}

Adding some code:

$team = Array();
function build_team( $userID, $team ){
     if ( !in_array($userID, $team ) :
        // get 1st level of referals
        // returns associative array ('id', 'login', 'sponsorid')
        $referals = get_user_referals( $userID );
        if (count($referals) > 0){ //added this line
          for ( $i=0; $i<count($referals); $i++ ) :
              $team[] = $referals[$i];
              $team[$referals[$i] = build_team( $referals[$i]['id'], $team ); // i've edited this line
          endfor;
          return $team; 
        }
    endif;
}

Upvotes: 2

Related Questions