épreuve écrite d'info à l'ENS

[rstuvw]

Bonjour à tous,
Je m'entraînais à faire le sujet d'info 2006 de l'ENS et en regardant le corrigé ce qui me surprend un peu est que les fonctions ne contiennent aucun appel récursif (même quand ça serait, il me semble, naturel ). Quelqu'un aurait une explication?
Autre question, pour ceux qui ont fait le sujet : je ne vois pas d'où sortent les complexités en O( |A|+|S|) ...

merci d'avance

Edit : pour avoir une idée ce sujet est-il plutôt difficile ou facile pour l'ENS info? classique ou original?

[Nuhlanaurtograff]

Je m'entraînais à faire le sujet d'info 2006 de l'ENS et en regardant le corrigé ce qui me surprend un peu est que les fonctions ne contiennent aucun appel récursif (même quand ça serait, il me semble, naturel ). Quelqu'un aurait une explication?

Quelles questions nécessitent d'après toi de la récursivité, parce que ça ne m'a pas semblé si évident (j'ai pas regardé en détail) ? J'ajoute au passage que l'énorme avantage d'une fonction itérative est qu'on peut très facilement expliciter sa complexité et son comportement, chose plus délicate à faire dans le cas récursif.

Autre question, pour ceux qui ont fait le sujet : je ne vois pas d'où sortent les complexités en O( |A|+|S|) ...

Quand tu parcours une liste d'adjacence d'un sommet de taille k, tu viens en fait de visiter k arêtes. Quand tu as parcouru tous les sommets et toutes leurs listes d'adjacence, tu as donc parcouru tous les sommets et toutes les arêtes.

[fakbill]

Je savais que les taupins MP info aimaient beaucoup le rec car c'est la façon dont on leur enseigne l'info. Par contre, je ne savais pas que s'en était au point de trouver étrange quand tout un code est écrit en iter

n! pour moi c'est une boucle. C'est ce qui me vient en premier.

[rstuvw]

Merci pour ta réponse Nuhlanaurtograff.