Récursion terminal

[medine14]

Bonjour à tous
Je ne poste pas souvent mais aujourd'hui j'ai besoin de votre aide !
J'ai une fonction en java :

static int bo(int n){
      if(n<=0) return 3;
      if(n==1) return 1;
      if(n==2) return 2;
      return 3*bo(n-3) + bo(n-2);
}

j'ai ici la fonction sous sa forme récursive terminale :

static int boTerm(int n, int b1, int b2, int b3){
      if(n <= 1)
         return b1;
      return boTerm(n-1,3*b3+b2,b1,b2);
}

Mais je ne comprends toujours pas comment arriver à ce résultat..
Je sais que j'ai peu de chance de tomber sur quelqu'un qui pourra m'aider mais bon je tente
Merci à vous !

 

[Peaky Blinders]

Déjà, que fait ta fonction ?

 

[medine14]

Déjà, que fait ta fonction ?

Je répondrais qu'elle calcule quelque chose, mais quoi, je ne sais pas.

 

[Peaky Blinders]

Bon bah reviens quand tu saura ce qu'elle fait

 

[medine14]

Bon bah reviens quand tu saura ce qu'elle fait

Tu peux pas me filer un petit coup de main ?

 

[Peaky Blinders]

Tu peux pas me filer un petit coup de main ?

Tu veux que je t'aide comment, je sais pas ce qu'elle fait ta fonction.

 

[medine14]

Tu veux que je t'aide comment, je sais pas ce qu'elle fait ta fonction.

Il me semble qu'on peut passer d'une fonction récursive non terminale à une fonction récursive terminale sans forcément comprendre ce que calcule la fonction.

 

[Paul GTP]

Il me semble qu'on peut passer d'une fonction récursive non terminale à une fonction récursive terminale sans forcément comprendre ce que calcule la fonction.

Je pense que tu as mal compris ton cours
Une fonction récusrive terminale c'est une fonction qui appelle une autre fonction sans effectuer de calcul derrière

Ta fonction bo retourne ceci:

return 3*bo(n-3) + bo(n-2);

Elle n'est donc pas terminale car en plus de bo("quelque chose"), tu fais des opérations. Elle aurait pu être terminale si ça le résultat avait été ça par exemple

return bo(n-1);

Car il n'y a qu'un seul appel de fonction dans ton return et qu'il n'y a aucun calcul derrière... ce qui est le cas dans ton boTerm (qui, comme son nom l'indique, est une fonction récursive terminale)

return boTerm(n-1,3*b3+b2,b1,b2);

Il n'y a pas de calculs, tu return juste la fonction.

Il n'y a pas, à ma connaissance, moyen de passer d'une fonction récursive non terminale à une fonction récursive terminale sans trop comprendre pourquoi.
Il suffit de regarde étape par étape ce que fait l'algorithme et faire en sorte qu'il le soit.

En l'occurrence, il faut justement comprendre ce que fais ta fonction pour comprendre comme la rendre terminale...
Certains peuvent sans doute y arriver sans mais je trouve ça plus facile de d'abord comprendre et après "convertir"

Bonne chance

 

[medine14]

Je pense que tu as mal compris ton cours
Une fonction récusrive terminale c'est une fonction qui appelle une autre fonction sans effectuer de calcul derrière

Ta fonction bo retourne ceci:

return 3*bo(n-3) + bo(n-2);

Elle n'est donc pas terminale car en plus de bo("quelque chose"), tu fais des opérations. Elle aurait pu être terminale si ça le résultat avait été ça par exemple

return bo(n-1);

Car il n'y a qu'un seul appel de fonction dans ton return et qu'il n'y a aucun calcul derrière... ce qui est le cas dans ton boTerm (qui, comme son nom l'indique, est une fonction récursive terminale)

return boTerm(n-1,3*b3+b2,b1,b2);

Il n'y a pas de calculs, tu return juste la fonction.

Il n'y a pas, à ma connaissance, moyen de passer d'une fonction récursive non terminale à une fonction récursive terminale sans trop comprendre pourquoi.
Il suffit de regarde étape par étape ce que fait l'algorithme et faire en sorte qu'il le soit.

En l'occurrence, il faut justement comprendre ce que fais ta fonction pour comprendre comme la rendre terminale...
Certains peuvent sans doute y arriver sans mais je trouve ça plus facile de d'abord comprendre et après "convertir"

Bonne chance

Un grand merci à toi pour le temps que tu as pris pour me répondre,
Je comprends un peu mieux.
Exam dans une semaine je te tiens au courant ahahah