Hello tout le monde,

Je viens vers vous afin d'implémenter mon tout premier arbre binaire. J'ai tout d'abord plusieurs questions sur les fonctions de l'arbre binaire. Je sais implémenter les lises chaînées et j'ai lu qu'un arbre binaire n'est en réalité que plusieurs listes chainées. Seulement, à la différence d'une liste chaînée, on ne possède pas un Dummy Tail qui permet d'avoir l'itérateur de fin et donc comment est il possible de parcourir un arbre chainée avec une boucle par exemple ? Comment automatiquement lier les nodes entre eux ? Avec le dummy tail de la liste chainée, c'est assez simple puisqu'on peut Push et POP au début ou à la fin où même d'ailleurs où on voit et y a toujours un node avant et après donc on a plus qu'à reconfigurer les pointers et le tour est joué. Là dans le cas de l'arbre binaire, l'utilisateur doit il lier lui même les nodes ?

Pour l'idée d'API j'ai pensé aux fonctions suivantes :

CreateNodes;

RemoveNodes;

SearchInTree;

SizeTree;

IsEmpty;

GetData;

SetData;

NbrLevelsTree;

J'imagine que y a des fonctions manquantes/plus pertinentes donc n'hésitez pas à me le dire. Merci

PS : J'ai vu/lu que les arbres binaires emploient pas mal la récursivitié. Est il possible de faire sans ? J'ai toujours appris que la récursivité avait une compelxité exponentielle O(2^n) et que c'était pas bon du tout.

-
Edité par Moshé Frydmann 17 janvier 2021 à 9:58:13

Ton explication est un peu confuse !

Tu devrais commencer par l'arbre binaire de recherche, qui est un des plus simple à implémenter.

Dans les arbres binaire les nœuds ont deux branches (deux pointeurs) vers les nœuds suivants (gauche et droit) et les données y sont ranger selon un critère de tri. Les données y sont donc trié. Ce qui en facilite la recherche (Il n'y a pas besoin de parcourir tout l'arbre, c'est donc plus rapide qu'une liste).

Tu peux commencer par deux fonctions, celle d’insertion et celle de recherche, les deux peuvent être implémentée par une boucle. Par contre les fonctions de parcours complet de l'arbre sont extrêmement plus simple en récursif (tu peux faire celle qui affiche l'arbre, même si en général elle n'est pas utile).

PS : Il y a beaucoup à ce sujet sur le web, il suffit juste de chercher !

Shémo a écrit:

Hello tout le monde,

Je viens vers vous afin d'implémenter mon tout premier arbre binaire. J'ai tout d'abord plusieurs questions sur les fonctions de l'arbre binaire. Je sais implémenter les lises chaînées et j'ai lu qu'un arbre binaire n'est en réalité que plusieurs listes chainées. 

Hello,

Il y a plusieurs façons très différentes d'implémenter en C une structure d'arbre. Une affirmation comme «un arbre binaire n'est en réalité que plusieurs listes chainées» n'est pas fausse en soi, c'est en effet comme si tu avais une liste chaînée mais au lieu d'avoir au plus un seul suivant tu peux en avoir plusieurs ; 2 au plus dans le cas des arbres binaires, n dans le cas des arbres n-aires.

Mais, bien souvent on voit les choses sous un autre angle : une liste est un cas dégénéré d'arbre, un cas où chaque nœud n'a qu'un enfant au plus. On parle de cas dégénéré (ce qui semble plutôt négatif) car pour les structures simples (et classiques) ces cas représentent le pire cas pour un algorithme.

Par exemple dans le cas d'un arbre binaire de recherche classique, si tu te retrouves avec un cas où ton arbre est une liste de n éléments, alors une recherche prendra au pire n étapes, alors qu'en moyenne on s'attend plus à un nombre d'étape proportionnel à log₂(n) (avec log₂ le logarithme en base 2). On parle dans ce cas d'un algorithme de recherche en O(n) ou linéaire.

C'est aussi pour cela qu'on a créé des structure qui vont garantir un algorithme de recherche en O(log n) dans tous les cas de figure. Ces structure de données sont également des arbre binaires (en général) mais que l'on dit équilibrés car leur partie gauche et droite auront sensiblement la même taille tout le temps (arbre AVL, ou roge/noir par exemple).

Shémo a écrit:

Seulement, à la différence d'une liste chaînée, on ne possède pas un Dummy Tail qui permet d'avoir l'itérateur de fin et donc comment est il possible de parcourir un arbre chainée avec une boucle par exemple ? Comment automatiquement lier les nodes entre eux ? Avec le dummy tail de la liste chainée, c'est assez simple puisqu'on peut Push et POP au début ou à la fin où même d'ailleurs où on voit et y a toujours un node avant et après donc on a plus qu'à reconfigurer les pointers et le tour est joué. Là dans le cas de l'arbre binaire, l'utilisateur doit il lier lui même les nodes ? 

Si tu n'implémentes pas une version spécifique d'arbre binaire (comme un arbre binaire de recherche aka BST binary search tree, ou AVL, un B-Tree, ou .…) qui ont des fonctions d'accès spécifiques (insertion garantissant un ordre par exemple) tu n'as pas de stratégie particulière de placement de nœuds,

Toi qui entre dans le domaine fabuleux des structure de données récursives, oublie un moment ta volonté de vouloir implémenter un algo itératif. Les algo récursifs vont à merveille avec les structure de données récursives comme les arbre (ou les listes ou les graphes ou …). C'est une façon de penser qui te viendra naturellement avec le temps. Par exemple c'est la définition même de la hauteur d'un arbre qui est récursive :

