Bonjour,

[En réponse à un message de ce fil : factoriel.]

Citation : noob4ever

@candide Tu penses à quoi d'autre que la factorielle donc ?

Si j'avais une intro rapide à initier à la récursivité en C, voici ce que je commencerais par expliquer. Bien sûr, cela reste assez loin d'un traitement complet. En particulier, cela manque d'exemples "positifs", "utiles" ou réels.



Une fonction C peut être récursive ie s'appeler elle-même. Voici un exemple artificiel dans son contenu mais assez typique de fonction récursive. Il s'agit d'une implémentation récursive du banal calcul du produit de deux entiers :

#include <stdio.h>

/* Retourne le produit n*x où n>=0 */
int produit(int n, int x)
{
  if (n > 0)
    return produit(n - 1, x) + x;
  else
    return 0;
}

int main(void)
{
  int n = 8, x = 5;

  printf("%d * %d = %d\n", n, x, produit(n, x));
  return 0;
}

Le programme est basée sur la simple observation que <math>\(nx=0\)</math> si <math>\(n=0\)</math> et que <math>\(n x= (n-1)x+x\)</math>.

À l'exécution, on obtient l'affichage suivant :

8 * 5 = 40

Il faudrait détailler sur cet exemple comment s'effectuent les appels.

L'exemple qui est le plus souvent utilisé pour décrire les fonctions récursives est celui de la fonction factorielle. On rappelle que par exemple factorielle de 6 est le nombre, noté 6!, et qui vaut :


Voici un programme qui calcule récursivement des factorielles :

/* factorielle.c */
#include <stdio.h>

/* Fonction qui calcule n! (factorielle n) */
int f(int n)
{
  if (n == 0)
    return 1;
  else
    return n * f(n - 1);
}

int main(void)
{
  int n=13;
   printf("%d! = %d\n", n, f(n));
  return 0;
}

Elle s'exécute en affichant :

13! = 1932053504

La fonction factorielle présente deux inconvénients :

a) Comme n! grandit très vite, pour petite valeur de n, le type int n'a pas une taille mémoire suffisante pour stocker un nombre aussi grand ;
b) L'écriture itérative de la fonction factorielle est très simple et dans ce cas, on préfère l'utiliser plutôt que la version récursive.



Un usage irréfléchi de fonctions récursives peut poser des problèmes d'exécution sur certaines implémentations. En effet, si la récursivité est profonde i.e. les appels récursifs sont nombreux, les fonctions sont appelées et ne retournent pas immédiatement leur résultat donc les appels s'accumulent. Ces appels sont souvent stockés dans une zone mémoire appelée "pile" et qui est de taille limitée. Si cette taille est dépassée, on obtient une erreur à l'exécution ("une explosion de la pile").

Par exemple, si on exécute la fonction ci-dessus avec une valeur de n très grande, on peut obtenir une erreur à l'exécution : ainsi, le code ci-dessous

/* recursifPile.c */
#include <stdio.h>

/* Retourne le produit n*x où n>=0 */
int produit(int n, int x)
{
  if (n > 0)
    return produit(n - 1, x) + x;
  else
    return 0;
}

int main(void)
{
  /* On suppose que la valeur 500000 tient dans un int */
  int n = 500000, x = 5;

  printf("%d * %d = %d\n", n, x, produit(n, x));
  return 0;
}

s'exécute de la manière suivante :

$ gcc -W -Wall -std=c99 -pedantic -o x recursifPile.c 
$ ./x
Erreur de segmentation
$

En fait, le code récursif utilisé peut-être dérécursifié de la manière suivante :

/* derecursifier.c */
#include <stdio.h>

/* Retourne le produit n*x où n>=0 */
int produit_bis(int n, int x)
{
  int i = 0;
  int temp = 0;

  for (i = 0; i < n; i++)
    temp = temp + x;

  return temp;
}

int main(void)
{
  /* on suppose que la valeur 500000 tient dans un int */
  int n = 500000, x = 5;

  printf("%d * %d = %d\n", n, x, produit_bis(n, x));
  return 0;
}

