Process returned -1073741571 (0xC00000FD)   execution time : 3.967 s
Press any key to continue.

-
Edité par pseudo-simple 15 juin 2018 à 22:52:50

Salut,

La récursivité est une technique géniale, mais extrêmement dangereuse, surtout si l'on n'y fait pas attention.

Le principal danger, de cette technique, c'est que l'on va ajouter des informations sur la pile d'appels à chaque fois que la fonction récursive est appelée.

Or, tu le sais sûrement, la pile d'appel, c'est un espace mémoire particulièrement limité!!! Le risque est énorme de saturer la pile d'appels au point que le système d'exploitation n'ait finalement pas d'autres choix que de... mettre le hola...

Et, bien sur, plus tu fais d'appels récursifs dans ta fonction, plus ce moment arrivera vite

Imagine un peu! Sans connaitre la logique que tu as mise en place, voici ce qui se passe sans doute lorsque tu appelle ta fonction sous la forme de i =fonction(100) (bon, c'est le cas le pire, ton code peut faire "un peu mieux " ):

fonction(100): appels récursifs pour 
  |-->fonction(99) : appels récursifs pour
  |  |-->fonction(98) : appels récursifs pour
  |  |  |-->fonction(97) : appels récursifs pour
  |  |  |  |-->fonction(96) /*...*/
  |  |  |  |-->fonction(95) /*...*/
  |  |  |  |-->fonction(94)
  |  |  |-->fonction(96) : appels récursifs pour
  |  |  |  |-->fonction(95) /*...*/
  |  |  |  |-->fonction(94) /*...*/
  |  |  |  |-->fonction(93) /*...*/
  |  |  |-->fonction(95) : appels récursifs pour
  |  |  |  |-->fonction(94) /*...*/
  |  |  |  |-->fonction(93) /*...*/
  |  |  |  |-->fonction(92) /*...*/
  |  |-->fonction(97)  : appels récursifs pour 
  |  |  |-->fonction(96) /*...*/
  |  |  |-->fonction(95) /*...*/
  |  |  |-->fonction(94) /*...*/
  |  |-->fonction(96) : appels récursifs pour
  |  |  |-->fonction(95) /*...*/
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |-->fonction(95) : appels récursifs pour
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |  |-->fonction(92) /*...*/
  |-->fonction(98) : appels récursifs pour
  |  |-->fonction(97) : appels récursifs pour
  |  |  |-->fonction(96) /*...*/
  |  |  |-->fonction(95) /*...*/
  |  |  |-->fonction(94) /*...*/
  |  |-->fonction(96) : appels récursifs pour
  |  |  |-->fonction(95) /*...*/
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |-->fonction(95) : appels récursifs pour
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |  |-->fonction(92) /*...*/
  |-->fonction(97) : appels récursifs pour
  |  |-->fonction(96) : appels récursifs pour
  |  |  |-->fonction(95) /*...*/
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |-->fonction(95) : appels récursifs pour
  |  |  |-->fonction(94) /*...*/
  |  |  |-->fonction(93) /*...*/
  |  |  |-->fonction(92) /*...*/
  |  |-->fonction(94) : appels récursifs pour
  |  |  |-->fonction(93) /*...*/
  |  |  |-->fonction(92) /*...*/
  |  |  |-->fonction(91) /*...*/

Et ca, c'est le résultat sur 4 niveaux de récursivité maximum à peine...

Essaye d'imaginer ce que cela donne avec 97, 98 ou 99 niveaux de récursivité!  Tu t'étonnes que ta pile d'appels finissent par saturer?

Ensuite, amuses toi à compter le nombre de fois où fonction(95) est appelée, en sachant que je n'ai pas affiché l'appel à chaque fois que fonction(96) avait été appelée et qu'il manque donc au moins trois appels à fonction(95).

Si j'ai bien compté, fonction(95) sera appelée un total de 13 fois!!! ... pour rien, parce que le résultat des différents appels sera toujours le même!

Mais, si fonction(95) est appelé 13 fois, alors que fonction 96 n'est appelée que 7 fois (si j'ai bien compté, toujours), je te laisse imaginer le nombre de fois que fonction(15) ou fonction(1) seront appelées.  Cela va littéralement crever le plafond!

Et tu t'étonne que ton programme commence à ralentir???

Si tu t'organisais ne serait-ce que pour "maintenir" quelque part le résultat obtenu lors de (le premier) l'appel pour une valeur donnée afin de pouvoir le récupérer pour "une utilisation ultérieure", tu imagines un peu le nombre d'appel "inutiles" que tu pourrais économiser?

