Помогите с рекурсией

Arqin · 27 Янв 2009

Помогите с рекурсией

Дело такое нужно выбрать всех потомков в таблице по указанному ID...
Вроде написал рекурсию, но не могу понять в чем загвоздка. Она корректно работает только при вложении не более 2...
Укажите на ошибку, пожалуйста...
Вот сосна код:

PHP:

    function getDescendant($val = '') {
	    $rr=array();
	    $res = array();
	    $rt = array();
	    if (!$val) {
	    	$val = $this->oid;
	    	$rr[] = $val;
	    	}
	    $qq="select OID from CATEGORY where PARENT_OID='{$val}' order by name";
	    $result = $this->cache->query ($qq);
	    while ($row=$result->fetchRow()) {
	      $rt = $this->getDescendant($row['OID']);
	      $rr[]=$row['OID'];
	      $res = array_merge ($rt, $rr);
	    }
	    return $res;
    }

Собственно сама функция является методом класса...

P.S.: Заранее спасибо =)

x-yuri · 27 Янв 2009

а отлаживать пробовал ;-)

Arqin · 27 Янв 2009

Пробовал... я понимаю что как-то неверно значения все полученные храню, но моск отказывается понимать куда правильно поставить =(

x-yuri · 27 Янв 2009

вставь перед возвращением результата var_dump($res) и проверь полученные результаты

Arqin · 27 Янв 2009

я правда другим немного способом проверял:

PHP:

echo '<pre>';
print_r ($res);
echo '</pre>';

но проверял.... поэтому и не пойму... он просматривает только ближайшее вложение судя по всему...

x-yuri · 27 Янв 2009

что значит ближайшее вложение? только один уровень? т.е. только непосредственных потомков?

Arqin · 27 Янв 2009

Автор оригинала: x-yuri
что значит ближайшее вложение? только один уровень? т.е. только непосредственных потомков?

Судя по всему да....сам толком не пойму... непосредственных или только последей выбранной записи...

-~{}~ 27.01.09 12:28:

я так полагаю массивы все кроме последнего обнуляются... ток вот никак не придумаю куда промежуточные результаты воткнуть чтобы они не исчезали...

x-yuri · 27 Янв 2009

а теперь вставь после array_merge: var_dump(array($rt, $rr, $res))

-~{}~ 27.01.09 11:37:

сеанс удаленной отладки, ёпт)

Arqin · 27 Янв 2009

да уж....
вставил....
склоняюсь к тому что, он всетаки непосредственных выводит...
я вчера уже его гонял взад и поперек...
я понимаю что проблема в хранении промежуточных данных, но никак не сообразить куда их класть чтобы не пропадали!
Вот к примеру один массив который он вернул:

Код:

array(3) {
  [0]=>
  array(0) {
  }
  [1]=>
  array(11) {
    [0]=>
    string(4) "1471"
    [1]=>
    string(4) "1474"
    [2]=>
    string(4) "1469"
    [3]=>
    string(4) "1470"
    [4]=>
    string(4) "1468"
    [5]=>
    string(4) "1463"
    [6]=>
    string(4) "1462"
    [7]=>
    string(4) "1464"
    [8]=>
    string(4) "1472"
    [9]=>
    string(4) "1465"
    [10]=>
    string(4) "1475"
  }
  [2]=>
  array(11) {
    [0]=>
    string(4) "1471"
    [1]=>
    string(4) "1474"
    [2]=>
    string(4) "1469"
    [3]=>
    string(4) "1470"
    [4]=>
    string(4) "1468"
    [5]=>
    string(4) "1463"
    [6]=>
    string(4) "1462"
    [7]=>
    string(4) "1464"
    [8]=>
    string(4) "1472"
    [9]=>
    string(4) "1465"
    [10]=>
    string(4) "1475"
  }
}

-~{}~ 27.01.09 12:55:

можно попробовать потестить на одной записи с определенным ID...

-~{}~ 27.01.09 13:05:

попробуй создай таблицу типа:

Код:

CREATE TABLE CATEGORY (
  OID int(11) NOT NULL auto_increment,
  `name` varchar(255) NOT NULL default '',
  PARENT_OID int(11) default NULL,
  PRIMARY KEY  (OID),
  KEY PARENT_OID (PARENT_OID),
  KEY OID (OID)
) ENGINE=MyISAM  DEFAULT CHARSET=koi8r;

заполни ее...
тада легче понять буит...
у мя уже моск кипит =(

-~{}~ 27.01.09 13:07:

думаю нуна попробовать тупо создать маленькую таблицу и на ней потестить...

x-yuri · 27 Янв 2009

да, вот такую
[sql]INSERT INTO CATEGORY (OID, PARENT_OID) VALUES
(1, NULL),
(2, 1),
(3, 2),
(4, 1),
(5, 4);[/sql]

-~{}~ 27.01.09 12:15:

посмотри, что возвращает каждый вызов метода и скажи, с каким $res ты не согласен

Arqin · 27 Янв 2009

вот что получилось для 1:

Код:

array(3) {
  [0]=>
  array(0) {
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
  [2]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
}

array(3) {
  [0]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "2"
  }
  [2]=>
  array(2) {
    [0]=>
    string(1) "3"
    [1]=>
    string(1) "2"
  }
}

array(3) {
  [0]=>
  array(0) {
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
  [2]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
}

array(3) {
  [0]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
  [1]=>
  array(2) {
    [0]=>
    string(1) "2"
    [1]=>
    string(1) "4"
  }
  [2]=>
  array(3) {
    [0]=>
    string(1) "5"
    [1]=>
    string(1) "2"
    [2]=>
    string(1) "4"
  }
}

array(3) {
  [0]=>
  array(0) {
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
  [2]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
}

array(3) {
  [0]=>
  array(1) {
    [0]=>
    string(1) "3"
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "2"
  }
  [2]=>
  array(2) {
    [0]=>
    string(1) "3"
    [1]=>
    string(1) "2"
  }
}

array(3) {
  [0]=>
  array(0) {
  }
  [1]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
  [2]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
}

array(3) {
  [0]=>
  array(1) {
    [0]=>
    string(1) "5"
  }
  [1]=>
  array(2) {
    [0]=>
    string(1) "2"
    [1]=>
    string(1) "4"
  }
  [2]=>
  array(3) {
    [0]=>
    string(1) "5"
    [1]=>
    string(1) "2"
    [2]=>
    string(1) "4"
  }
}

-~{}~ 27.01.09 13:21:

вот все ресы:

Код:

array(0) {
}

array(1) {
  [0]=>
  string(1) "3"
}

array(0) {
}

array(1) {
  [0]=>
  string(1) "5"
}

array(3) {
  [0]=>
  string(1) "5"
  [1]=>
  string(1) "2"
  [2]=>
  string(1) "4"
}

array(0) {
}

array(1) {
  [0]=>
  string(1) "3"
}

array(0) {
}

array(1) {
  [0]=>
  string(1) "5"
}

array(3) {
  [0]=>
  string(1) "5"
  [1]=>
  string(1) "2"
  [2]=>
  string(1) "4"
}

-~{}~ 27.01.09 13:23:

очень увлекательная получилась отладка, но к сожалению мне необходимо убегать....
если завтра не дотумкаю сам что к чему, то можно будет возобновить диалог ^_^

x-yuri · 27 Янв 2009

что-то у тебя как будто твой метод 2 раза запускается
но в общем обрати внимание на "ресы", с каким из них ты не согласен?

-~{}~ 27.01.09 13:04:

кстати, есть фраза: чтобы понять рекурсию, нужно понять рекурсию ))

Arqin · 29 Янв 2009

доковырял я в конечном итоге этот метод...
собсно вот конечный результат:

PHP:

function getDescendant($val = '') {
	    $rr = array();
	    $rt = array();
	    $res = array();
	    $r1 = array();
	    if (!$val) {
	    	$val = $this->oid;
	    	$r1[] = $val;
	    	}
	    $qq="select OID from CATEGORY where PARENT_OID='{$val}' order by name";
	    $result = $this->cache->query ($qq);
	    while ($row=$result->fetchRow()) {
	      $rt = $this->getDescendant($row['OID']);
	      $rr[]=$row['OID'];
	      $rr = array_merge ($rt, $rr);
	    }
	    $res = array_merge ($r1, $rr);
	    return $res;
    }

проблема была всетаки в хранении промежуточных значений.
и метод выдавал только результат последних веток...

x-yuri · 30 Янв 2009

кстати, первое значение ($this->oid) можно сразу в $rr добавлять

Arqin · 30 Янв 2009

угу... это так тестово-рабочий вариант был.
красоту и оптимизирую потом =)

Помогите с рекурсией

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок

x-yuri

Новичок

Arqin

Новичок