repousser la limite de recursion

Version imprimable

25/01/2018, 23h39
Legro

repousser la limite de recursion

Bonjour,
Je me rends compte qu'une fonction récursive a ses limites, c'est à dire qu'elle ne peut pas s'appeler indéfiniment.
Si je comprends bien ceci est dû au fait que la taille de la pile où les fonctions s'empillent en attendant leur tour, est naturellement limitée.
Ma question est dans le cas où je désire pouvoir faire une plus grande quantité de récursions, dois-je nécéssairement augmenter la mémoire de mon ordi, ou bien il existe un réglage quelque part (dans mon code, dans le compilateur ou dans windows ???) qui permet d'obtenir plus de mou dans la pile ?
Merci.
26/01/2018, 00h57
dalfab

Citation:

Envoyé par Legro

Ma question est dans le cas où je désire pouvoir faire une plus grande quantité de récursions, dois-je nécéssairement augmenter la mémoire de mon ordi, ou bien il existe un réglage quelque part (dans mon code, dans le compilateur ou dans windows ???) qui permet d'obtenir plus de mou dans la pile ?

Non et non.
Une fonction récursive consomme nettement plus de mémoire que son équivalent non récursif. Et elle utilise la pile limitée à quelques MégaOctets, alors que l'équivalent non récursif à accès à toute la mémoire donc quelques GigaOctets. Il n'a y pas photo, il faut transformer la fonction pour qu'elle ne soit plus récursive.

Tu peux faire de la récursivité en utilisant une autre pile que la pile système.
Exemple classique où la récursivité est nécessaire, le parcours d'un arbre simplement chaîné:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <string>
#include <stack>
#include <iostream>
#include <memory>
#include <vector>
#include <functional>
#include <exception>
using namespace std;
using namespace std::placeholders;
 
struct noeud
{
	string nom;
	noeud* pFilsGauche;
	noeud* pFilsDroit;
 
	noeud() : nom(), pFilsGauche(nullptr), pFilsDroit(nullptr) {}
	noeud(string nom)  : nom(nom), pFilsGauche(nullptr), pFilsDroit(nullptr) {}
};

Imagine que tu as une fonction de parcours existante en C++, avec une récursivité naïve:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
typedef function<void(noeud* pNoeud)> callback_parcours_cpp;
 
void parcours_arbre(noeud* pNoeud, callback_parcours_cpp cbPrefixe, callback_parcours_cpp cbInfixe, callback_parcours_cpp cbPostfixe)
{
	if(pNoeud==nullptr) { return; }
	if(cbPrefixe) { cbPrefixe(pNoeud); }
	parcours_arbre(pNoeud->pFilsGauche, cbPrefixe, cbInfixe, cbPostfixe);
	if(cbInfixe) { cbInfixe(pNoeud); }
	parcours_arbre(pNoeud->pFilsDroit, cbPrefixe, cbInfixe, cbPostfixe);
	if(cbPostfixe) { cbPostfixe(pNoeud); }
}

Avec un code pour l'appeler:

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
43
44
45
46
class memoire_noeuds
{
	vector<unique_ptr<noeud>> liste;
public:
	noeud* nouveau(string nom)
	{
		noeud* pNoeud = new noeud(nom);
		liste.push_back(unique_ptr<noeud>(pNoeud));
		return pNoeud;
	}
};
 
 
class afficheur
{
	int indent_;
public:
	afficheur() : indent_() {}
	void prefixe( noeud* pNoeud) { check(pNoeud); int indent=indent_++; cout << string(indent, ' ') << "<noeud  nom=\"" << pNoeud->nom << "\">" <<endl; }
	void infixe(  noeud* pNoeud) { check(pNoeud); int indent=indent_;   cout << string(indent, ' ') << "<infixe nom=\"" << pNoeud->nom << "\"/>" <<endl; }
	void postfixe(noeud* pNoeud) { check(pNoeud); int indent=--indent_; cout << string(indent, ' ') << "</noeud nom=\"" << pNoeud->nom << "\">" <<endl; }
private:
	void check(noeud* pNoeud)
	{
		if(pNoeud==nullptr)
			throw invalid_argument("pNoeud est nul.");
		if(pNoeud->nom.length() > 20)
			throw invalid_argument("pNoeud a un nom plus long que le plus gros qu'on accepte pour l'instant, il doit etre corrompu");
		if(indent_ > 5)
			throw logic_error("indent est hors de controle");
	}
};
 
 
int main(void)
{
	memoire_noeuds memoireNoeuds;
	noeud* pRacine = memoireNoeuds.nouveau("Racine");
	pRacine->pFilsGauche = memoireNoeuds.nouveau("Fils Gauche");
	pRacine->pFilsGauche->pFilsDroit = memoireNoeuds.nouveau("Petit-Fils");
	pRacine->pFilsDroit = memoireNoeuds.nouveau("Fils Droit");
 
	afficheur aff;
	parcours_arbre(pRacine, bind(&afficheur::prefixe, &aff, _1), bind(&afficheur::infixe, &aff, _1), bind(&afficheur::postfixe, &aff, _1));
	return 0;
}

