Différence entre récursion et itération

Un programme est dit récursif lorsqu’une entité s’appelle elle-même. Un programme est appelé itératif lorsqu’il y a une boucle (ou répétition).

Exemple : Programme pour trouver la factorielle d’un nombre

Vous trouverez ci-dessous des explications détaillées pour illustrer la différence entre les deux :

Pour un aperçu, 👉 cliquez sur une couverture pour feuilleter le livre sur Amazon 📚.


1 – Complexité du temps : Trouver la complexité temporelle de la récursion est plus difficile que celle de l’itération.

  • Récursion : La complexité temporelle de la récursivité peut être trouvée en trouvant la valeur du n-ième appel récursif par rapport aux appels précédents. Ainsi, trouver le cas de destination en termes de cas de base, et le résoudre en termes de cas de base nous donne une idée de la complexité temporelle des équations récursives.
  • Itération : La complexité temporelle de l’itération peut être trouvée en trouvant le nombre de cycles qui se répètent à l’intérieur de la boucle.

2 – Utilisation : L’utilisation de l’une ou l’autre de ces techniques est un compromis entre la complexité temporelle et la taille du code. Si la complexité temporelle est le point central, et que le nombre d’appels récursifs est important, il est préférable d’utiliser l’itération. Cependant, si la complexité temporelle n’est pas un problème et que la taille du code l’est, la récursivité serait la solution.

  • Récursion : La récursivité consiste à appeler la même fonction à nouveau, et donc, a une très petite longueur de code. Cependant, comme nous l’avons vu dans l’analyse, la complexité temporelle de la récursion peut devenir exponentielle lorsqu’il y a un nombre considérable d’appels récursifs. Par conséquent, l’utilisation de la récursion est avantageuse dans le cas d’un code plus court, mais d’une complexité temporelle plus élevée.
    Itération : L’itération est la répétition d’un bloc de code. Cela implique une plus grande taille de code, mais la complexité temporelle est généralement moindre que pour la récursivité.

3 – Répétition infinie : La répétition infinie en récursion peut entraîner un crash du processeur mais en itération, elle s’arrête lorsque la mémoire est épuisée.

  • Récursion : Dans la récursion, des appels récursifs infinis peuvent se produire en raison d’une erreur de spécification de la condition de base, qui, ne devenant jamais fausse, continue d’appeler la fonction, ce qui peut entraîner un crash du CPU du système.
  • Itération : L’itération infinie due à une erreur dans l’affectation ou l’incrémentation de l’itérateur, ou dans la condition de fin, conduira à des boucles infinies, qui peuvent ou non conduire à des erreurs système, mais arrêteront sûrement l’exécution du programme plus loin.
PROPRIÉTÉ RÉCURSION ITÉRATION
Définition La fonction s’appelle elle-même. Un ensemble d’instructions exécutées de manière répétitive.
Application Pour les fonctions. Pour les boucles.
Terminaison Par le cas de base, où il n’y aura pas d’appel de fonction. Lorsque la condition de sortie de l’itérateur cesse d’être remplie.
Utilisation Utilisé lorsque la taille du code doit être petite et que la complexité du temps ne pose pas de problème. Utilisé lorsque la complexité temporelle doit être compensée par une taille de code plus importante.
Taille du code Taille du code plus petite Taille du code plus grande.
Complexité temporelle Très grande (généralement exponentielle) complexité temporelle. Complexité temporelle relativement plus faible (généralement polynomiale et logarithmique).

Métier : Développeur – développeuse Web

Le développeur Web est un expert des langages informatiques. Il traduit le cahier des charges fourni par un client en lignes de code informatique afin de concevoir des programmes sur mesure. Il conçoit l’application, assure le suivi des tests, réalise la documentation associée, implémente la solution avec les technologies retenues. Par la suite, il intervient pour effectuer la maintenance ou faire évoluer les programmes. La révolution numérique le place parmi les professionnels les plus recherchés.

Cliquez ici pour voir la fiche métier de l’Onisep: développeur/euse informatique

Pour en savoir plus


Les Metiers du Web

Brexit : comment le référendum européen a été gagné grâce à la science des données

« Tout le monde sait qui a gagné, mais peu de gens savent comment »

Brexit La Guerre incivile nous a montré comment le référendum européen a été gagné grâce à la science des données

QUI SE CACHE DERRIÈRE LE VOTE « NON » DU BREXIT ?

