Récursion avec while

Version imprimable

14/09/2012, 12h33
okoweb

Récursion avec while

Bonjour,
Je trouve la récursion avec un while plus légère qu'une fonction qui appelle elle même. Quelqu'un pourrait m'apprendre ce principe par la boucle while ?
Une application simple serait la bienvenue.

Merci d'avance...

Bonjour,

en simplifiant, la récursivité c'est le fait pour tout ou partie d'un algorithme de s'auto-exécuter.
Et pour le coup while n'est pas récurisif, c'est une boucle qui s'éxécute tant qu'une condition est vérifiée en entrée ou sortie de boucle.

Un peu de lecture ici
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // RECURSIVITE function factorielle($x) { if($x == 0) return 1; else return $x*factorielle($x-1); } // BOUCLE $i = 0; $j = 1; while($i < 10) { $j += $i; $i += 1; }
Est ce que tu ne parlerais pas par hasard de la transformation d'un algorithme récursif en algorithme itératif ?

14/09/2012, 13h10
okoweb
Dans ce sens :
Code:

1 2 3 4 5 6 if ($current = $doc->getElementById($id)) { while ($current = $current->parentNode) { //actions } }
Un autre exemple se déplacer enfant > parent > grand parent ou inversement...
en utilisant while.
14/09/2012, 14h07
rawsrc

Ton exemple n'est pas récursif.
Il équivaut à dire : Tant qu'un noeud parent existe exécuter ces actions sur le parent.
En gros, je ne vois pas trop ce que tu cherches à te faire expliquer.

La seule chose qui pourrait nécessiter des explications c'est la transformation du récursif vers l'itératif. Parfois, ça peut être assez compliqué.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$html =  '<ul>
	<li><a href="#">Accueil</a></li>
	<li><a href="#">Pays</a>
		<ul>
			<li><a href="#">Rca</a></li>
			<li><a href="#">Cameroun</a>
				<ul>
					<li><a href="#">Yaounde</a></li>
					<li><a href="#" id="current">Douala</a>
				</ul>
			</li>
			<li><a href="#">Tchad</a></li>
		</ul>
	</li>
	<li><a href="#">Contact</a></li>
</ul>';
 
$doc = new DOMDocument;
$doc->loadHTML($html);
 
if ($current = $doc->getElementById('current')) {
	while ($current = $current->parentNode) {
		if ($current->nodeName == 'li')
			$current->setAttribute('class', ltrim($current->getAttribute('class') . ' chemin'));
	}
}
 
echo "<pre>" . htmlentities($doc->saveHTML()) . "</pre>";

Résultat :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
<ul>
	<li><a href="#">Accueil</a></li>
	<li class="chemin"><a href="#">Pays</a>
		<ul>
			<li><a href="#">Rca</a></li>
			<li class="chemin"><a href="#">Cameroun</a>
				<ul>
					<li><a href="#">Yaounde</a></li>
					<li class="chemin"><a href="#" id="current">Douala</a></li>
				</ul>
			</li>
			<li><a href="#">Tchad</a></li>
		</ul>
	</li>
	<li><a href="#">Contact</a></li>
</ul>

Observez le boulot de while, remonter récursivement dans l'arborescence pour appliquer des actions. C'est ce que je souhaite comprendre. Comment à chaque nœud il recherche le parent.

moi je procéderais ainsi par une fonction récursive.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
function getbreadcrumb(DOMDocument $doc, $checkclass, $addclass, $tag = null){
	$return = false;
	if ( $anchor = $doc->getElementById($checkclass) ) {
		$parent = $anchor->parentNode;
		addclass($parent, $addclass, $tag);
		$return = $doc->saveHTML();
	}
	return $return;
}
 
function addclass(DOMElement $node, $addclass, $tag){
	if ( $node && $node->nodeName == $tag ) {
		$node->setAttribute('class', $addclass);
		//Recursively		
		$parent = $node->parentNode; //ul
		$parent = $parent->parentNode; //li
		addclass($parent, $addclass, $tag);
	}
}
 
$html =  '<ul>
	<li><a href="#">Accueil</a></li>
	<li><a href="#">Pays</a>
		<ul>
			<li><a href="#">Rca</a></li>
			<li><a href="#">Cameroun</a>
				<ul>
					<li><a href="#">Yaounde</a></li>
					<li><a href="#" id="current">Douala</a>
				</ul>
			</li>
			<li><a href="#">Tchad</a></li>
		</ul>
	</li>
	<li><a href="#">Contact</a></li>
</ul>';
libxml_use_internal_errors(false);
$doc = new DOMDocument();
$doc->loadHTML($html);
$html = getbreadcrumb($doc, 'current', 'chemin', 'li');
echo $html;

C'est plus long. while fait un sale boulot que ne comprend pas.

14/09/2012, 14h50
rawsrc

Citation:

Envoyé par okoweb

Observez le boulot de while, remonter récursivement dans l'arborescence pour appliquer des actions.

Non, while ne remonte pas récursivement l'arborescence. Il ne s'appelle pas lui-même : la boucle initiale s'exécute tant qu'il y a un parent. C'est totalement différent.
while remonte un à un les noeuds. Je tiens encore à te rappeler qu'une fois lancée, c'est la même boucle qui s'exécute tant qu'une condition est vérifiée.

La seule subtilité réside dans l'initialisation de la boucle while et dans ses appels successifs (et pas récursifs, hein) :

Code:

while ($current = $current->parentNode) { ... }

Deux choses sont faites : on se positionne sur le noeud parent et on le transforme en noeud courant. C'est tout.
Ensuite le code s'exécute sur le nouveau noeud courant. Et ainsi de suite tant qu'il existe un noeud parent au noeud courant.

C'est plus clair ?

Le même algo en reccursif:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<?php
 
$html = <<< HTML
<ul>
    <li><a href="#">Accueil</a></li>
    <li><a href="#">Pays</a>
        <ul>
            <li><a href="#">Rca</a></li>
            <li><a href="#">Cameroun</a>
                <ul>
                    <li><a href="#">Yaounde</a></li>
                    <li><a href="#" id="current">Douala</a>
                </ul>
            </li>
            <li><a href="#">Tchad</a></li>
        </ul>
    </li>
    <li><a href="#">Contact</a></li>
</ul>
HTML;
 
$doc = new DOMDocument;
$doc->loadHTML($html);
 
function add_class ($node, $class, $nodename) {
    if (!$node)
        return;
 
    if ($node->nodeName == $nodename)
        $node->setAttribute('class', ltrim($node->getAttribute('class') . " $class"));
 
    add_class($node->parentNode, $class, $nodename);
}
 
 
($current = $doc->getElementById('current')) && add_class($current, 'chemin', 'li');
 
echo "<pre>" . htmlentities($doc->saveHTML()) . "</pre>";

La récursivité n'apporte rien dans ce cas, autant utiliser un bon vieil algo itératif classique :ccool:

21/09/2012, 19h19
okoweb

Citation:

Envoyé par rawsrc

C'est plus clair ?

Oui.
21/09/2012, 19h26
okoweb

Merci à vous tous !:mouarf: