[PHP] Recursieve functie werkt niet helemaal

[Reveller]

Ik heb de volgende array en functie

PHP:

$nodes[1]  = array('pid'=>0, 'title'=>'Home'    , 'level' => 0);
$nodes[2]  = array('pid'=>1, 'title'=>'Groenten', 'level' => 1);
$nodes[3]  = array('pid'=>1, 'title'=>'Fruit'   , 'level' => 1);
$nodes[5]  = array('pid'=>3, 'title'=>'Zomer'   , 'level' => 2);
$nodes[6]  = array('pid'=>3, 'title'=>'Winter'  , 'level' => 2);
$nodes[7]  = array('pid'=>5, 'title'=>'Rood'    , 'level' => 3);
$nodes[8]  = array('pid'=>5, 'title'=>'Geel'    , 'level' => 3);
$nodes[10] = array('pid'=>7, 'title'=>'Kers'    , 'level' => 4);
$nodes[11] = array('pid'=>7, 'title'=>'Aardbei' , 'level' => 4);
$nodes[13] = array('pid'=>1, 'title'=>'Drinken' , 'level' => 1); 

function nav_indent($nodes, $current_node)
{
  foreach ($nodes as $nid => $node)
  {
    if ($node['pid'] == $current_node)
    {
      return nav_indent($nodes, $nid);
    }
    else
    {
      $output[] = str_repeat('-', $node['level']).$node['title'];
    }
  }
  return $output;
}

print_r(nav_indent($nodes, 0));

De output van hiervan is:

code:

Array
(
    [0] => Home
    [1] => -Groenten
    [2] => -Fruit
    [3] => --Zomer
    [4] => --Winter
    [5] => ---Rood
    [6] => ---Geel
    [7] => ----Kers
    [8] => ----Aardbei
    [9] => -Drinken
)

maar ik verwacht

code:

Array
(
    [0] => Home
    [1] => -Groenten
    [2] => -Fruit
    [3] => --Zomer
    [4] => ---Rood
    [5] => ----Kers
    [6] => ----Aardbei
    [7] => ---Geel
    [8] => --Winter
    [9] => -Drinken
)

Ik heb gecontroleerd of regel 18 (return nav_indent($nodes, $nid);) toch echt wordt aangeroepen. Dat gebeurt twee keer. Toch wordt de $nodes array van boven naar onderen doorlopen. Regel 18 veranderen in $output[] = nav_indent($nodes, $nid) of $output[] = array_merge(nav_indent($nodes, $nid)) helpt niet. Wat doe ik verkeerd?

[drm]

Laat ik je 1 tip geven:

Als je zorgt dat je die hele "level" niet in de array opneemt, dwing je jezelf de recursie goed op te bouwen. De level kun je namelijk reproduceren aan de hand van de diepte van de recursie en die 1 op te hogen zodra je recurreert (is that a word? )

De functie slaat op dit moment namelijk helemaal nergens op; de enige reden dat er nog iets uitkomt wat ergens op lijkt is die 'level', de recursie zelf leidt nergens toe.

[Reveller]

@drm: ik snap wat je bedoelt:

PHP:

function nav_indent($nodes, $current_node, $level) {
  //...
  nav_indent($nodes, $current_node, $level+1)
}

maar die level-waarde heb ik toch al in de database zitten. Ik wil nl. in staat zijn om bv. ineens alle nodes van het derde level te laten zien. De recursie heb ik alleen nodig om de goede kinderen onder de goede parent te krijgen. Nu ik erover nadenk - kan dit niet zonder recursie als je al die complete $nodes array hebt?

[Michali]

Dit is volgens mij vrij lastig te doen zonder recursie. Ik weet de methode iig niet. Zo kan het wel iig:

PHP:

<?php

$nodes[1]  = array('pid'=>0, 'title'=>'Home'    , 'level' => 0);
$nodes[2]  = array('pid'=>1, 'title'=>'Groenten', 'level' => 1);
$nodes[3]  = array('pid'=>1, 'title'=>'Fruit'   , 'level' => 1);
$nodes[5]  = array('pid'=>3, 'title'=>'Zomer'   , 'level' => 2);
$nodes[6]  = array('pid'=>3, 'title'=>'Winter'  , 'level' => 2);
$nodes[7]  = array('pid'=>5, 'title'=>'Rood'    , 'level' => 3);
$nodes[8]  = array('pid'=>5, 'title'=>'Geel'    , 'level' => 3);
$nodes[10] = array('pid'=>7, 'title'=>'Kers'    , 'level' => 4);
$nodes[11] = array('pid'=>7, 'title'=>'Aardbei' , 'level' => 4);
$nodes[13] = array('pid'=>1, 'title'=>'Drinken' , 'level' => 1); 