Été 2016. Le Royaume-Uni est en pleine campagne électorale. Les camps du « Leave » (quitter l’Europe) ou du « Remain » (rester dans l’Europe) s’affrontent. Dominic Cummings (Benedict Cumberbatch), directeur de la campagne en faveur du Brexit, use d’une stratégie inédite. Basé sur les données d’algorithmes sophistiqués explorant les recoins les plus sombres d’Internet, le but est de rechercher les électeurs cachés. Cette tactique ne fait pas l’unanimité auprès des partisans du Leave. Les coups bas et les trahisons commencent…

Brexit La Guerre incivile

Dans Brexit La Guerre incivile, on peut voir comment Dominic a fait enfermer une équipe de Data Scientists de AggregateIQ dans une pièce ombragée, comme une sorte de projet séparé du reste de la campagne de Leave.

La première chose qu’on les voit faire est de créer une campagne pour savoir ce que les différents groupes d’électeurs pensent des différentes questions concernant l’UE. Pour ce faire, ils ont donné aux gens la possibilité de gagner un pari global, qui serait statistiquement presque impossible à gagner (une chance sur 5 000 000 000 000 000 000 000 000). Ils ont ensuite utilisé les résultats de cette recherche pour créer des messages comportementaux microciblés à l’intention de différents segments de l’électorat.

 

Il a été constaté que pendant le référendum, ils ont diffusé plus d’un milliard de publicités sur Facebook, avec divers messages en faveur du congé. Par exemple, des segments d’électeurs moins “racistes” ont pu recevoir des photos de Boris Johnson déclarant : “Je suis pro-immigration, mais surtout, je suis pour l’immigration contrôlée”. Alors que d’autres ont reçu des messages tels que “La TURQUIE A UNE POPULATION DE 76 MILLIONS. LA TURQUIE REJOINT L’UE. BONNE IDÉE ?”.

 

S’ils cliquaient sur l’annonce correspondante, ils recevraient alors une horde d’annonces en continu sur le même sujet, ce qui renforcerait ce point de vue. M. Cummings a déjà expliqué comment ils ont retenu la majorité de leur budget et l’ont consacré à ce type de publicité dans les dix derniers jours précédant le référendum européen. Il affirme qu’environ 7 millions de personnes ont été visées pendant cette période.

 

Dans Brexit La Guerre incivile, on voit même l’équipe de la campagne “Leave” demander pourquoi les publicités ne sont pas diffusées à la télévision et dans les journaux télévisés, alors qu’elle pensait que l’autre camp n’avait aucune idée de ce qui se passait.

Pourquoi la science des données modifie-t-elle le paysage politique ?

Bien sûr, quiconque suit même légèrement le cycle des nouvelles en Occident aura probablement entendu parler du scandale de Cambridge Analytica. Cambridge Analytica a été créé et dirigé par Robert Mercer (un expert milliardaire de l’IA) et Steve Bannon, le financier et directeur de campagne de Donald Trump. Christopher Wyle, dénonciateur de Cambridge Analytica, a souligné les liens étroits entre AggregateIQ et Cambridge Analytica.

Ce scandale nous a montré que, grâce à l’utilisation abusive des données des utilisateurs de Facebook, ils pouvaient établir le profil psychométrique de l’ensemble de l’électorat. En utilisant une application de personnalité virale appelée myPersonality, ils ont pu croiser les types de personnalité avec ce que les gens avaient aimé sur Facebook pour profiler les gens avec un haut degré d’exactitude.

Les données recueillies et utilisées pour alimenter les algorithmes de profilage de l’électorat sont devenues une arme essentielle lors du référendum européen et des élections américaines. Wyle a même décrit comment Steve Bannon a qualifié ces outils d’armes dans sa “guerre psychologique”, avec pour objectif de susciter des mouvements populistes nationalistes dans le monde entier.

Si certains peuvent s’opposer à cette forme de manipulation politique et la considèrent comme effrayante. Sur une note positive, Cambridge Analytica a maintenant fermé ses portes en raison de la pression politique intense qui a suivi les retombées de l’élection de Donald Trump, Facebook a pris des mesures pour lutter contre la fuite de données de tiers qui a permis la création de ces outils scientifiques, et la protection des citoyens européens par RGPD signifie que vous avez désormais plus de contrôle sur l’utilisation de vos données personnelles. La prochaine fois que cela se produira, ce ne sera probablement pas aussi facile ni aussi inaperçu.

Malheureusement, d’autres entreprises comme Cambridge Analytica existent toujours et continueront à le faire tant qu’il y aura une demande suffisante. Les politiciens dépensent beaucoup d’argent dans des campagnes, bien sûr, ils vont utiliser les dernières techniques et technologies pour essayer de gagner.

Attendez-vous à ce que ce soit la nouvelle norme

