ALMO TP n°2 - Fonctions imbriquées et récursives

Préambule

Ce TP utilise encore le simulateur MARS vu au TP précédent. Il a pour but d'illustrer comment les conventions définies pour les appels de fonctions permettent à une fonction d'en appeler une (ou plusieurs) autre(s), voire de s'appeler elle-même dans le cas des fonctions récursives.

1. Moyenne de N entiers stockés dans un tableau

On souhaite écrire en assembleur MIPS32 le programme C qui calcule la valeur moyenne de tous les entiers (non négatifs) stockés dans un tableau de dimension quelconque. Par convention, et pour pouvoir réutiliser la fonction sumtab(), on suppose que le dernier élément du tableau possède une valeur négative. Ce dernier élément n'est pas pris en compte dans le calcul de la moyenne.

Le programme principal appelle la fonction arimean() qui a pour seul argument un pointeur sur un tableau d'entiers. Elle renvoie la valeur de la moyenne arithmétique des éléments du tableau (tronquée à la valeur entière inférieure). La fonction arimean() appelle elle-même la fonction sizetab() qui prend pour seul argument le pointeur sur le tableau, et renvoie le nombre d'éléments non négatifs contenus dans le tableau. Elle appelle ensuite la fonction sumtab(), qui calcule la somme de tous les entiers non négatifs contenus dans le tableau. Elle effectue la division entière et renvoie le quotient au programme appelant.

L'ensemble du programme s'écrit en C de la façon suivante :

#include <stdio.h>

/* variables globales initialisées */
int tab[] = {23, 7, 12, 513, -1} ;

/* programme principal */
int main(void)
{
    int x = arimean(tab);
    printf(" %h ", x);
    return 0;
}

/* cette fonction renvoie la moyenne arithmétique des éléments d'un tableau */
int arimean(int t[])
{
    int n = sizetab(t);
    int x = sumtab(t);
    return (x / n);
}

/* cette fonction renvoie le nombre d'éléments d'un tableau */
int sizetab(int t[])
{
    int index = 0;
    while (t[index] >= 0)
    {
        index++;
    }
    return index;
}

/* cette fonction renvoie la somme des éléments d'un tableau */
int sumtab(int t[])
{
    int accu = 0;
    int index = 0;
    while(t[index] >= 0)
    {
        accu = accu + t[index];
        index++;
    }
    return accu;
}

• Écrire le programme assembleur correspondant à ce programme C, et exécutez-le à l'aide du simulateur MARS. Commencer, pour chaque fonction, à déterminer les valeurs nr, nvet 'na`. Vous pouvez aussi dessiner l'état de la pile à l'entrée dans une fonction et après son prologue.

2. Fonctions récursives : calcul de la factorielle

On souhaite écrire en langage d'assemblage MIPS32 le programme de calcul de la factorielle d'un nombre entier positif. On rappelle que fact(n) se note n!, et vaut :

n! = n * (n-1) * (n-2) * .. * 2 * 1

On peut également définir la fonction factorielle par la relation de récursion suivante :

• n!  = (n-1)! * n (si n > 0)
• 0! = 1

En utilisant cette définition récursive, on peut écrire un programme C qui calcule la factorielle d'un entier quelconque, en utilisant la fonction fact(n), définie ci-dessous en langage C :

/* fonction fact */
int fact(int n)
{
    if (n == 0)
    {
        /* cas terminal */
        return 1;
    }
    else
    {
        /* récursion */
        return fact(n - 1) * n;
    }
}

/* programme principal */
int main(void)
{
    printf("%h\n", fact(5));
    return 0;
}

• Écrire le code assembleur du programme principal et de la fonction fact(). La fonction fact() possède une seule variable locale et utilise deux registres. Exécutez ce programme sous MARS. Représenter graphiquement les valeurs contenues dans la pile après une exécution du programme lorsque la valeur de n vaut '3'.

• Que se passe-t-il lorsque la valeur du paramètre 'n' est positive mais très grande (égale à 1000 par exemple) ?

• Que se passe-t-il lorsque la valeur du paramètre 'n' est négative ?

• Que peut-on faire pour résoudre ces difficultés ?