qui affiche le message suivant

500000 * 5 = 2500000

Il n'est pas toujours aussi simple de dérécursifier un code récursif. Toutefois, un compilateur moderne est capable de le faire sous certaines conditions de récursivité et si on l'utilise avec certaines options. Plus précisément, en général, il suffit que :

1°) le compilateur sache se ramener à une récursivité dite "terminale" où la dernière opération effectuée est l'appel récursif
2°) on passe une option d'optimisation au compilateur, du genre -O2 pour gcc.

Ainsi avec l'exemple ci-dessus, on obtient l'exécution suivante :

$ gcc -O2 recursifPile.c -o x
$ ./x
500000 * 5 = 2500000
$

A la différence du langage C++, le langage autorise la récursivité de la fonction main(). Bien que cela soit de peu d'intérêt pratique, voici un exemple d'appel récursif de la fonction main() :

#include <stdio.h>

int main(void)
{
  static int i = 0;

  if (i++ < 1)
    {
      printf("i=%d, %d\n", i, main());
      printf("Adieu !\n");
      return 0;
    }

  printf("A+ !\n");
  return 0;
}

qui affiche

A+ !
i=2, 0
Adieu !

Intéressant ! Surtout l'histoire de la pile (si un programme avait planté à cause de ça chez moi, j'aurais cherché pendant des semaines xD) et la dérécursification par compilateur
Dans quels cas la récursivité est plus intéressante que la méthode itérative ? Est-ce que ces nombreux appels ralentissent l'exécution ou est ce au contraire plus rapide qu'une boucle for par exemple ?

Citation : CokieForever

Dans quels cas la récursivité est plus intéressante que la méthode itérative ?

Ça dépend, on écrit généralement les fonctions de la manière la plus simple, si la récursivité est mieux adaptée, on l'utilise.

Citation : CokieForever

Est-ce que ces nombreux appels ralentissent l'exécution ou est ce au contraire plus rapide qu'une boucle for par exemple ?

La différence ne se voit pas vraiment, mais si on a 10000000 appels récursifs ça se verra sans doute. La récursion terminale peut remédier à ce problème.
En tous cas le choix entre récursif et itératif est très difficile, on ne peut pas prétendre qu'il y a des différences de performances tellement grandes.

D'accord. En gros, il faut faire au plus simple
Merci !
Sinon, c'est quoi la récursion terminale ?

Note: Le C n'est pas adapté pour faire de la récursivité à tout bout de champ, on préfèrera les langages fonctionnels pour ça.
Du à la limite de la pile et la lenteur des appels de fonctions, on restreint généralement la récursivité à des algos de complexité inférieures à log2(n).

En effet, si j'ai une complexité O(n), ça veut dire que jevais recopier n fois les arguments de ma fonction récursive dans la pile. (l'exemple de la multiplication est très clair, 2 arguments int(4 octets), ça fait 8 octets, si on multiplie 1 000 000 par 1 000 000, on aura 1 000 000 * 8 octets dans la pile, 8 000 000 o == 8 Mo de perdus stupidement)
Note, il y a même un int de plus "invisible" à prendre en compte pour chaque appel de fonction normalement, ce qui amènerai à 12o la taille de chaque appel.

La récursivité est donc interressante pour des problèmes comme le parcours d'arbre ou de tri.

Dernier point, tout problème récursif possède une solution itérative.

Citation

b) L'écriture itérative de la fonction factorielle est très simple et dans ce cas, on préfère l'utiliser plutôt que la version récursive.

Sans prendre en compte les performances que procure la version itérative, l'écriture de la factorielle en récursif est juste plus simple !

en récursif la ligne qui mérite reflexion est return n * fac(n - 1); alors qu'en itératif le code est plus long, et donc automatiquement plus long à comprendre :

resultat = 1;

for (i = 1; i <= n; i++)
        resultat *= i;

Citation

Note: Le C n'est pas adapté pour faire de la récursivité à tout bout de champ, on préfèrera les langages fonctionnels pour ça.

Mais en quoi les langages fonctionnels sont plus adaptés ? Parce qu'il font de la tail recursion à tout bout de champ ? Chose qu'on peut faire en C. Ou alors leur compilateur sont plus performant pour traiter du code récursif ?

Citation : noob4ever

Sans prendre en compte les performances que procure la version itérative, l'écriture de la factorielle en récursif est juste plus simple !

Je dirais que les deux sont courts voire simples.


Mais conceptuellement, la récursivité est moins facile à assimiler. Quand tu écris return n*f(n-1); , le f(n-1) est potentiel. Le code itératif traduit une formulation plus vulgaire : "faire le produit de tous les entiers entre 1 et n" et ce n'est pas du tout ce que dit la version récursive même si c'est ce qu'elle fait.

Ce n'est pas pour rien que l'on dit que l'itération est humaine et la récursion divine. La récursivité a souvent quelque chose de magique (le potentiel devient réel). Donc quand on parle de simplicité, il ne faut pas se limiter à compter les lignes de code. D'ailleurs, bien souvent moins il y a de lignes de code, plus c'est difficile à trouver.

La factorielle en C avec ou sans récursivité est un débat creux à mon avis (rien déjà parce qu'en C90 qui est le C le plus utilisé, tu ne vas pas au-delà de 14!). Il y a bien d'autres programmes où la récursivité est vraiment intéressante (rien que dans le problème des huit reines dont on parlait il y a peu).

Pour ma part, je trouve que la factorielle itérative est beaucoup plus simple à comprendre, car à l'itération on si je puis dire, toute les étapes du calcul, la plus simple factorielle itérative, je trouve est celle ci :

/*Factorielle de n : produit des entiers compris dans l'intervalle ]0;n].
Perso je la définie comme ça.*/

/*je trouve qu'on retrouve plus la définition en itératif qu'en récursif.*/

int facto(int n){ 
     int a=1;
     for(n=10;n>0;n--)
         a*=n;
     return a;
}

salut,

Mais la définition de la factorielle est récursive (n! = n*(n-1)! ou 1 si n = 1). de ce point de vue il est plus rationnel d'utiliser la récursivité.

d'autre algo sont aussi intuitivement récursif (DFS par exemple => pour l'exploration d'arbre) et de manière général les algorithme qui utilise une pile (tant qu'a faire autant utiliser la pile d'appel non ?)

Pour le fonctionel, a mon avis ce genre de la,gage est axé récursif (notamment l'exploration de liste avec cdr et car).

Enfin pour répondre à CokieForever: je crois que la récursion est dite terminal lorsque la fonction appelante fourni directement un résultat qui peut être utilisé dans le prochain appel qu'elle fait d'elle même.
en gros (que ceux qui s'y connaisse plus que moi me corrige au cas ou) pour la factorielle tu fait monter ta pile d'appel jusqu'à ce que n = 1 puis tu la redescend en multipliant, dans une fonction recusive terminal tu ne fait rien en redescendant.

Hedi

Citation : hedi07

Mais la définition de la factorielle est récursive (n! = n*(n-1)! ou 1 si n = 1). de ce point de vue il est plus rationnel d'utiliser la récursivité.

Moi on m'a expliqué la récursivitéfactorielle comme cela :

<math>\(n! = \prod_{k=0}^{n-1} n-k\)</math>

Tout ça pour dire que tout est récursif ET itératif.

Citation : candide

1°) le compilateur sache se ramener à une récursivité dite "terminale" où la dernière opération effectuée est l'appel récursif

Hum, il est en effet fort probable qu'un compilateur puisse faire ceci dans de petite proportion, mais il faudrait quand même encourager ceux qui écrivent le code à chercher à faire du tail-rec de leurs fonctions récursives quand c'est possible (ça ne l'est pas toujours). Le compilateur optimise ce qu'il peut, le programmeur peut favoriser certaines optimisations ou mettre en avant des opportunités d'optimisation (écrire du tail-rec, éviter les variables inutiles, etc.).

Citation : candide

A la différence du langage C++, le langage C autorise la récursivité de la fonction main().

Oui, et j'en profite pour linker cette intéressante discussion à ce sujet.

Citation : nepser

Note: Le C n'est pas adapté pour faire de la récursivité à tout bout de champ, on préfèrera les langages fonctionnels pour ça.
Du à la limite de la pile et la lenteur des appels de fonctions, on restreint généralement la récursivité à des algos de complexité inférieures à log2(n).

Les langages fonctionnels ne sont pas plus "adaptés", c'est juste qu'avec un langage fonctionnel pur, on ne peut pas faire autrement pour écrire une boucle. Le C, comme l'OCaml, gère très bien la récursivité et à ma connaissance tous les compilateurs dignes de ce nom peuvent optimiser sur les fonctions tail-rec. Comme la récursivité est quand même plus présente dans les langages fonctionnels, ça ne m'étonnerait pas que les étapes d'optimisations de leur compilateur s'intéressent plus aux fonctions récursives, mais là je n'en sais pas plus.

Sinon, pour les fonctions récursives terminales, ce sont simplement des fonctions dont l'appel récursif est la dernière action de ces dernières (ie, plus rien n'est à faire après ; l'implémentation récursive naïve de la fonction factorielle n'est pas tail-rec puisqu'il reste les multiplications à faire).

Citation : hedi07

dans une fonction recusive terminal tu ne fait rien en redescendant.

Non, avec une fonction récursive terminale, si le compilateur optimise, on ne "redescend" pas puis qu'on a même pas besoin d'une pile d'appel.

Citation : apprentimagicien

Moi on m'a expliquer la récursivité comme cela :

<math>\(n! = \prod_{k=0}^{n-1} n-k\)</math>

Aucun rapport avec la récursivité.

Citation : apprentimagicien

Tout ça pour dire que tout est récursif ET itératif.

Ben oui, tout est dans tout et réciproquement


Rappel de quelques messages sur ce forum où cette question a déjà été abondemment traitée :
*) Programmation récursive
*) Du bon usage de la récursivité

Citation : candide

Citation : apprentimagicien

Moi on m'a expliquer la récursivité comme cela :

<math>\(n! = \prod_{k=0}^{n-1} n-k\)</math>

Aucun rapport avec la récursivité.

mea culpa je voulais dire la fonction factorielle. Comme tu l'auras sans doute compris.

apprentimagicien>> ça marche aussi, évidemment, il y a d'ailleurs un théorème ou un preuve qui dit que tout algo récursif peut être passer en itératif et vice-versa.

Citation : hedi07

apprentimagicien>> ça marche aussi, évidemment, il y a d'ailleurs un théorème ou un preuve qui dit que tout algo récursif peut être passer en itératif et vice-versa.

Tu peux bien sûr toujours simuler la pile d'appel toi-même et écrire un code "itératif".

Citation : apprentimagicien

Citation : candide

Citation : apprentimagicien

Moi on m'a expliquer la récursivité comme cela :

<math>\(n! = \prod_{k=0}^{n-1} n-k\)</math>

Aucun rapport avec la récursivité.

mea culpa je voulais dire la fonction factorielle.

OK. Mais je répète que la fonction factorielle est un mauvais exemple d'un point de vue pédagogique. La plupart des ouvrages considèrent que la récursivité s'arrête avec le codage d'une factorielle. Supposons que tu veuilles coder efficacement le calcul de 1000000! : jamais tu ne vas utiliser la méthode récursive (ou itérative d'ailleurs). La logique récursive de la factorielle est mauvaise dans la mesure où elle peut faire croire que la définition mathématique "savante" (par récurrence) donne l'implémentation ce qui est faux, l'exemple classique étant la suite de Fibonacci qui est souvent implémentée par des programmeurs professionnels de manière récursive.