Ici l'arbre a au plus quatre nœuds, mais s'il en avait des millions, la pile exploserait.
Maintenant, si plutôt qu'utiliser la pile système, on utilisait une pile qui alloue sa mémoire sur le tas?

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
43
struct etat_parcours
{
	noeud* pNoeudActuel;
	int dernierFilsTraite; //-1 si on vient d'entrer, 0 si on revient du gauche, 1 si on revient du droit
 
	etat_parcours(noeud* p, int f) : pNoeudActuel(p), dernierFilsTraite(f) {}
};
 
void parcours_arbre_nonsysteme(noeud* pRacine, callback_parcours_cpp cbPrefixe, callback_parcours_cpp cbInfixe, callback_parcours_cpp cbPostfixe)
{
	stack<etat_parcours> pile;
	pile.push(etat_parcours(pRacine, -1));
 
	while(!pile.empty())
	{
		etat_parcours etat = pile.top();
		pile.pop();
		noeud* pNoeud = etat.pNoeudActuel;
		//cout << "Taille pile: " << etat.size() << "Noeud depile:" << () << "Dernier fils traite:" << etat.dernierFilsTraite << endl;
 
		switch(etat.dernierFilsTraite)
		{
		case -1: //On vient d'entrer
			if(pNoeud==nullptr) { break; } //Noeud vide: rien du tout, on laisse remonter (le break quitte le switch)
			if(cbPrefixe) { cbPrefixe(pNoeud); }
 
			//Le prochain à parcourir est le fils gauche, puis il faudra revenir à ce noeud
			pile.push(etat_parcours(pNoeud, 0));
			pile.push(etat_parcours(pNoeud->pFilsGauche, -1));
			break;
		case 0: //On revient du fils gauche
			if(cbInfixe) { cbInfixe(pNoeud); }
			//Le prochain à parcourir est le fils droit, puis il faudra revenir à ce noeud
			pile.push(etat_parcours(pNoeud, 1));
			pile.push(etat_parcours(pNoeud->pFilsDroit, -1));
			break;
		case 1: //On revient du fils droit
			if(cbPostfixe) { cbPostfixe(pNoeud); }
			//On laisse remonter
			break;
		}
	}
}

Ici on a toujours de la récursivité, on utilise toujours une pile pour savoir où on en est (avec un arbre simplement chaîné, on n'a pas le choix) mais on n'utilise plus la pile système, on a donc accès à toute la mémoire que l'ordinateur peut offrir.

28/01/2018, 06h11
koala01

Salut,

La première règle, c'est déjà de n'utiliser la récursivité que ... contraint et forcé:

Il arrive en effet très souvent que l'on puisse obtenir un résultat tout à fait équivalent à la récursivité en utilisant une "simple boucle", et ce, sans que cela ne complique la logique outre mesure. Si tu es dans un cas pareil, tu dois utiliser une boucle (la récursivité pour calculer la factorielle ou l'exponentielle, par exemple, n'a absolument aucun sens )

Si tu n'as pas d'autre choix que d'utiliser la récursivité, essaye de la rendre terminale (c'est, en gros, la technique proposée par médinoc :D ). Cela économisera une bonne partie de ta pile d'appel ;)

Si tu es dans l'impossibilité de rendre ta fonction récursive terminale (j'aimerais savoir laquelle), tu peux envisager d'augmenter la taille de la pile (certains compilateurs l'autorisent), mais ce ne sera jamais qu'un "pis allé", vu que -- tôt ou tard -- cette nouvelle limite sera aussi atteinte ... Et puis, je ne suis pas sur du tout que les compilateurs qui autorisent cette pratique n'impose pas malgré tout une limite quant à la taille maximale de la pile ;)
28/01/2018, 09h45
Legro