Vous pouvez vous en défaire si vous n’êtes pas satisfait du résultat du référendum européen ou de l’élection de Donald Trump. C’est simplement parce que les mouvements populistes nationaux sont arrivés les premiers.

Depuis que nous sommes entrés dans l’ère numérique, nous partageons de plus en plus de données sur nous-mêmes et nous créons de nouvelles voies pour que l’information nous atteigne. Le marketing et la publicité modernes consistent de plus en plus à créer des messages pertinents et personnalisés à l’intention de segments cibles de plus en plus granuleux, la politique n’étant qu’un client parmi d’autres sur ce marché.

La science des données trouvera des moyens d’assembler nos informations pour créer des profils de nous afin de s’assurer que les bons messages nous parviennent. Les campagnes politiques trouveront des moyens de rechercher nos états émotionnels sur des questions particulières et de créer des messages qui suscitent en nous une réaction de vote particulière. Des plateformes continueront d’exister pour permettre à ces messages de campagne ciblés de nous atteindre.

Si Brexit La Guerre incivile m’a montré quelque chose, c’est l’échec de la campagne Remain à adopter les derniers outils et technologies disponibles grâce à l’explosion de la science des données. Ils auraient pu eux aussi cibler les électeurs que la campagne “Leave” visait et ceux qui ne se sont pas donné la peine d’aller voter. Comme les sondeurs traditionnels, ils ont utilisé les mêmes vieilles techniques qui ont été utilisées pendant des décennies et n’ont pas réussi à les appliquer correctement.

Il est temps que la politique entre dans le 21ème siècle

Nous vivons maintenant dans ce que l’on appelle l’ère de l’après-vérité, il s’agit moins d’argumenter le pour et le contre dans un débat rationnel, mais de lancer des “grenades” d’informations (qu’elles soient vraies ou fausses) qui résonnent avec l’électorat de manière émotionnelle, ce qui oblige ensuite l’opposition à “éteindre les feux”.

Cela peut être une voie à double sens, je ne propose certainement pas que le mensonge soit acceptable, il serait parfaitement possible de construire de meilleurs outils de vérification des faits qui permettraient de vérifier en temps réel les fausses informations à l’avenir pour aider à faire face à cela. Mais je dis que les campagnes, quel que soit le côté de l’argument, doivent apprendre de Cambridge Analytica et d’AggregateIQ que l’ancienne façon de faire de la politique est révolue, la science des données est là pour rester. Le gagnant est celui qui reste en tête du jeu.

Brexit La Guerre incivile

Pour aller plus loin

Data scientist : Connaissez-vous Billy Beane ?

Le Stratège, film de Bennett Miller sorti en 2011, raconte l’histoire de Billy Beane, sélectionneur d’une équipe de baseball qui décida d’utiliser des méthodes statistiques et d’analyse de données pour assembler une équipe capable de gagner la Ligue majeure de baseball américaine.

Billy Beane, pionnier de l’utilisation de la data

En 2002, l’équipe de baseball Oakland Athletics se fait rafler ses meilleurs joueurs par les Yankees. Une équipe de renom au budget gargantuesque : 125 millions de dollars par an. Quand on sait que les Athletics doivent même payer leurs canettes de soda, on comprend vite le déséquilibre…

Frustré et à cours d’argent, Billy Beane décide de former une toute nouvelle équipe avec l’aide d’un économiste particulièrement fan des théories mathématiques de Bill James. Tous les deux vont alors utiliser les statistiques « sabermetrics » pour recruter des talents moins cotés et pour sélectionner les meilleurs joueurs à chaque poste. Une méthode raillée à ses débuts mais qui porte ses fruits très rapidement ! Aujourd’hui, pas une équipe de sport ne travaille sans l’analyse statistique des datas.

La victoire des canards boiteux… et des stats

Jugée au départ comme une équipe de bras cassés (trop vieux, blessés, impopulaires…), les Athletics remportent finalement 20 victoires consécutives, battant ainsi le record de l’American League. Et le tout pour un budget de 41 millions de dollars, soit 3 fois moins que celui des Yankees.

Le Stratège de Bennett Miller avec Brad Pitt et Jonah Hill est sorti en 2011 et est adapté du livre Moneyball de Michael Lewis publié en 2003.

Moneyball – The Art of Winning an Unfair Game

Source : Le Stratège : l’analyse statistique au service de la performance

Quel livre choisir en Terminale NSI ?

Il existe actuellement 5 livres destinés aux élèves de Terminale qui ont choisi la spécialité NSI  (« Numérique et sciences informatiques ») et qui souhaitent acquérir un très bon niveau dans l’optique d’aborder dans les meilleures conditions la Terminale et, bien sûr, de réussir le bac, pourquoi pas avec mention.