la hauteur h(T) d'un arbre T est 0 si l'arbre est vide ou sinon 1+max(hauteur(fils_gauche(T)), hauteur(fils_droit(T)).

Shémo a écrit:

PS : J'ai vu/lu que les arbres binaires emploient pas mal la récursivitié. Est il possible de faire sans ? J'ai toujours appris que la récursivité avait une compelxité exponentielle O(2^n) et que c'était pas bon du tout.

-
Edité par Shémo il y a environ 1 heure

On t'a appris de la merde (ou tu auras mal compris).

Si tu veux un contre exemple : le calcul de la hauteur d'un BST  de n nœuds est au pire linéaire … elle est même au pire en O(log n) pour les arbres binaires équilibrés.

Si tu veux une bonne référence lecture →

https://book4you.org/book/541024/5b1659 The Algorithm Design Manual de Skiena

https://book4you.org/book/986690/1e31b0 Introduction to Algorithms de Cormen and Co

Je peux t'en donner d'autres si tu veux.

Je pense que le conseil de Rouloude est bon, lis pour apprendre ce qu'est un BST d'abord et ensuite essaye d'en créer une implémentation en C.

La seule addition aux fonctions que propose Rouloude est que pour toute structure de donnée tu dois fournir :

• un moyen d'en construire un représentant → une fonction de création (bst_create oar exemple)
• un moyen de libérer les ressources utilisées par un représentant → une fonction de destruction (bst_delete …)
• un moyen d'accéder en lecture seule aux états d'un représentant → une ou plusieurs fonctions d'accès (bst_height, bst_size, …)
• un moyen de modifier un représentant → ajouter un élément (bst_add)
• …

Ça c'est l'API publique, il y a aussi l'API privée → création d'un nœud par exemple …

Si tu te débrouille bien tu peux avoir la même API en te foutant complètement de l'implémentation concrète de l'arbre (par pointeurs, par index, par tableau, …). Tu pourras même passer de l'une à l'autre suivant tes besoins (insertion rapide vs recherche rapide vs taille mémoire vs …)

Merci pour ces précisions. Effectivement j'ai suivi le conseil de Rouloude en démarrant l'implémentation d'un simple BST. J'ai implémenté la création de nodes, l'insertion, l'impression et la recherche. Je vous mets les codes ici :

/******************************************************************************************
*Title: tree
*Author : 
*Reviewer: 
*Description:
*Status: in developpment
*****************************************************************************************/
#ifndef __TREE_BINARY_H__
#define __TREE_BINARY_H__

typedef struct node node_t;

#include <stddef.h> /* size_t, ssize_t */

/**************************************************************
Description : Insert node depend of the logic of the tree : if new key is less that the previous, insert left place. If bigger, right place.
return pointer to new node
Complexity : O(log n) */

node_t *Insert(node_t *node, unsigned int key);

/*Description : Print in order all element of the tree
Complexity : O(n) */

void PrintInOrder(node_t *root);

/*Description : Research number in the tree/
Return : 1 if found. 0 if not.
Complexity : O(n) */

int SearchNumber(node_t *root, int nbr);


#endif /*__TREE_BINARY_H__ */

Ici le .c :

/******************************************************************************************
*Title: tree
*Author : 
*Reviewer: 
*Description:
*Status: in developpment
*****************************************************************************************/
#include <stdlib.h> /* malloc / free*/ 
#include <stdio.h> /* prinf=tf */
#include <assert.h> /* assert */
#include "tree.h" 

node_t *CreateNode(unsigned int item);

struct node
{
    unsigned int key;
    struct node *left;
    struct node *right;
};

node_t *CreateNode(unsigned int item) 
{ 
    node_t *temp = (node_t *)malloc(sizeof(node_t)); 
    temp->key = item; 
    temp->left = NULL;
    temp->right = NULL;
     
    return temp; 
} 

node_t *Insert(node_t *node, unsigned int key) 
{ 

    if (NULL == node) 
    {
        return CreateNode(key); 
    }
  
    if (key < node->key) 
    {
        node->left = Insert(node->left, key); 
    }
    else if (key > node->key) 
    {
        node->right = Insert(node->right, key); 
    }
  
    return node; 
} 

void PrintInOrder(node_t *root)
{ 
    if (NULL != root) 
    { 
        PrintInOrder(root->left); 
        printf("%d \n", root->key); 
        PrintInOrder(root->right); 
    } 
} 

int SearchNumber(node_t *root, int nbr)
{
	node_t *tmp = root;

	
	while (tmp->key != nbr && NULL != tmp)
	{
		if (nbr < tmp->key)
		{
			tmp = tmp->left;
		}
		else
		{
			tmp = tmp->right;
		}	
	}
	
	return (tmp->key == nbr);

}

Ainsi que le fichier test :

/******************************************************************************************
*Title: tree
*Author : 
*Reviewer: 
*Description:
*Status: in developpment
*****************************************************************************************/
#include <stdio.h> /* printf */
#include "tree.h" 

void TestTree();
void IntCompare(int input, int output, char *string);

enum end_prog
{
	SUCCESS = 0, FAILED = 1
};

#define KNRM  "\x1B[0m"
#define KRED  "\x1B[31m"
#define KGRN  "\x1B[32m"
#define KYEL  "\x1B[33m"
#define KBLU  "\x1B[34m"
#define KMAG  "\x1B[35m"

int main(void)
{
	TestTree();
	
	return SUCCESS;
}

void TestTree()
{
	node_t *root = NULL; 
    root = Insert(root, 50); 
    Insert(root, 30); 
    Insert(root, 20); 
    Insert(root, 40); 
    Insert(root, 70); 
    Insert(root, 60); 
    Insert(root, 80); 
  
    PrintInOrder(root); 
  	IntCompare(SearchNumber(root, 80), 1, "Research");
}

void IntCompare(int input, int output, char *string)
{
	if (input == output)
	{
		printf(""KGRN"SUCCESS"KNRM" %s in the tree\n", string);
	}
	else
	{
		printf(""KRED"ERROR"KNRM" %s in the tree\n", string);
	}
}

Bon ne faites pas gaffe aux tests j'ai juste vérifié que ca fonctionnait sans chercher la faute.

Maintenant, que pourrais-je implémenter de plus sur cette base ?

-
Edité par Moshé Frydmann 17 janvier 2021 à 13:46:00

L'insertion d'une valeur dans un BST est linéaire et non logarithmique.

Tsss … une recherche itérative 🙄🤣

int SearchNumber(node_t *root, int nbr)
{
    if      (root==NULL)        return 0;
    else if (root->key == nbr)  return 1;
    else if (root->key <  nbr)  return SearchNumber(root->right, nbr);
    else   /*root->key >  nbr*/ return SearchNumber(root->left, nbr);
}

Ton implémentation itérative ne fonctionne pas dans le cas d'un arbre vide donné en paramètre.

Il ne faut pas caster le retour de malloc en C.

Tu devrais avoir une structure représentant un arbre autre qu'un simple pointeur sur un nœud.

Shémo a écrit:

Maintenant, que pourrais-je implémenter de plus sur cette base ?

-
Edité par Shémo il y a 8 minutes

Corriger la base puis … comme c'est écrit dans les deux références que je t'ai données :

«The basic operations supported by binary trees are searching, traversal, insertion, and deletion.»

trouver une valeur, la plus grande, l;a plus petite, toutes les valeurs dans un intervalle, toutes celles plus grandes qu'une valeur donnée, plus petites qu'une valeur donnée …

Appliquer une fonction à chaque nœud = faire un map, reduce, …

-
Edité par White Crow 17 janvier 2021 à 13:59:25

J'ai rajouté un assert dans le search si l'arbre est vide, du coup ca stop le programme.

Ok je viens de voir ce que tu m'as écris sur la recherche des valeurs. Je vais essayer d'implémenter cela!

PS : WhiteCrow, j'ai du mal à comprendre dans cet exemple pourquoi la recherche d'un nbr est mieux par récursivité plutôt que par itération ?

-
Edité par Moshé Frydmann 17 janvier 2021 à 14:24:54

Shémo a écrit:

PS : WhiteCrow, j'ai du mal à comprendre dans cet exemple pourquoi la recherche d'un nbr est mieux par récursivité plutôt que par itération ?

Moi aussi ?

WhiteCrow, j'ai du mal à comprendre dans cet exemple pourquoi la recherche d'un nbr est mieux par récursivité plutôt que par itération ?

Mieux …. pas mieux mais plus dans le ton. 

Nous aurions tort de nous en priver car :

• les algorithmes récursifs sont naturels avec une structure de donnée elle-même récursive. Les définitions et notions s'énoncent simplement et récursivement sans qu'on y fasse même attention. Il n'y a rien de plus simple qu'implémenter récursivement une définition récursive 😆
• mis à part les algo simples, comme la recherche de valeur dans un BST, la plupart des algo seront récursifs. Tu pourras les dérécursiver mais ce ne sera pas en général efficace de le faire. Ni efficace ni plus lisible d'ailleurs, bien au contraire.
• les compilos modernes reconnaissent certaines formes d'appels récursifs et dérécursivent très efficacement : on a le beurre et l'argent du beurre ; la lisibilité et l'intelligence du compilo.

Comme tu auras de toute façon à te frotter à ce genre de programmation (et attention c'est encore plus bluffant avec la programmation dynamique) autant le faire pour t'y habituer.

Alors attention ! Ne pas utiliser  les assert comme substitut à une vérification. N'oublie jamais que les assert sont des macros qui ne sont traduites en code que si la macro NDEBUG est définie … donc plus de check au runtime ! absolument pas ce qu'on veut puisque dans ton implémentation tu as la possibilité de créer un arbre vide … donc la nécessité de traiter ce cas comme un cas valide.

Tu as raison pour l'assert. Dans ce cas on ne veut pas stopper le programme mais juste savoir que l'arbre est vide.

Pour la récursivité je comprends. J'ai lu dans le livre sur la programmation en C que pour les arbres, la récursivité est quelque chose de standard. C'est juste que au niveau de la compléxité j'avais lu qu'il fallait éviter la récursivité... MAIS comme tu le dis, c'est une notion qu'il faut voir et comprendre et savoir utiliser. Je veux juste avoir le code le plus optimale possible.

J'ai aussi implémenter la fonction Delete en récursive d'ailleurs lol

void BstDelete(node_t *root)
{
	node_t *tmp = root;
	
	if (NULL != root)
	{
				
		BstDelete(root->left);
		root->left = NULL;
		BstDelete(root->right);
		root->right = NULL;
		free(root);
		root = NULL;
	}
}

-
Edité par Moshé Frydmann 17 janvier 2021 à 15:47:24

Shémo a écrit:

Tu as raison pour l'assert. Dans ce cas on ne veut pas stopper le programme mais juste savoir que l'arbre est vide.

C'est surtout que les assertions ne sont pas faites pour ça. Elles sont faites pour vérifier que les fonctions sont bien utilisées comme elles le devraient suivant leur spécification → elles captent les erreurs de programmation du développeur pas les erreurs dues à l'utilisation erronée par un utilisateur du programme.

Shémo a écrit:

C'est juste que au niveau de la compléxité j'avais lu qu'il fallait éviter la récursivité... 

Oublie ça … mais genre immédiatement …

quicksort récursif est-il moins performant qu'un bubble sort itératif ? qu'un quicksort itératif ?

quicksort itératif est-il plus lisible qu'un quicksort récursif ?

quicksort c'est une règle de Quiddich ? lool j'ai même pas compris tes dernières phrases

Ok bon de toute façon faut savoir utiliser les récursives donc c'est l'occasion de s'y mettre

Shémo a écrit:

quicksort c'est une règle de Quiddich ? lool j'ai même pas compris tes dernières phrases

Ok bon de toute façon faut savoir utiliser les récursives donc c'est l'occasion de s'y mettre

Quicksort, ou tri rapide en français, est un tri qui comme son nom l'indique est … rapide.

Maîtriser les algos de tri classiques est un plus, il faut au minimum les connaître :

les tris par comparaison entre éléments

• bubble sort / cocktail sort
• insertion sort / selection sort
• quicksort
• heapsort → le nom vient de la sdd de tas (heap) qui est une structure arborescente très pratique
• mergesort
• Shell sort
• …

les tris sans comparaison entre éléments

• radixsort
• binsort/bucketsort

Il y a les versions stables (deux éléments ayant des clés de tri identiques gardent le même ordre avant et après tri) et non -stables, les version en place (les algos sont en O(1) en espace) ou non …

Un vrai bestiaire qu'il est, àmha, important de connaître. Cela devrait faire partie de la culture G de tout dèv.

Shémo a écrit:

Ok bon de toute façon faut savoir utiliser les récursives donc c'est l'occasion de s'y mettre

👍

Avec ces algos on peut tout trier ? Comme une list chaînée ou un arbre par exemple ?

Un algo de tri est juste un algo. Par exemple l'essence de quick sort est :

• on choisit un pivot ;
• on sépare les données en 2, celles plus petites que le pivot d'un côté et celles plus grandes de l'autre ;
• pour chaque côté on recommence récursivement.

Tu peux le faire aussi bien sur un tableau que sur une liste … il n'y aura pas les même performances. Certains tris sont plus adaptés à certaines structures qu'à d'autres.

Le tri par tas, heapsort est intéressant dans le sens où il trie un tableau en l'interprétant comme un arbre un peu particulier qu'on appelle un tas …

Il y a aussi des tris sur les graphes comme le tri topologique.

Oui … c'est un monde merveilleux

Intéressant ! Donc dans un tri récursif ou à chaque tour on diminue le nombre d’éléments à trier, on tend donc à arriver vers 0 ou 1. On est sur une complexité de O(log n), right ?

Shémo a écrit:

Intéressant ! Donc dans un tri récursif ou à chaque tour on diminue le nombre d’éléments à trier, on tend donc à arriver vers 0 ou 1. On est sur une complexité de O(log n), right ?

Alors comme pour trier n nombres il faut au minimum du minimum les lire, un algo de tri sera toujours en temps en O(n) au mieux du mieux, il est impossible de faire moins.

Pour les tris par comparaisons d'éléments on ne peut pas faire mieux qu'un O( n log n ). En fait trier en comparant les valeurs entre elles revient à faire des choix pour trouver laquelle parmi les n! permutations est celle qui est ordonnée. Trouver une donnée parmi n! ne peut se faire qu'en O(log n!) au mieux, et comme n!≤nⁿ on a log(n!)≤log(nⁿ) = n log n. La mesure est faite soit en terme de nombre d'échanges (pour les tris en place) ou de copies (pour les tris non en place).

Pour les tris qui ne comparent pas les éléments entre eux, la limite est plus basse, enfin en quelque sorte. Si il faut au plus b bits pour coder un élément alors la complexité en temps est en O(b×n). Du coup pour trier des entiers 64 bits il existe des algos ne O(n). C'est le genre de tri qu'on utilise pour trier les jeux de 32 cartes en 5 passes à la main quand on est informagicien lool.

De plus n'oublie pas qu'on peut toujours dérécursiver n'importe quelle fonction récursive pour obtenir une version itérative en gardant la même complexité temporelle …

Le compilateur C  traduit les appels de fonctions par des instructions machines qui agissent sur une pile explicite. Que les fonctions soient récursives ou pas, c'est pareil.  Donc c'est pareil, même complexité.

Pour écrire une version non récursive, si c'est pour faire le boulot du compilo à sa place, c'est pas la peine.  Par contre si on arrive à éliminer l'utilisation de la pile on peut y gagner.  Mais c'est pas simple, en dehors des cas évidents de récursion terminale (Quand il y a un seul appel récursif, tout à la fin)

-
Edité par michelbillaud 18 janvier 2021 à 11:33:46

Intéressant. Merci pour ces réponses. Je vais essayer de rajouter les fonctions ; lecture latérales, nbr de niveaux et de feuilles. Je vais aller voir ce qui est proposé pour ce type de functions.

remarquez que parfois, le compilateur C, qui n'est pas la moitié d'une andouille, est capable de remplacer la récursion terminale par une boucle.

Exemple, la factorielle maudite (*)

int fac(int n) 
{
   if (n == 0) 
     return 1;
   else 
     return n*fac(n-1);
}

est transformée (gcc -O2) en

fac:
	movl	$1, %eax
	testl	%edi, %edi
	je	.L1
.L2:
	imull	%edi, %eax
	subl	$1, %edi
	jne	.L2
.L1:
	ret

(*) pédagogiquement un très mauvais exemple pour les gens qui 1. ont appris précédemment à programmer avec des boucles (et donc se demandent pourquoi on vient les emmerder avec un truc qu'ils savent déjà faire autrement et qui n'a pas l'air plus simple) 2. n'en ont en fait rien à péter de la factorielle, pas plus que de fibonnacci. 3. Sont totalement insensibles aux charmes de l'axiomatique de Peano.

-
Edité par michelbillaud 18 janvier 2021 à 11:44:52

MichelBillaud, une petite question technique : lors de l'appel d'une fonction sur la stack, ce qui est envoyé en premier sont les registres EAX, EBX, ECX, etc... ensuite l'adresse de retour, ensuite le poiteur EBP, suivi par la stack frame (argument, variables, etc...) ce qui a pour conséquence de bouger le pointeur ESP en haut de la stack. Ensuite y a aussi le poiteur(j'ai oublié le nom, IP je crois ?) qui pointe sur la prochaine actioon à éxécute.

Corrige moi stp car je pense me tromper.

Pour revenir sur le sujet, donc si je comprends bien les compilateurs modernes optimise en réalité la récursivité si besoin et donc ce n'est plus si "mauvais" d'utiliser des récursies à la place d'autres compléxité comme O(n) par exemple ?

Si tu veux savoir, regarde le code.

Ça n'a jamais été mauvais d'employer des fonctions récursives bien écrites, et ça ne change strictement rien à la complexité temporelle, on te l'a déjà dit. (*)

Ce qui peut changer, c'est l'espace utilisé sur la pile, par des "cadres" qui s'ajoutent les uns au dessus des autres. Problème = nombre de cadres x taille de chacun..

(*) tu as peut être été marqué par un très mauvais exemple qu'on t'a montré, genre fibonacci naïf, qui prend un temps exponentiel parce que suivre directement la definition, ce n'est pas la bonne façon de la calculer récursivement.  On arrive même à le faire en temps logarithmique, parce que le couple ( fib(2n), fib(2n+1)) s'exprime en fonction de (fib(n), fib(n+1)).

-
Edité par michelbillaud 18 janvier 2021 à 14:26:37

Je ne suis pas encore très familier avec le code assembleur lol J'ai déjà essayé quelques fois de comprendre le code assembleur de mon main mais c'est pas si simple

Et c'est différent selon que l'on est en x86 ou x86-64

X86       c'est par la pile

x86-64  4 registres puis le reste sur la pile !

Et ça peut varier selon les convention d'appel !

Ça n'est utile que si tu souhaites écrire des fonctions en asm.

Je ne sais pas encore ce que c'est asm mais disons que c'est histoire de comprendre en profondeur ce qu'il se passe.

asm -> assembleur

Logique... merci

Est ce aussi utile de connaitre cela si on veut bosser sur les appels systèmes ? Et plus précisémment si on veut programmer un SHELL par exemple ?

• ça dépend de ce qu'on appelle bosser sur les appels système
• pour programmer un shell on s'en passe très bien.
• est-ce important de savoir que les ordinateurs, ça marche avec de l'électricité ?
• C'est pas de l'assembleur, c'est du langage d'assemblage (soyons pédants jusqu'au bout).

-
Edité par michelbillaud 18 janvier 2021 à 17:27:47

michelbillaud a écrit:

remarquez que parfois, le compilateur C, qui n'est pas la moitié d'une andouille, est capable de remplacer la récursion terminale par une boucle.

Exemple, la factorielle maudite (*)

int fac(int n) 
{
   if (n == 0) 
     return 1;
   else 
     return n*fac(n-1);
}

[...]

Ta fonction fac n'est une fonction récursive terminale. La récursion terminale est un cas où tout appel récursif est la dernière action, ce qui n'est pas le cas dans ton exemple puisqu'il y a une multiplication entre l'appel récursif et le retour d'appel.

Une version récursive terminale serait plutôt :

int fac_recter(int n, int f)
{
    if (n<2) return f;
    else     return fac_recter( n-1, f*n );
}

int factorial( int n )
{
    return fac_recter(n, 1);
}

Mais c'est clair, les compilos C modernes gèrent bien la dérécursivation (et hop un joli néologisme).

Le passage par une autre fonction auxiliaire qui utilise un parametre tampon, pour aller vers une fonction terminale récursive qui se transformer boucle c'est assez standard et bien étudié depuis les années 70.

Mais peu importe, le point c'est que le compilo s'en débrouille. Parfois.

Pas le courage de vérifier maintenant, mais il me semble que gcc n'y arrivait pas avec une expression conditionnelle

    return n == 0 ? 1 : n*fac(n-1);

-
Edité par michelbillaud 18 janvier 2021 à 22:29:54