Récursivité

Fonctions récursives

Une fonction est qualifiée de récursive si elle s’appelle elle-même.

Par exemple, cette fonction qui permet de calculer \(x^y\) (\(y\) étant supposé > 0) :


 

 

Structure

Toute fonction récursive doit avoir, grâce à une structure conditionnelle, une condition pour laquelle elle ne s’appelle pas elle-même. Sans cela, elle ne s’arrêterait jamais !

Cette condition s’appelle le cas de base.

Dans l’exemple précédent, le cas de base est la condition y <= 0 .

En pratique Python prévoit une profondeur de récursion maximum (par défaut 1000, mais modifiable), mais l’atteindre provoque une erreur, et surtout témoigne d’une faute de programmation.

 

 

Il existe toujours une façon non récursive de réaliser une fonction donnée.

Écrire une fonction sous forme récursive est souvent plus naturel. En revanche, les grandes profondeurs de récursion peuvent solliciter fortement la mémoire et rendre son exécution plus lente.

 

Exercices

Écrire sous forme récursive la fonction : \(factorielle:x \rightarrow x!\)
Calculer l’ordre de complexité de cet algorithme.

 

Proposer un algorithme récursif de calcul de la somme de deux entiers naturels a  et b  en supposant que les seules opérations de base disponibles sont :

  • l’ajout de1 à un entier : a+= 1
  • le retrait de 1 à un entier : a-=1
  • les comparaisons à 0 d’un entier : a==0 , a>0  et a<0

Comment étendre cette fonction aux entiers relatifs ?

 

Un palindrome est un mot dont les lettres lues de gauche à droite sont les mêmes que celles lues de droite à gauche. Les mots radar , elle , été , ici  sont des palindromes.
Réaliser une fonction, selon un algorithme récursif, qui teste si un mot est un palindrome ou non.

Vous aimerez aussi...

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code