D'autant plus que, si tu t'y prend bien, cela te permettrait sans doute de rendre ta récursivité terminale, et, du coup, tu saturerais sans doute beaucoup moins vite ta pile d'appels

Merci Koala01 pour ton message détaillé.

J'ai mis en oeuvre tes idées, et j'ai bien avancé : maintenant avec le principe de stocker les valeurs dans un tableau (programmation dynamique), j'obtiens mon bon résultat pour n=100 000.

Par contre , pour n=3 milliards, j'ai l'exception suivante.

terminate called after throwing an instance of 'std::bad_array_new_length'
  what():  std::bad_array_new_length

Process returned 3 (0x3)   execution time : 1.103 s
Press any key to continue.

D'après ce que j'ai trouvé, ce nombre excederait une certaine quantité pré-établie. (laquelle d'ailleurs ?).

J'avais tout stocké dans un tableau déclaré avec :

int *t=new int[n+1];

Je pense que c'est peut-être parce qu'à priori, 3 milliards c'est un peu grand pour un tableau, mais je suis certain qu'il y a une solution pour palier à cela.

As-tu une idée ?

Merci

-
Edité par pseudo-simple 16 juin 2018 à 1:57:04

Si, bien sur que j'ai une solution : passer sous linux 64bits, avec 64Gb de RAM, autant de swap et compiler en 64 bits

Plus sérieusement, rien ne t'empêche de travailler "par lot":

A partir du moment ou f(x) utilise les résultats de f(x-1), f(x-2) et f(x-3), cela signifie que, si tu as les résultats de f(x), f(x+1) et f(x+2), tu dois pouvoir calculer le résultat de... f(x+3)... Non?

Dés lors, si tu prend un tableau de N éléments (ou N>3) et que tu "préremplis" les trois premiers élément (en considérant que le premier correspond au résultat de f(x), que le deuxième correspond au résultat de f(x+1) et que le troisième correspond au résultat de f(x+2), tu pourras calculer sans problème le la valeur du troisième élément, qui correspondra au résultat de f(x+3) et, à partir de là, la valeur de tous les autres éléments de ton tableau.

Si bien que, pour un x donné, la valeur que tu trouvera à la position P de ton tableau corespondra au résultat de l'appel de ta fonction en lui ayant transmis la valeur x+P ...Ou alors je me trompes très largement.

Une fois que ton tableau est remplis, tu en copie les deux dernières valeurs dans un autre, tu considère que x = x+(nombre de position)-2, et tu recommence ;).

Avec cette méthode, le seul problème contre lequel tu ne pourras rien faire (*) sera le risque d'overflow (comprend: d'essayer de représenter une valeur numérique qui a besoin de plus de bits pour être représentée que le nombre de bits dont dispose le type que tu utilises pour représenter cette valeur  )

De plus, en effectuant ce "retournement de logique", il y a de fortes chances pour que tu n'aies même plus besoin de recourir à la récursivité, et qu'une simple boucle puisse parfaitement faire l'affaire.

D'ailleurs, c'est bien simple: une très grande majorité des fonctions récursives terminales sont susceptibles d'être remplacées par une implémentation "purement séquentielle" (sous forme de "simple(s) boucle(s)" ). 

Pour être clair : il n'y a que très peu d'algorithmes pour lesquels tu n'aie pas d'autre choix que d'avoir recours à la récursivité. Pour une grosse majorité des algorithmes, on se rend compte qu'il n'est sans doute pas plus difficile (mais surement bien plus efficace) de fournir une implémentation à base de boucle qu'une implémentation récursive

(*) Et encore: en utilisant une bibliothèque d'arithmétique à précision arbitraire (comme GMP) limite finale sera celle de ta machine (de la quantité de mémoire que la machine peut allouer aux opérations) ou peu s'en faut

-
Edité par koala01 16 juin 2018 à 2:51:36

Salut Koala01, merci beaucoup, j'ai appliqué ce que tu as dit par lot de 3, et ça fonctionne aussi sur 3 milliards , au prix de plus d'attente tout de même que 100 000 , ce qui est normal.

C'est vraiment cool d'avoir de la guidance sur un forum. MERCI

ça m'a bien fait rire quand tu as dit de prendre un Linux 64 Go de Ram, avec 64 bits .... et autant de SWAP ...64... Une fois, j'ai fait cela : en plus, je suis passé en long long int . J'ai tout utilisé au max. Je pense que j'ai peut-être été contraint de faire, étant donné que je faisais du calcul sur des nombres très grands : beaucoup plus que 10 milliards.

Je vais ouvrir un nouveau sur le code ASCII et Assembleur. J'espère que tu peux passer dessus pour m'aider

Merci