function nav_indent($nodes, $pid = 0)
{
    static $output;
    
    foreach ( $nodes as $id => $node )
    {
        if ( $node['pid'] == $pid )
        {
            $output[] = str_repeat('-', $node['level']) . $node['title'];
            
            nav_indent($nodes, $id);
        }
    }
    
    return $output;
}

echo implode("<br/>\n", nav_indent($nodes));

?>

[drm]

Reveller:
@drm: ik snap wat je bedoelt:

PHP:

function nav_indent($nodes, $current_node, $level) {
  //...
  nav_indent($nodes, $current_node, $level+1)
}

maar die level-waarde heb ik toch al in de database zitten. Ik wil nl. in staat zijn om bv. ineens alle nodes van het derde level te laten zien.

Dat begrijp ik, maar 't is voor 't goede begrip van de recursie beter om niet de $level uit de database te gebruiken, daarom zei ik het

De recursie heb ik alleen nodig om de goede kinderen onder de goede parent te krijgen. Nu ik erover nadenk - kan dit niet zonder recursie als je al die complete $nodes array hebt?

Als je ze op de goede volgorde uit de database kunt halen, is dat inderdaad wel mogelijk. De diepte van een node is tenslotte alleen maar een presentatiekwestie in dit geval.

[Verwijderd]

Ten eerste zou ik inderdaad willen zeggen dat je beter recursie kan vermijden.

Mocht je dat niet kunnen dan is mijn ervaring de de foreach in php nogal wat problemen geeft bij recursie.

De variabele die de foreach lus vult wil nog wel eens uit een verkeerd level gehaald worden.

[Michali]

Hoe bedoel je dat precies? Is het echt een bug of meer een addertje onder het gras?

[Verwijderd]

Het is denk ik geen bug maar meer een eigenschap van de foreach functie die op de array zelf een index bijhoud en niet in de lus.
Als je iets probeerd te doen zoals hierboven dan doe ik dat eigenlijk alleen maar met referenties naar de hoofd array (anders zit je bij elke stap een duplica te maken van de array). En dan krijg je in het volgende geval een vrij iritant resultaat:

code:

<?
$nodes[0]  = array('pid'=>-1, 'title'=>'Home');
$nodes[1]  = array('pid'=>0, 'title'=>'Groenten');
$nodes[2]  = array('pid'=>0, 'title'=>'Fruit');
$nodes[3]  = array('pid'=>2, 'title'=>'Zomer' );
$nodes[4]  = array('pid'=>2, 'title'=>'Winter');
$nodes[5]  = array('pid'=>3, 'title'=>'Rood');
$nodes[6]  = array('pid'=>1, 'title'=>'Geel');
$nodes[7] = array('pid'=>6, 'title'=>'Kers');
$nodes[8] = array('pid'=>6, 'title'=>'Aardbei');
$nodes[9] = array('pid'=>0, 'title'=>'Drinken');

function printTree(&$nodes, $current_node, $level)
{
  foreach ($nodes as $nid => $node)
  {
    if ($node['pid'] == $current_node)
    {
      print($level.$node['title']."<BR>");
      printTree($nodes, $nid, $level." - ");
    }
  }
}

function printTree2(&$nodes, $current_node, $level)
{
  for ($nid=0; $nid < count($nodes); $nid++)
  {
    $node = $nodes[$nid];
    if ($node['pid'] == $current_node)
    {
      print($level.$node['title']."<BR>");
      printTree2($nodes, $nid, $level." - ");
    }
  }
}

printTree ($nodes, -1, "");
echo "<br>";
printTree2($nodes, -1, "");
?>

Resultaat:

Home
- Groenten
- - Geel
- - - Kers

Home
- Groenten
- - Geel
- - - Kers
- - - Aardbei
- Fruit
- - Zomer
- - - Rood
- - Winter
- Drinken