Comment inverser un tableau récursivement en langage C
Dans ce tutoriel, on veut coder une fonction d'inversion de tableau récursivement. Il se trouve que la méthode récursif soit plus difficile par rapport à l'itérative, toutefois un programme récursif est plus formel.
Pour commencer, il faut définir les cas de la récursivité. Dans un premier temps, vous devez d'abord écrire le programme de la méthode itérative pour comprendre.
Cette figure explique en trois étapes l'opération de la permutation entre la case i et la case n-i, on répète l'opération jusqu'à atteindre la moitié de la longueur du tableau. Il faut répéter l'opération seulement sur la première moitié du tableau sinon on va permuter les éléments de la deuxième moitié avec ceux de la première qui ont été déjà traités, et là on retombe sur notre tableau de début.
Le code suivant permute un tableau avec la méthode itérative:
Pour commencer, il faut définir les cas de la récursivité. Dans un premier temps, vous devez d'abord écrire le programme de la méthode itérative pour comprendre.
Cette figure explique en trois étapes l'opération de la permutation entre la case i et la case n-i, on répète l'opération jusqu'à atteindre la moitié de la longueur du tableau. Il faut répéter l'opération seulement sur la première moitié du tableau sinon on va permuter les éléments de la deuxième moitié avec ceux de la première qui ont été déjà traités, et là on retombe sur notre tableau de début.
Le code suivant permute un tableau avec la méthode itérative:
#include<conio.h>L'exécution de ce code donne:
#include<stdio.h>
int main()
{
int i,n,temp;
printf("Taille du tableau ");
scanf("%d",&n);
int t[n];
for(i=0;i<n;i++)
{
printf("t[%d]=",i);
scanf("%d",&t[i]);
}
i=0;
while(i<n/2)
{
temp = t[i];
//n-1 parce que le tableau commence par 0
t[i]=t[n-1-i];
t[n-1-i]=temp;
i++;
}
printf("\nTableau inverse: \n");
for(i=0;i<n;i++)
{
printf("\nt[%d]=%d",i,t[i]);
}
getch();
}
Inverser un tableau en C avec la méthode récursif
Maintenant qu'on a notre programme de la méthode itérative, on va créer une version formelle. Vous allez poser la question, elle se diffère de quoi ? Eh bien! La version récursif est une fonction qui fait appel à lui même jusqu'à atteindre le point d'appui. Cet appel récursif est l'équivalent de la boucle dans la version itérative.
Il suffit de traduire le programme itérative pour obtenir un programme récursif. Le point d'appui est la condition d’arrêt dans la boucle while i<n/2 (dans le programme on a mis i>=(n+1)/2 parce que lors de l'appel de la fonction, on a décrémenté la taille du tableau n-1). i devient le paramètre principal de la fonction parce que le test d’arrêt se fait après chaque incrémentation de i.
Il suffit de traduire le programme itérative pour obtenir un programme récursif. Le point d'appui est la condition d’arrêt dans la boucle while i<n/2 (dans le programme on a mis i>=(n+1)/2 parce que lors de l'appel de la fonction, on a décrémenté la taille du tableau n-1). i devient le paramètre principal de la fonction parce que le test d’arrêt se fait après chaque incrémentation de i.
L'exemple suivant montre comment inverser les éléments d'un tableau en C de façon récursif.
#include<conio.h>
#include<stdio.h>
int* inverse(int[],int,int);
main()
{
int i,n;
printf("La taille du tableau ");
scanf("%d",&n);
int t[n];
int *ti;
for(i=0;i<n;i++)
{
printf("t[%d]=",i);
scanf("%d",&t[i]);
}
ti=inverse(t,n-1,0);
printf("\nle tableau inverse est: \n");
for(i=0;i<n;i++)
{
printf("\nt[%d]=%d",i,ti[i]);
}
getch();
}
int* inverse(int t[],int n, int i)
{
int temp;
if(i>=(n+1)/2 )
return t;
else{
temp = t[i];
t[i]=t[n-i];
t[n-i]=temp;
return inverse (t,n,i+1);
}
}
La compilation et l'exécution de ce code donne le résultat suivant:
