prog bash récursif factorielle

[jakol]

prog bash récursif factorielle

Bonjour,

je souhaiterais avoir des suggestions de code pour un programme récursif comptant la factoriel d'une valeur donnée.

J'ai fait le prog en itératif, mais en récursif...

voici ci-joint mon prog en itératif:

#!/bin/bash

declare -i r=1

for ((i=1;i<=$1;i++))

do

((r=r*i))

done

echo "factorielle = " $r

~

Merci d'avance pour vos réponses

[theocrite]

Ce n'est pas tellement du récursif, mais l'algo est bon.

Pour le code par contre j'ai un doute.

[BreizFenrir]

Ton code est bon, encore que je ne vois pas à quoi sert declare (et le seul declare que connait man sur mon serveur est celui utilisé en SQL). J'imagine qu'il est équivalent à "r=1".

Pour ce qui est de mettre en place un récursion, ce n'est pas bien dur à condition d'avoir fait l'effort de comprendre le principe de la récursion. Ci-dessous un code récursif qui ne fait pas grand chose (mais que tu vas pouvoir adapter à tes besoins après coup) :

#!/bin/bash
#
# Le script s'appelle "testreq" et est dans le PATH

if [ $1 -eq 0 ]
then
#ps -edf | grep testreq
echo "FIN"
else
echo "CONT $1"
testreq $(( $1 - 1 ))
fi

A noter que ce code a plusieurs défauts :

• On ne vérifie pas avant traitement que la valeur passée en paramètre est bien un nombre.
  
• En faisant en sorte que le script s'appelle lui-même, on entraine la création d'un nombre de processus bash équivalent au nombre d'itérations du script, ce qui n'est pas souhaitable. Cela se vérifie bien en décommentant la ligne précédent l'affichage de "FIN". La solution est de déclarer une fonction récursive au sein du script, qui n'est plus appelé qu'une seule fois.
  

A noter enfin qu'il n'y a pas un algorithme de récursion possible mais deux (en espérant que je ne me trompe pas dans la terminologie, mes cours étant loins...) :

• Récursion "classique" : on lance un calcul dans lequel il manque une valeur intermédiaire déterminée par récursion ; il faut donc attendre que les calculs "plus simples" soient effectués avant que le calcul qui nous intéresse puisse se faire, et éventuellement retourne sa valeur au calcul en attente un niveau au-dessus.
  
• Récursion "terminale" : plutôt que d'attendre après appel qu'une valeur nous soit retournée, on effectue notre part de calcul et envoyons la valeur calculée intermédiaire au script appelé (en plus de la valeur qui contrôle l'arrêt de l'itération), qui l'utilisera pour effectuer sa part de calcul et l'enverra au script à se suite, etc. jusqu'à la fin de l'itération, où on disposera déjà de la valeur finale, les calculs nécessaires ayant été effectués avant coup plutôt qu'après coup dans la solution "classique".
  

Un bon exercice étant, bien évidemment, d'implémenter les deux solutions.

[lorinc]

note que pour la factorielle, c'est un peu tricky car il va falloir multiplier n avec factorielle(n-1). Donc finalement, c'est le résultat de ce produit que ton scripte de factorielle doit afficher. Du coup, le résultat du niveau n-1 est pipé de la sortie standard vers une variable du niveau n.

[theocrite]

le seul declare que connait man sur mon serveur est celui utilisé en SQL

Essaye man bash, c'est une builtin

Le script s'appelle "testreq" et est dans le PATH

Pour faire quelque chose comme ça, il est bien plus simple de faire la récursion sur une fonction et non pas sur un fichier.

A noter enfin qu'il n'y a pas un algorithme de récursion possible mais deux (en espérant que je ne me trompe pas dans la terminologie, mes cours étant loins...) :

• Récursion "classique" : on lance un calcul dans lequel il manque une valeur intermédiaire déterminée par récursion ; il faut donc attendre que les calculs "plus simples" soient effectués avant que le calcul qui nous intéresse puisse se faire, et éventuellement retourne sa valeur au calcul en attente un niveau au-dessus.
  
• Récursion "terminale" : plutôt que d'attendre après appel qu'une valeur nous soit retournée, on effectue notre part de calcul et envoyons la valeur calculée intermédiaire au script appelé (en plus de la valeur qui contrôle l'arrêt de l'itération), qui l'utilisera pour effectuer sa part de calcul et l'enverra au script à se suite, etc. jusqu'à la fin de l'itération, où on disposera déjà de la valeur finale, les calculs nécessaires ayant été effectués avant coup plutôt qu'après coup dans la solution "classique".
  

Ce n'est pas exactement ça (ou alors je n'ai pas très bien compris ce que tu as voulu dire.

Il y a trois possibilités pour faire un calcul "en boucle".

• L'itératif, c'est ce que tout le monde connait (avec un for ou un while).
  
• Le récursif : C'est le fait pour une fonction de s'appeler elle même et de prendre en compte la valeur de retour afin de retourner sa propre valeur.
  
• Le récursif terminal : Lorsque l'on a des ressources limités (mémoire, disque, ...) et que l'on veut quand même faire du récursif (plus gourmand que l'itératif, car plus d'appels), alors on peut utiliser une récursion bâtarde qui consiste à ce qu'une fonction s'appelle elle même et se termine aussitôt (et qui ressemble du coup beaucoup à de l'itératif niveau implémentation). Du coup pas de pile contrairement au récursif classique.
  

[lorinc]

Y a juste un truc qui me chagrinne dans votre érécursion terminale" : la fonction appelante est forcément en attente du résultat (à moins de jouer du jump en assembleur), donc on empile quand même un paquet de merde. On empile même un plus gros paquet que dans la version récursive, car en plus de la variable récursive, il faut faire passer les résultats intermédiaire par la pile.

Perso, je trouve ça inefficace au possible, mais peut-être me trompe-je.

[theocrite]

Non justement, la récursion terminale, c'est un trub bâtard qui transforme la récursion en itération.

Donc plus de pile, par contre il faut passer un buffer qui stocke les résultats intermédiaires.

[BreizFenrir]

Le script s'appelle "testreq" et est dans le PATH

Pour faire quelque chose comme ça, il est bien plus simple de faire la récursion sur une fonction et non pas sur un fichier.

D'où mes commentaires en-dessous de mon code. Compte-tenu du problème qui nous a été présenté, j'ai supposé que notre ami jakol n'avait pas une grande expérience en bash, et je suis resté dans l'idée de faire dans le plus simple possible (quitte à faire dans l'idiot, l'objectif étant d'être didactique avant d'être complet -- même si vu la problématique, je te l'accorde, la mise en place d'une fonction n'aurait pas rendu le code moins clair ).

Sinon pour la récursion terminale, quand bien même j'ai tenté de présenter la chose j'avais les mêmes doutes que lorinc. Jusqu'à ce que Wikipedia me rappelle dans quels cas la mise en place de tels algorithmes étaient utiles (j'ai adoré faire du Scheme en école d'ingé, mais je n'y ai pas retouché depuis ).

[olasd]

Y a juste un truc qui me chagrinne dans votre érécursion terminale" : la fonction appelante est forcément en attente du résultat (à moins de jouer du jump en assembleur), donc on empile quand même un paquet de merde. On empile même un plus gros paquet que dans la version récursive, car en plus de la variable récursive, il faut faire passer les résultats intermédiaire par la pile.

Perso, je trouve ça inefficace au possible, mais peut-être me trompe-je.

La récursion terminale, ça n'est utile que dans les langages (majoritairement fonctionnels, je pense à OCaml, Scheme, diallectes de Lisp, etc.) qui l'optimisent en évitant "d'empiler le paquet de merde", par modification flot d'exécution... Ça permet d'« émuler » des structures itératives efficacement en fonctionnel pur... Mais effectivement en bash, mis à part faire péter la pile d'appels (un petit peu) plus vite je vois pas bien l'intérêt :)

A+,

[theocrite]

int test (truc)
{
 if (truc>5)
 return test (truc-1);
}

N'empile pas un paquet de merde.

[lorinc]

ah si ah si, ça empile un paquet de merde voilà comment ça se désassemble :

08048344 <test>:
8048344:	   55					  push   %ebp
8048345:	   89 e5				   mov	%esp,%ebp
8048347:	   83 ec 08				sub	$0x8,%esp
804834a:	   83 7d 08 05			 cmpl   $0x5,0x8(%ebp)
804834e:	   7e 13				   jle	8048363 <test+0x1f>
8048350:	   8b 45 08				mov	0x8(%ebp),%eax
8048353:	   83 e8 01				sub	$0x1,%eax
8048356:	   89 04 24				mov	%eax,(%esp)
8048359:	   e8 e6 ff ff ff		  call   8048344 <test>
804835e:	   89 45 fc				mov	%eax,0xfffffffc(%ebp)
8048361:	   eb 02				   jmp	8048365 <test+0x21>
8048363:	   eb 03				   jmp	8048368 <test+0x24>
8048365:	   8b 45 fc				mov	0xfffffffc(%ebp),%eax
8048368:	   c9					  leave  
8048369:	   c3					  ret

C'est à dire un bon vieux push des familles au début, on compare à 5, si le test est faux, on retourne, si le test est vrai, on fait une soustraction et un bon gros call.

Je te parie que je peux faire peter une pile en ajoutant un truc assez gros en second argument (style une grosse structure).

exemple

struct my_str_t {
	long double tab[10000];
};
typedef struct my_str_t my_str;


int test(int truc, my_str s, int i)
{
	printf("%d\n", i);
	if (truc>5)
			return test (truc-1, s, ++i);
	return truc;
}


int main(void)
{
	my_str s;

	test(1000, s, 1);

	return 0;
}

Si tu arrives à faire les 995 itérations demandées, bravo

[lorinc]

gcc est malin, je viens d'essayer avec un -O3 et ça se désassemble comme ça :

08048350 <test>:
8048350:	   55					  push   %ebp
8048351:	   89 e5				   mov	%esp,%ebp
8048353:	   8b 55 08				mov	0x8(%ebp),%edx
8048356:	   83 fa 05				cmp	$0x5,%edx
8048359:	   7e 60				   jle	80483bb <test+0x6b>
804835b:	   83 fa 06				cmp	$0x6,%edx
804835e:	   74 59				   je	 80483b9 <test+0x69>
8048360:	   83 fa 07				cmp	$0x7,%edx
8048363:	   74 54				   je	 80483b9 <test+0x69>
8048365:	   83 fa 08				cmp	$0x8,%edx
8048368:	   74 4f				   je	 80483b9 <test+0x69>
804836a:	   83 fa 09				cmp	$0x9,%edx
804836d:	   8d 76 00				lea	0x0(%esi),%esi
8048370:	   74 47				   je	 80483b9 <test+0x69>
8048372:	   8d 42 fb				lea	0xfffffffb(%edx),%eax
8048375:	   83 f8 05				cmp	$0x5,%eax
8048378:	   74 3f				   je	 80483b9 <test+0x69>
804837a:	   83 f8 06				cmp	$0x6,%eax
804837d:	   8d 76 00				lea	0x0(%esi),%esi
8048380:	   74 37				   je	 80483b9 <test+0x69>
8048382:	   8d 42 f7				lea	0xfffffff7(%edx),%eax
8048385:	   eb 2d				   jmp	80483b4 <test+0x64>
8048387:	   83 f8 04				cmp	$0x4,%eax
804838a:	   74 2d				   je	 80483b9 <test+0x69>
804838c:	   83 f8 05				cmp	$0x5,%eax
804838f:	   90					  nop	
8048390:	   7e 29				   jle	80483bb <test+0x6b>
8048392:	   83 f8 06				cmp	$0x6,%eax
8048395:	   74 22				   je	 80483b9 <test+0x69>
8048397:	   83 f8 07				cmp	$0x7,%eax
804839a:	   74 1d				   je	 80483b9 <test+0x69>
804839c:	   83 f8 08				cmp	$0x8,%eax
804839f:	   90					  nop	
80483a0:	   74 17				   je	 80483b9 <test+0x69>
80483a2:	   83 f8 09				cmp	$0x9,%eax
80483a5:	   74 12				   je	 80483b9 <test+0x69>
80483a7:	   83 f8 0a				cmp	$0xa,%eax
80483aa:	   74 0d				   je	 80483b9 <test+0x69>
80483ac:	   83 e8 09				sub	$0x9,%eax
80483af:	   83 f8 02				cmp	$0x2,%eax
80483b2:	   74 05				   je	 80483b9 <test+0x69>
80483b4:	   83 f8 03				cmp	$0x3,%eax
80483b7:	   75 ce				   jne	8048387 <test+0x37>
80483b9:	   5d					  pop	%ebp
80483ba:	   c3					  ret	
80483bb:	   5d					  pop	%ebp
80483bc:	   8d 74 26 00			 lea	0x0(%esi),%esi
80483c0:	   c3					  ret	
80483c1:	   eb 0d				   jmp	80483d0 <main>

et hop, disparu le call à test, remplacé par des jumps, dont un vers main pour la sortie finale.