Le problème de l'apprentissage de la récursivité est qu'il s'agit d'une notion délicate et que les exemples doivent être choisis avec réflexion pour à la fois isoler la notion de récursivité en tant que telle mais sans la noyer dans un environnement compliqué tout en faisant comprendre qu'elle peut être utile à réaliser efficacement des programmes de tous les jours.

Citation : hedi07

apprentimagicien>> il y a d'ailleurs un théorème ou un preuve qui dit que tout algo récursif peut être passer en itératif et vice-versa.

J'entends souvent parler de ce résultat, as-tu une référence précise avec un énoncé formel et une preuve "mathématique" ? Bon sinon, dérécursifier certains algorithmes naturellement récursifs peut être particulièrement délicat, je pense au tri-fusion, au quicksort, aux tours de Hanoï ou à Karatsuba par exemple.

Citation

J'entends souvent parler de ce résultat, as-tu une référence précise avec un énoncé formel et une preuve "mathématique" ? Bon sinon, dérécursifier certains algorithmes naturellement récursifs peut être particulièrement délicat, je pense au tri-fusion, au quicksort, aux tours de Hanoï ou à Karatsuba par exemple.

Ca se justifie relativement simplement... Ton algoritme récursif devient itératif a partir du moment ou tu considère la pile d'appel des fonctions comme une bête pile.

