Discussion :

[onlytime]

bonjour tout le monde
j'ai un petit probléme en récursivité voila a peu prés l'ennocé

soit un tableau de n entier compris entre 0 et 9 alors faut implementer un algorithme recursif qui permet de donner le nombre que constitu les elements de ce tableau

exemple
le tableau contient :1 2 6 7 5

en resultat j'aurais le chiffre 12675

j'ai essayer un code

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
type tab:array[1..max];
 
function tableau(t:tab):integer;
i:=max;
function tab(t:tab):integer;
  begin
 
 if i:=o then tab:=t[0] {cas trivial}
  else
     tab:=tab[i-1];{appel récursif}
   end;

mon principe était de decomposer le mon tableau et faire l'appel recursif au reste du tableau,malgré que cette solution me satisfait pas alors pourriez vous me dire ce que j'ai louppé
merci

[pseudocode]

Quel peut bien etre l'interet de faire cet algo par recursion ??

Enfin bon, si c'est pour un exercice, voila une solution:

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
public class TestBase10 {
 
	int[] array = new int[] {1,2,6,7,5};
 
	private int compute(int result, int index) {
		// end recursion: index out of range
		if (index>=array.length) return result;
 
		// step: add a digit to the right 
		int newresult = 10*result + array[index];
 
		// recurse: increment index
		return compute( newresult , index+1 );
	}
 
	public static void main(String[] args) {
		// initial step: result=0, index=0
		int result = new TestBase10().compute(0,0);
 
		// print result
		System.out.println("resultat:"+result);
	}
}

[Jedai]

Quel peut bien etre l'interet de faire cet algo par recursion ??

En C ou en Java aucun. Avec un vrai tableau, quel que soit le langage l'intérêt reste très limité... Avec une liste de nombre dans un langage fonctionnel, c'est assez naturel :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
list2num li = accum 0 li
  where 
    accum s (x:xs) = accum (10 * s + x) xs
    accum s [] = s

Bien qu'on utilise plus probablement un combinateur de plus haut niveau, comme un fold :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

list2num = foldl' (\s x -> 10 * s + x) 0

--
Jedaï

[onlytime]

oui,voila moi je fais qu'essayer de resoudre l'exercice,bref le plus important n'est pas le langage d'implémentation mais l'algorithme ,l'idée de trouver une solution recursive

[pseudocode]

oui,voila moi je fais qu'essayer de resoudre l'exercice,bref le plus important n'est pas le langage d'implémentation mais l'algorithme ,l'idée de trouver une solution recursive

Si tu as un nombre N (a plusieurs chiffres) et que tu veux mettre un seul nouveau chiffre C a droite, le nombre R obtenu peut se calculer comme suit:

R = 10*N + C

Ca consiste a faire un décalage de N a gauche (en multipliant par 10), puis a ajouter C (qui est entre 0 et 9, donc qui ne modifie pas les chiffres de N)

Apres, pour la recursion, c'est toujours la meme chose:

1. Decrire les données du problemes
2. Ecrire les conditions initiales
3. Trouver la condition de sortie de la boucle de recursion
4. Calculer une étape de la boucle de recursion
5. Trouver comment passer a l'étape suivante de la boucle de récursion

Dans notre cas:

1: Liste {a,b,c,d,...}. formule R = 10*N + C

2: Liste {a,b,c,d,...}, Index=0, R=0, N=0, C=0

3: On arrete quand l'Index a ateint la fin de la liste

4: prendre C=Liste[Index] et calculer R = 10*N + C

5: Liste {a,b,c,d,...} (inchangé), Index=Index+1, R=R (inchangé), N=R, C=? (peu importe)

voila.

[Jedai]

Ce que tu décris ressemble plus à une méthode pour trouver un algo itératif... Il n'y a pas de "boucle" de récursion ni de "condition de sortie", ou d'"étape".
Généralement pour la récursion l'idée est plutôt de distinguer les différentes entrées possibles, trouver les sorties correspondantes, puis généralement vérifier qu'on a bien un cas de base (un cas où la fonction ne se rappelle pas elle-même) et qu'on arrive toujours au cas de base au bout d'un nombre fini de récursion.

1. Ici, avec une liste de nombre, on a deux cas possibles : la liste est vide
   

   Code :

   Sélectionner tout - Visualiser dans une fenêtre à part

   list2num [] = 0

   on remarque que c'est un cas de base.
   
   
   
2. ou la liste n'est pas vide :
   

   Code :

   Sélectionner tout - Visualiser dans une fenêtre à part

   list2num (x:xs) = x + 10 * list2num xs

   Dans ce cas on additionne le dernier chiffre de la liste à 10 fois le nombre représenté par le reste des chiffres (qu'on obtient bien par list2num xs, on remarque ici une caractéristique de la récursion : on suppose "a priori" que la fonction qu'on est en train de fabriquer marche déjà).
   
   Point de syntaxe : la reconnaissance de motif me permet ici de découper une liste non vide en un tête x (un chiffre) et une queue xs (une liste).
   On remarque que l'appel récursif se fait sur une liste moins longue que l'appel initial, on arrivera donc bien finalement au cas de base, notre récursion est correcte.

Ici j'ai un peu triché parce que j'ai inversé l'ordre des chiffres, autrement dit la liste [1, 2, 4, 9] donnera 9421 et pas 1249, néanmoins ceci n'est qu'un point mineur, facile à corriger par exemple en retournant la liste, ou en employant un accumulateur comme dans mon post précédent.

--
Jedaï

[Jedai]

De même pour un vrai tableau :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
tab2num t = numUntil sup
    where
      (inf, sup) = bounds t
      numUntil index 
          | index >= inf  = 10 * numUntil (index - 1) + (t ! index)
          | otherwise     = 0

sauf que là j'ai besoin d'une fonction auxiliaire parce que la récursion va avoir besoin de savoir où elle en est dans le tableau, je crée une fonction numUntil qui me donne le nombre représenté par le tableau jusqu'à l'index donné en paramètre.

--
Jedaï

[henderson]

Salut !

Je me permets de participer modestement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int Tab[5] = {1,2,3,4,5};

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
int Calcul(int R, // résultat en cours
           int *T,  // valeur suivante 
           int Count) // limite
{
if(Count > 0) R = Calcul((R * 10) + *T, // résultat en cours
                          T + 1, // valeur suivante
                          Count - 1); // limite
return R;
}

Donc à l'usage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int r = Calcul(0, Tab, 5);

A plus !