# Objective C et appels récursifs



## p4bl0 (28 Mai 2008)

Hello,

Ce n'est pas un problème technique que j'ai, je ne fais pas d'objective c (pour le moment du moins, je veux apprendre C++ avant).
Mais en surfant sur 99 Bottles of Beer (j'adore ce site ), j'ai vu un truc que j'avais jamais remarqué sur la version ObjC :


> Objective-C is only supposed to handle 63 recursive calls



J'ai chercher sans trop insister mais sans trouver de réponses.

C'est vrai ça ?


----------



## ntx (28 Mai 2008)

Un petit test avec ce code :

```
#import <Foundation/Foundation.h>

void maFonction(int rec)
{
  NSLog(@"Appel %@", [NSString stringWithFormat:@"%i", rec]);
  if(rec < 1000)
    maFonction(rec+1);
}

int main (int argc, const char * argv[]) {
  NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

  NSLog(@"Hello, World!");
  
  maFonction(0);
  
  [pool drain];
  
  return 0;
}
```
Ca n'a pas l'air de beaucoup le déranger  Mais c'est peut l'invocation d'un methode d'une classe qui bloque.

PS : si tu appelles une méthode d'une classe Obj-C, ça ne semble pas coincer non plus.


----------



## Eul Mulot (28 Mai 2008)

C'est vrai que le test pour le vérifier est 'achement compliqué !


----------



## p4bl0 (29 Mai 2008)

Eul Mulot a dit:


> C'est vrai que le test pour le vérifier est 'achement compliqué !


Ah heu ouais... :rateau: ça m'a tellement étonné j'y ai pas pensé :-/

Pourquoi c'est encore écrit sur ce site alors ?! Parce ce qu'en plus c'est la seule version Objective-C dispo...
C'est peut-être une private joke ou un truc du genre ? ^^.


Merci


----------



## tatouille (29 Mai 2008)

63 bottles of beer is not too much


----------



## p4bl0 (29 Mai 2008)

tatouille a dit:


> 63 bottles of beer is not too much


héhé ^^


Merci !

EDIT: n'empêche que la connerie de l'autre est toujours sur le site... Y en a pas un de vous qui se sent de faire un beau 99BoB en Objective-C ?


----------



## grumff (29 Mai 2008)

En même temps faut mieux être prudent avec les appels récursif, ça te sature la ram et la pile assez rapidement, peu importe le langage. S'il y a moyen de faire autrement (et c'est souvent le cas), c'est toujours mieux.


----------



## Dr_cube (2 Juin 2008)

Il est souvent possible d'écrire du récursif qui ne remplit pas plus la pile que de l'itératif (récursivité terminale). Mais je ne sais pas comment c'est traité en Objective C.


----------



## p4bl0 (2 Juin 2008)

Dr_cube a dit:


> Il est souvent possible d'écrire du récursif qui ne remplit pas plus la pile que de l'itératif (récursivité terminale). Mais je ne sais pas comment c'est traité en Objective C.


Tu pourrais entrer un peu plus dans les détails ou linker des articles qui en parles ? Ça m'intéresse (curiosité simplement) ?

Merci


----------



## Dr_cube (2 Juin 2008)