Ainsi là ou l'algorithme récursif va appeler la fonction, l'algorithme itératif va empiler les arguments et sauter au début (il empilera aussi les "return" sur une pile de résultats)

Après pour la preuve formelle, je pense qu'il faut regarder de ce coté ci :
http://fr.wikipedia.org/wiki/Th%C3%A8se_de_Church

Citation : hedi07

apprentimagicien>> ça marche aussi, évidemment, il y a d'ailleurs un théorème ou un preuve qui dit que tout algo récursif peut être passer en itératif et vice-versa.

Encore une chance oui ! (enfin pour le moment je n'ai pas besoin de la récursivité)

Citation : candide

l'exemple classique étant la suite de Fibonacci qui est souvent implémentée par des programmeurs professionnels de manière récursive.

Oui c'est ce qu'on m'a dit une fois, et je me suis empressé de coder ça : (après je sais pas si c'est la meilleur technique mais bon)

#include <stdio.h>

double fibo(int c){
    double a = 0, b = 1;
    double resultat = 0;
    int i;
    for(i = 0; i < c; i++){
        resultat = a + b;
        b = a;
        a = resultat;
    }
    return resultat;
}

int main(void){

    int i = 0;
    for(; i < 100; i++)
        printf("%d: %.0f\n", i, fibo(i));

	return 0;
}

Citation : Floooder

Ca se justifie relativement simplement... Ton algoritme récursif devient itératif a partir du moment ou tu considère la pile d'appel des fonctions comme une bête pile.

Tout cela est très vague, je vois bien ce que tu veux dire (en quelque sorte, on regarde l'espace mémoire global créé par chaque appel empilé comme un itérable et on itère dessus) mais on est très très loin de ce que j'appelle une preuve.

Très concrètement, si je te donne une implémentation récursive IR (par exemple du quicksort ou des Tours de Hanoï), sais-tu me transformer de manière systématique (je veux dire "générique") mon implémentation IR en une implémentation II itérative équivalente ?

Citation : Floooder

Après pour la preuve formelle, je pense qu'il faut regarder de ce coté ci :
http://fr.wikipedia.org/wiki/Th%C3%A8se_de_Church

Non, je ne vois rien de précis alors que je parle moi d'un résultat très précis. En plus mon regard n'est pas celui de l'info théorique, ce que je "veux" c'est un algorithme capable de dérécursifier (un algorithme donc pas un truc qui marcherait au cas par cas).

Candide>> je n'ai pas de preuve on avait vu ça en cours et le prof nous avait dit quelque chose comme: en récursif t'as le cas simple et les autres, en itératif t'as la condition et le traitement. je sais pas si je m'exprime bien alors voila l'exemple avec la factoriel (dsl):

tant n <> 1
faire resultat *= n
n=n-1
fin tant

si n = 1
retourné 1
sinon
retourné n*fact(n-1)

on voit une certaine symétrie intuitivement.

mais je n'ai pas de preuve.

-
Edité par DifelSouha 27 décembre 2015 à 15:40:42

stp une  execution a la main pour mieux comprendre

-
Edité par soukin24 29 décembre 2015 à 16:24:03