Complexité d'une fonction récursive

Bonjour,

J'aimerai bien savoir votre avis sur la complexité de cette fonction récursive suivante :

Code:

---

1 2 3 4 5 6

int fct(int n) { if(n < 0) return 1; else return (fct(n-1) - fct(n-1)); }

---

Mercii pour votre aide.

Sisiniya.

Pour la complexité je dirais en 0(N!)
Maintenant quand à ton code je ne vois pas trop son intérêt, il renverra toujours 0 :haha:
Tu calcules fct de n-1 et tu le soustrait à fct de n-1 du coup f(n-1) - f(n-1) = 0 ;)

Oui il renvoi 0 pour des nombres positives c'est ça. Juste c'est un exemple pour calculer la complexité de ce type de fonction récursive.

En fait, pourquoi vous avez dit O(n!), moi je vois que c'est O(n) . Que dites - vous ?

Merci.

Sisiniya

O(2^n) . Plus précisément, (2)^(n+1)-1

Tu appelle deux fois ta fonction en n-1. Donc à chaque étape, tu double ton nombre de fonction appelé ! Et c'est pas parce-que c'est la même fonction qu'elle n'est pas renouvelé entièrement.

n=0, 1
n=1, 3 = 2*1 +1
n=2, 7 = (2*1 + 1)*2+1
etc...