Ils sont un outil indispensable pour ceux qui souhaitent poursuivre des études supérieures dans une formation ayant une composante informatique importante.

Tous ces livres de Terminale NSI, suivent strictement le programme de la spécialité conforme à la réforme du Bac 2021. Ils exposent en détail chaque notion avec rigueur. Ils aident à acquérir des savoirs solides permettant de développer des capacités de raisonnement et de résolution qui sont la clé de la réussite dans les études supérieures scientifiques.

Les 5 livres de Terminale NSI ont des différences que je développerai dans d’autres articles mais aussi des points communs.

  • Le cours, sous forme de synthèse ou rappel de cours,  pour vous permettre d’accéder à une connaissance synthétique des notions.
  • Des QCM, pour tester votre compréhension du cours et vous éviter de tomber dans les erreurs classiques.
  • Des exercices et les corrigés détaillés et commentés.

Quel livre choisir en première NSI ?

Il existe actuellement 6 livres destinés aux élèves de Première qui ont choisi la spécialité NSI  (« Numérique et sciences informatiques ») et qui souhaitent acquérir un très bon niveau dans l’optique d’aborder dans les meilleures conditions la Terminale et, bien sûr, de réussir le bac, pourquoi pas avec mention.

Ils sont un outil indispensable pour ceux qui souhaitent poursuivre des études supérieures dans une formation ayant une composante informatique importante.

Tous ces livres de première NSI, suivent strictement le programme de la spécialité conforme à la réforme du Bac 2021. Ils exposent en détail chaque notion avec rigueur. Ils aident à acquérir des savoirs solides permettant de développer des capacités de raisonnement et de résolution qui sont la clé de la réussite dans les études supérieures scientifiques.

Les 6 livres de première NSI ont des différences que je développerai dans d’autres articles mais aussi des points communs.

  • Le cours, sous forme de synthèse ou rappel de cours,  pour vous permettre d’accéder à une connaissance synthétique des notions.
  • Des QCM, pour tester votre compréhension du cours et vous éviter de tomber dans les erreurs classiques.
  • Des exercices et les corrigés détaillés et commentés.

Pour aller plus loin

Métier : Community manager

Le community manager (appelé aussi chargé de communication Web ou social media manager) a pour mission de s’assurer de la présence et de la bonne réputation d’une entreprise sur les réseaux sociaux. Pour cela, il anime une communauté d’internautes, publie des tweets, répond aux questions sur le site internet de l’entreprise, alimente la page Facebook

Community Manager

Vidéo Onisep: community manager

Pour en savoir plus


Les Metiers du Web

Comprendre les fonctions récursives avec Python

Introduction

Lorsque nous pensons à répéter une tâche, nous pensons généralement aux boucles For et While. Ces constructions nous permettent d’effectuer des itérations sur une liste, une collection, etc.

Cependant, il existe une autre forme de répétition d’une tâche, d’une manière légèrement différente. En appelant une fonction sur elle-même, pour résoudre une petite instance du même problème, nous effectuons une récursion.

Ces fonctions s’appellent elles-mêmes jusqu’à ce que le problème soit résolu, divisant pratiquement le problème initial en de nombreuses petites instances de lui-même; comme par exemple, prendre de petites bouchées d’un plus gros morceau de nourriture.

L’objectif final est de manger toute l’assiette. Vous le faites en prenant une bouchée encore et encore. Chaque bouchée est une action récursive, après laquelle vous entreprenez la même action la fois suivante. Vous faites cela pour chaque bouchée, en évaluant que vous devez en prendre une autre pour atteindre le but, jusqu’à ce qu’il n’y ait plus de nourriture dans votre assiette.

Pour un aperçu, 👉 cliquez sur une couverture pour feuilleter le livre sur Amazon 📚.


Qu’est-ce que la récursion ?


Comme indiqué dans l’introduction, la récursion implique un processus qui s’appelle lui-même par définition. Une fonction récursive comporte généralement deux composantes :

  • Le cas de base, qui est une condition qui détermine quand la fonction récursive doit s’arrêter
  • L’appel à soi-même

Prenons un petit exemple pour démontrer les deux composantes :

Le cas de base pour nous est que si la variable i est égale à 0, c’est-à-dire combien de chaînes “Bonjour !” restantes nous devons imprimer. La fonction s’arrêtera tout simplement.

Après l’instruction print, nous appelons à nouveau bonjour_recursive mais avec une valeur i réduite. C’est important ! Si nous ne réduisons pas la valeur restante, la fonction sera exécutée indéfiniment. En général, lorsqu’une fonction récursive s’appelle elle-même, les paramètres sont modifiés pour être plus proches du cas de base.

