Récursion avec while

**okoweb** · 14/09/2012, 11h33

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...

**rawsrc** · 14/09/2012, 11h54

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

**okoweb** · 14/09/2012, 12h10

Dans ce sens :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**rawsrc** · 14/09/2012, 13h07

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é.

**okoweb** · 14/09/2012, 13h32

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**rawsrc** · 14/09/2012, 13h50

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ?

**Benjamin Delespierre** · 14/09/2012, 16h09

Le même algo en reccursif:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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>";