Récursivité en arm

Discutez d'informatique ici !
Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 18:42

Récursivité en arm

par Rockleader » 29 Oct 2014, 15:20

Hello,


j'ai un problème assez simple d'un point de vue algorithmique, mais que je n'arrive pas à coder correctement.


Il s'agit de faire récursivement la somme des éléments d'un tableau en arm

En supposant que le tableau se termine par une constante connu (disons -1) , c'est assez simple à réaliser en itératif. Par contre pour passer à la récursivité j'ai du mal; à chaque fois que l'on va rappeler le sous programme on va de nouveau empiler, et j'ai du mal à suivre le processus. Je pensais m'inspirer de fonction plus connu comme la factorielle mais j'ai pas trouvé de code arm le faisant x)
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !



Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 16:40

par Zorro_X » 29 Oct 2014, 20:10

je ne sais pas coder en arm, mais la fonction récursive serait quelque chose du genre :
Code: Tout sélectionner
somme(tableau,taille,element_courant)
{
   si(element_courant < taille )  // condition d'arrêt de la récursivité
   {
      // tu renvoies l'élément courant + l'adition des éléments restants :
      renvoyer tableau[element_courant] + somme(tableau, taille, element_courrant+1);
   }
   sinon
   {
       renvoyer 0;
   }
}

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 18:42

par Rockleader » 29 Oct 2014, 20:44

Zorro_X a écrit:je ne sais pas coder en arm, mais la fonction récursive serait quelque chose du genre :
Code: Tout sélectionner
somme(tableau,taille,element_courant)
{
   si(element_courant < taille )  // condition d'arrêt de la récursivité
   {
      // tu renvoies l'élément courant + l'adition des éléments restants :
      renvoyer tableau[element_courant] + somme(tableau, taille, element_courrant+1);
   }
   sinon
   {
       renvoyer 0;
   }
}



J'avais déjà l'algo ;) Mais merci quand même^^
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
fatal_error
Membre Légendaire
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

par fatal_error » 29 Oct 2014, 22:58

je connais pas l'arm mais si tu as des fonctions c'est évident.
Si tu as pas de fonctions, tu peux toujours faire des goto...qui simulent le corps d'une fonction, et de fait, tu gères toi même ta pile d'appel+context.

Le passage du récursif à l'itératif se fait assez facilement,
Code: Tout sélectionner
int count(n){
 if (n==0){return 0}
 return 1+count(n-1)
}

donne quelque chose du style
Code: Tout sélectionner
globalCount = 0
globalStack //initialize stack properly
label: count
 n = globalStack.pop //pop is removing last added element
 if n==0
   goto finished
 globalCount +=1
 globalStack.push n-1 //store parameters to explore
 goto count


grossierement tu peux très bien imaginer globalStack un tableau de la taille de ton ...tableau
et une variable z qui compte la taille utilisée de ton tableau.
.push equivaut à ajouter un element (ici element c'est un int, mais tu pourrais imaginer que c'est un contexte (idem une liste de paramètres) a z+1, puis faire z++
.pop equivaut à retourner lelement à z, et faire z--
(dans les grandes lignes juste faire gaffe aux index)

c'est pas très générique, mais ca devrait faire son taff pour ton problème
(c'est pas générique, parce que on a pas besoin de sauvegarder le contexte de la fonction (idem on attend pas le retour de la fonction qu'on appèle), ya un nom quand tu fais l'appel récursif dans le return, mais j'ai oublié...)
la vie est une fête :)

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 18:42

par Rockleader » 29 Oct 2014, 23:21

Ya tellement d'arm différent je pense qu'on parle pas du même ;)

Pour ma part, je n'ai pas la possibilité d'utiliser des fonction, autre que les opérateurs basiques style ADD pour faire une addition, MOV pour placer une valeur dans un registre; les instruction pour empiler et dépiler et chargé des valeurs de tableau.




Si j'avais du le faire en itératif (je fais du code à la va vite surement pas tout à fait juste mais c'est l'idée) Je mets des comm à chaque ligne


Code: Tout sélectionner
mov r0,#0 @r0 sera la somme
mov r1,#0 @r1 compteur
tq: cmp r1,#N @je suppose N taille du tableau défini
     beq FINtq @ si c'est égal tableau fini
      @ sinon
     ldrb r3,tab[r1]   @ r3 = tab[cpt]
     add r0,r0,r3 @ on incrémente la somme
     add r1,r1,#1 @on incrémente le compteur
     btq  @ on repart sur la boucle
FINtq: On sort du sous programme avec la somme dans r0


Sa c'est la version itérative basique; mais en récursif je vois pas trop comment on faire faire pour le coup...pas niveau algo mais niveau codage, parce que à chaque fois qu'on va rappeler notre fonction, notre nouvelle somme va s'empiler pour le passage suivant...mais à la fin il faudra bien dépiler et au final je crois qu'on va retomber sur somme = 0.
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 16:40