Visualisons comment cela fonctionne lorsque nous appelons bonjour_recursive(5) :

Après que la fonction ait affiché “Bonjour !”, elle s’appelle elle-même avec une valeur inférieure pour rester jusqu’à ce qu’elle atteigne 0. À zéro, la fonction retourne à l’endroit où elle a été appelée dans bonjour_recursive(1), qui retourne à l’endroit où elle a été appelée dans bonjour_recursive(2) … et qui retourne finalement à l’endroit où elle a été appelée dans bonjour_recursive(5).

Pourquoi ne pas utiliser une boucle ?

Toutes les opérations peuvent être effectuées à l’aide de boucles. Néanmoins, certains problèmes sont souvent plus faciles à résoudre avec la récursion plutôt qu’avec l’itération. Un cas d’utilisation courant de la récursion est le parcours d’un arbre :

Il est généralement plus facile de penser à la traversée des nœuds et des branches d’un arbre en utilisant la récursion. Même si les boucles et la récursivité parcourent toutes les deux l’arbre, elles ont des objectifs différents : les boucles sont destinées à répéter une tâche alors que la récursivité est destinée à décomposer une grande tâche en tâches plus petites.

La récursion avec les arbres par exemple fonctionne bien parce que nous pouvons traiter l’arbre entier en traitant individuellement des parties plus petites de l’arbre.

Exemples

La meilleure façon de se familiariser avec la récursion, ou tout autre concept de programmation, est de la pratiquer. La création de fonctions récursives est simple : veillez à inclure dans votre programme votre cas de base et à appeler la fonction de manière à ce qu’elle se rapproche du cas de base.

Somme d’une liste

Python inclut une fonction de somme pour les listes. L’implémentation par défaut de Python, utilise une boucle de for-loop en C pour créer cette fonction.

Voyons comment faire avec la récursion :

Le cas de base est la liste vide – la meilleure somme pour cela est 0. Une fois que nous avons traité notre cas de base, nous supprimons le dernier élément de la liste. Nous appelons enfin la fonction sum_recursive avec la liste réduite, et nous ajoutons le nombre que nous avons retiré au total.

Conclusion

La récursivité nous permet de décomposer une grande tâche en de plus petites en s’appelant de façon répétitive. Une fonction récursive nécessite un cas de base pour arrêter l’exécution, et l’appel à soi-même qui conduit progressivement à la fonction au cas de base. Elle est couramment utilisée dans les arbres, mais d’autres fonctions peuvent être écrites avec la récursivité pour fournir des solutions élégantes.

E3C – NSI – QCM sujet 0 – partie 5/7

E3C en première NSI

Pour les élèves qui ne conservent pas la spécialité numérique et sciences informatiques (NSI) en terminale devront passé au dernier trimestre de l’année de première la session commune de contrôle continu (E3C).

L’évaluation de type QCM aura une durée : 2 heures, avec un coefficient de 5
.

L’épreuve de spécialité numérique et sciences informatiques est un questionnaire à choix multiple en 7 parties, chacune composée de 6 questions.

La calcultarice est interdite pour cette épreuve.

QCM – NSI sujet 0

Les QCM d’entrainement E3C – NSI sujet n°0 est là pour vous permettre de vous mettre en situation et de vous préparer à l’épreuve de spécialité numérique et sciences informatiques (NSI) pour la sessioncommune de contrôle continu (E3C).

Chaque QCM correspond à une partie du programme officiel de la spécialité numérique et sciences informatiques (NSI) de première.

Les QCM vous permettront de connaître votre niveau, de mémoriser vos leçons plus facilement et de savoir sur quels points vous devez encore vous améliorer pour obtenir le diplôme sans problème.

Avantages du QCM en ligne

  • Pour réviser ou s’entrainer,
  • Corrections immédiates avec le barème officiel avec le corrigé détaillé,
  • Nombre d’essais illimité,
  • Fonctionne sur tous les appareils ordinateurs, tablette et smartphone et sur tout les système (Windows, Ios, linux)
  • Avec les QCM en ligne vous réviser quand et où vous voulez

Tester le QCM – NSI sujet 0 en ligne

Pour réviser et vous entrainer à cette épreuve, je vous propose de tester GRATUITEMENT le QCM de la première partie du sujet  n°0 officiel ; Architectures matérielles et systèmes d’exploitation

Cliquez ici pour vous inscrire:

Je m’inscris !

Pour aller plus loin

Show Buttons
Hide Buttons
Translate »