Bin de ce que je me souviens de mes cours, une fonction récursive est _récursive terminale_ si tous les appels récursifs ne sont pas dans un calcul (on dépile ou on s'arrête). 

Si on prend l'exemple habituel de la factorielle : 


```
int fact(int n) {
  if (n <= 1) { 
     return 1; 
  }
  return n * fact(n-1); 
}
```
Cette fonction n'est pas récursive terminale car on ne va revenir du premier appel récursif que lorsqu'on atteint le cas de base. Et donc on va empiler n appels récursifs, ce qui n'est pas bon. 

Par contre : 

```
int fact(int n, int acc) { 
  if(n <= 1) { 
    return acc; 
  } 
  return fact(n-1, n*acc); 
}
```
Cette fonction est récursive terminale. Je ne crois pas qu'il y ait une méthode générale pour transformer une fonction récursive en une fonction récursive terminale, mais en principe une bonne piste est d'utiliser un ou plusieurs accumulateurs. 
Je crois que certains (bon) compilateurs traitent les fonctions récursives terminales comme des fonctions itératives (pas de sauvegarde de contexte à chaque appel). 

J'ai retrouvé l'un de mes TP de Caml de l'année dernière qui parlait de ça, peut-être que ça pourra t'aider. Sinon il doit certainement y avoir des infos sur Google. 
http://laure.gonnord.org/pro/teaching/RICM-LP2/tp1-enonce.pdf
En tout cas en Caml c'est super important de savoir transformer des fonctions en récursives terminales, parce qu'on gagne vraiment en rapidité. Mais c'est très souvent bien plus dur à écrire, et on commence parfois par écrire la version non terminale avant de la transformer. 
Quoi qu'il en soit, on est censé pouvoir réécrire n'importe quelle fonction récursive terminale en une fonction itérative assez facilement. 

Je suis curieux de savoir comment le compilateur d'Objective C traite les fonctions récursives terminales. Je vais me renseigner un peu.


----------



## p4bl0 (2 Juin 2008)

Merci !
Très intéressant 

j'vais googler pour en apprendre plus !


----------



## tatouille (2 Juin 2008)

p4bl0 a dit:


> Merci !
> Très intéressant
> 
> j'vais googler pour en apprendre plus !




```
static int fact2(int n) {
    int i=1;
    if(0 > n)
        return fact2(-(n));
    while (n>0)
        i *= n--;        
    return i;
}

static int fact(int n) {
    if (0 > n)
        return -1;
    if (0 == n)
        return 1;
    return (n * fact(n-1));
}
```


----------



## p4bl0 (3 Juin 2008)

tatouille a dit:


> ```
> static int fact2(int n) {
> int i=1;
> if(0 > n)
> ...


Dans l'exemple que tu donnes, la seconde fonction est récusive mais pas _récursive terminale_ non ? Ou alors j'ai pas encore bien pigé le truc 

*edit:* en fait je suis à peu près sûr d'avoir saisi. Avec une fonction récursive terminale, on retourne la valeur dès qu'on arrive à la fin de la "récusivité" en stockant la valeur dans un autre paramètre, plutôt que de tout "remonter" à la fin.

Et là je pense pas que ce soit le cas.


----------



## tatouille (3 Juin 2008)

p4bl0 p4bl0, oui effectivement on peut etre bete et mechant mais c'est qu'a un moment ya des monsieurs, les mathematicans  qu'ont resolus ce genre de truc de facon plus optimizee

exemple;

f(x) = O(log n) ou Omega ou big O pour les ricains (un peu gogole)
es ce que cet "infini physique" tu vas lui donner une valeur superieur 
a la possibilite de calcul de ton CPU? ce que riviendrait a faire

f(x) = log n 

et a attendre la mort par toungua 

c'est juste qu'a un moment faut appliquer tes *théorèmes ca evite un appel inutile*, et ce qui fait partie 
de l'optmization de ton code dans n'importe quel language, chose que trop *inapliquee dans le web scripting *
trop de guiguis qu'ont rien a y faire :afraid::afraid::afraid: quelle langue de pute ce tatouille





p4bl0 a dit:


> Dans l'exemple que tu donnes, la seconde fonction est récusive mais pas _récursive terminale_ non ? Ou alors j'ai pas encore bien pigé le truc
> 
> *edit:* en fait je suis à peu près sûr d'avoir saisi. Avec une fonction récursive terminale, on retourne la valeur dès qu'on arrive à la fin de la "récusivité" en stockant la valeur dans un autre paramètre, plutôt que de tout "remonter" à la fin.
> 
> Et là je pense pas que ce soit le cas.


----------



## Dr_cube (3 Juin 2008)

Rahh tatouille je n'ai pas compris un mot de ton dernier message ! 

Effectivement sa deuxième fonction n'est pas récursive terminale, puisqu'il s'agit de la même fonction non récursive terminale que j'ai donné en exemple. La seule différence est qu'il traite le cas où le nombre donné est négatif, alors que je considère que tout nombre donné doit être positif ou nul (sans renvoyer d'erreur dans le cas contraire). 

Dans la journée je vais essayer de retrouver mes TP/TD de Caml afin de donner un exemple plus compliqué et plus réaliste que la factorielle. Tu pourras alors apprécier toute la difficulté du passage en récursif terminal.


----------



## p4bl0 (3 Juin 2008)

Dr_cube a dit:


> Rahh tatouille je n'ai pas compris un mot de ton dernier message !
> 
> Effectivement sa deuxième fonction n'est pas récursive terminale, puisqu'il s'agit de la même fonction non récursive terminale que j'ai donné en exemple. La seule différence est qu'il traite le cas où le nombre donné est négatif, alors que je considère que tout nombre donné doit être positif ou nul (sans renvoyer d'erreur dans le cas contraire).
> 
> Dans la journée je vais essayer de retrouver mes TP/TD de Caml afin de donner un exemple plus compliqué et plus réaliste que la factorielle. Tu pourras alors apprécier toute la difficulté du passage en récursif terminal.


Merci pour le temps que tu passes là dessus c'est super cool ! 

Je crois qu'en gros tatouille voulais faire passer le message suivant 





			
				decode(tatouille) :D a dit:
			
		

> "itératif, récursif, récursif terminal" tout ça c'est bien jolie mais dans la vraie vie la bonne solution c'est celle qui est vraiment optimisée à l'aide des maths et des outils mathématiques (théorême et cie) dont on dispose.



Un peu comme dans un de ses dernier post ou il "gueule" contre les "guiguis" (il aime bien ce mot ) qui passe un array de bool ou plein de bool à une fonction/méthode qui pourrait simplement recevoir un int composé à partir de flags (genre mafunct(OPTIONUN | OPTIONDEUX | OPTIONQUATRE) plutôt que mafunct(1, 1, 0, 1)).


----------



## tatouille (3 Juin 2008)

p4bl0 a dit:


> Merci pour le temps que tu passes là dessus c'est super cool !
> 
> Je crois qu'en gros tatouille voulais faire passer le message suivant
> 
> Un peu comme dans un de ses dernier post ou il "gueule" contre les "guiguis" (il aime bien ce mot ) qui passe un array de bool ou plein de bool à une fonction/méthode qui pourrait simplement recevoir un int composé à partir de flags (genre mafunct(OPTIONUN | OPTIONDEUX | OPTIONQUATRE) plutôt que mafunct(1, 1, 0, 1)).




```
#include <stdio.h>
#include <stdint.h>
#include <string.h>

void tobinstr(uint32_t x, char *buf) 
{
    uint32_t r;
    if(x <= 1)
        return;
    r = x % 2;
    tobinstr(x >> 1, buf);
    strcat (buf , (char *)(r > 0 ? "1" : "0"));
}

int main(void) {
    char buf[33];
    strcpy (buf,"0");
    tobinstr(12345, buf);
    
    printf("%s \n", buf);
    
    return 0;
}
```
un simple parse xml est une fonction recursive terminal 

tant que le nombre de node !=  0
continue

count 10 -> j'en trouve un node--

voir aussi:  O(N log 2 N)

http://en.wikipedia.org/wiki/Fibonacci_number

mais il est vraie que la recursivite terminale est plus appropriee a des languages comme o-caml ou lisp
plutot que le C


----------