Merci à tous de vos réponses.

En fait avant de poster ma question j'avais utilisé le moteur de recherche et j'étais tombé sur ça :
https://www.developpez.net/forums/d1...ite-recursion/
et je m'étais donc demandé si en C++ il y avait également des moyens d'utiliser la récursion à grande échelle.

Maintenent pour mon problème je suis en train de me creuser la tête pour voir comment n'utiliser que des boucles, pas évident.
Il ne fait aucun doute que la version récursive de mon algoritme était bien plus simple, mais bon ça me fait de l'exercice...

En tout cas ce que j'ai bien compris pour le moment c'est que les récursions c'est comme les tartes aux fraises : de temps à autres et à petite dose.;)
28/01/2018, 13h29
Médinoc

En parlant d'éviter la récursivité: L'arbre binaire de mon exemple? S'il était doublement chaîné (c'est-à-dire, si en plus des pointeurs déjà présents, chaque fils avait un pointeur vers son nœud "père"), alors il serait possible de parcourir l'arbre itérativement, sans aucune pile.
30/01/2018, 00h04
JolyLoic

Si l'algorithme s'exprime vraiment plus naturellement de manière récursive, il y a peut-être moyen de pousser un peu les limites :
- Limiter l'espace pris sur la pile par chaque appel de fonction (en réduisant autant que possible la mémoire nécessaire pour les variables locales, les arguments passés à la fonction... Par exemple éviter un std::array<double, 200000>)
- Travailler en mode optimisé, pas en mode debug : Outre que le compilateur va de lui même supprimer quelques variables inutiles (cf point précédent), l'inlining va dans certains cas réduire le nombre de fonctions dans la pile
- Modifier les options du compilateur pour avoir une pile plus grande (sachant qu'il y a une limite maximale). Par exemple, sous windows : https://docs.microsoft.com/en-us/cpp...set-stack-size
30/01/2018, 13h12
Luc Hermitte

A savoir que si tu arrives/peux transformer ta récursivité en récursivité terminale, alors il y aura de fortes chances que ton compilateur saura transformer l'appel récursif en boucle. En contrôlant l'assembleur généré/les perfs, cela peut se vérifier.
Maintenant, ce n'est pas possible avec tous les algorithmes.
30/01/2018, 15h40
Médinoc

Notamment, je ne vois pas trop comment faire de la récursivité terminale pour un algorithme qui a besoin de plus d'un appel récursif (notamment le parcours d'arbre).
Contrairement aux fonctions mathématiques de type X_n-1, qui crient "je peux être implémenté en itératif".
31/01/2018, 16h46
koala01

En fait, il y a moyen de transformer un parcours d'arbre en récursif terminal. Par contre, je ne suis pas sur du tout qu'il y aura moyen de remplacer ce genre de parcours par une boucle...

Citation:

Envoyé par Médinoc

Notamment, je ne vois pas trop comment faire de la récursivité terminale pour un algorithme qui a besoin de plus d'un appel récursif (notamment le parcours d'arbre).

En multipliant les accumulateurs, mais ça n'a pas vraiment de sens dans un langage comme C++.

Par exemple la suite de Fibonacci F_{n+2} = F_{n+1} + F_n :
Code:

1 2 3 4 5 6 7 8 unsigned fibonacci_impl(unsigned n, unsigned acc1, unsigned acc2) { return n == 0 ? acc1 : fibonacci_impl(n-1, acc1+acc2, acc1); } unsigned fibonacci(unsigned n) { return fibonacci_impl(n, 0, 1); }
Pour un arbre de degré n, on peut écrire son parcourt en tailrec avec n accumulateurs. En théorie, le compilateur peut optimiser ce parcourt en boucle, et peut déplier les boucles. Mais celui-ci est un programme au ressources finies et ne peut pas voir au delà d'un certain niveau d'abstractions et seule l'expérimentation peut confirmer ou infirmer cette capacité.

02/02/2018, 13h18
Médinoc

Mais Fibonacci est une fonction mathématique de type X_n-1 X_n-2, implémentable en itératif simplement en mémorisant les deux dernières valeurs.
Ça n'a rien à voir avec un parcours d'arbre simplement chaîné.
02/02/2018, 13h43
prgasp77

La même logique est applicable : un accumulateur peut être une position dans un arbre ou un arbre lui-même. Mais pour une raison qui reste à déterminer j'ai préféré le faire sur un exemple simple.