par Zorro_X » 29 Oct 2014, 23:33

Bah, ce qu'ils veulent te faire faire dans l'exercice c'est utiliser les "call" et les "ret" (return) ainsi que dépiler les paramètres de la pile (suite à un call) pour récupérer un état...
Compile une fonction bête avec un ou deux paramètres qui ne fait pas grand chose et regarde le code assembleur, tu verras comment ca fonctionne.
Après, si t'as pas les call/ret je ne vois pas comment tu peux faire du "récursif" en assembleur (??)

Edit : réflexion faite, si, tu peux simuler un call et un ret en utilisant le registre de pile et le registre d'instruction, le tout en ne faisant que du "mov", en utilisant les bonnes adresses... ;) Là tu risques de t'amuser un petit peu !

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 18:42

par Rockleader » 29 Oct 2014, 23:37

Edit : réflexion faite, si, tu peux simuler un call et un ret en utilisant le registre de pile et le registre d'instruction, le tout en ne faisant que du "mov", en utilisant les bonnes adresses... ;) Là tu risques de t'amuser un petit peu


C'est l'idée, je me suis déjà servi du registre de pile r13 pour faire passer tout un tas de paramètres, mais ça se limitait à une fonction ;)
Là la fonction se rappelle elle même, et je commence à être perdu avec mon pointeur de pile ^^
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 16:40

par Zorro_X » 29 Oct 2014, 23:44

Ca remonte un peu loin tout ça pour moi et l'assembleur n'est pas ma façon de coder préférée, mais si mes souvenirs sont bons :
call :
1) ajouter l'adresse suivante du pointeur d'instruction dans la pile ;
2) ajouter les paramètres dans la pile, un à un ;
3) changer l'adresse du pointeur d'instruction vers celle du point d'entrée dans la fonction ;

Puis dans la fonction :
1) accéder aux paramètres directement dans la pile, sans les dépiler ;
2) dérouler le code de la fonction ;

Enfin, le return fait le ménage :
1) dépiler les paramètres ;
2) dépiler l'adresse de retour (en la mettant dans un autre registre par exemple) ;
2bis) placer la valeur de retour dans un registre particulier réservé à cet usage ;
3) changer l'adresse du pointeur d'instruction vers celle de retour.

Après, c'est à toi de trouver les mov et les registres qu'il faut utiliser, surtout pour les opérations "empiler" et "dépiler", le reste, ca devrait aller tout seul... ;)

Avatar de l’utilisateur
fatal_error
Membre Légendaire
Messages: 6610
Enregistré le: 22 Nov 2007, 12:00

par fatal_error » 29 Oct 2014, 23:46

mais à la fin il faudra bien dépiler et au final je crois qu'on va retomber sur somme = 0.


(c'est pas générique, parce que on a pas besoin de sauvegarder le contexte de la fonction (idem on attend pas le retour de la fonction qu'on appèle), ya un nom quand tu fais l'appel récursif dans le return, mais j'ai oublié...)


ben c'est complement stupide de dépiler dans la mesure ou tu as pas besoin de revenir dans ta fonction appelante!!!

si tu as un truc style
Code: Tout sélectionner
f(n){
 return f(n-1)+f(n-2)
}

ok une fois que tu as calculé f(n-1) tu dois revenir pour calculer f(n-2)
mais quand t'as
Code: Tout sélectionner
f(n){
 return 1+f(n-1) ben t'as pas besoin de revenir....
}

à la rigueur, si tu avais
Code: Tout sélectionner
f(n){
 return f(n-1) + 1 //...ben si t'es teubé, tu calcules f(n-1) d'abord puis tu reviens pour ajouter 1 XD
}

donc pour la théorie, ce que tu fais, c'est
lors du call de f (avant pour etre précis)
tu stores toutes les variables nécessaires dans un context.
tu appeles f
...
tu restores tes variables, et tu termines f

jte ferais pas le code en arm, parce que cam fout la gerbe l'assembleur, mais tu peux t'en sortir ainsi (même si je me répète récursiver sur l'enveloppe, ca sert à rien)
la vie est une fête :)

Avatar de l’utilisateur
Rockleader
Habitué(e)
Messages: 2126
Enregistré le: 11 Oct 2011, 18:42

par Rockleader » 30 Oct 2014, 00:22

Ce que je veux dire, il faut bien dépiler le contexte de la fonction pour revenir dans le main à la fin. Donc on est obligé de dépiler, mais il ne faut dépiler qu'à la fin. C'est là que c'est tordu =)


Enfin bref, c'est chiant l'arm :mur:

Parait que c'est avec ça que sont codé la plupart des programmes des smartphones --' vive la galère =)
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 16:40

par Zorro_X » 30 Oct 2014, 07:25

bah !? dépiler c'est juste décrémenter le registre de la pile (!)

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite