LicenceInfoLyon1

Une fonction est récursive si elle s'appelle elle-même dans sa définition. En programmation fonctionnelle comme en Scheme, la récursivité remplace souvent les boucles.

Une fonction récursive se compose généralement :

• D’un cas de base : condition d’arrêt qui retourne une valeur sans appel récursif
• D’un appel récursif : la fonction se rappelle sur une version "réduite" du problème

Scheme est un langage fonctionnel qui travaille beaucoup avec les listes. Voici quelques fonctions fondamentales :

• null? → teste si une liste est vide
• car → récupère le premier élément
• cdr → récupère le reste de la liste
• cons → ajoute un élément en tête de liste

Exemple : additionner tous les éléments d’une liste :

(define (somme lst)
  (if (null? lst)
      0
      (+ (car lst) (somme (cdr lst)))))

En récursivité, on distingue :

• Calcul descendant : les calculs s'accumulent pendant la descente, puis sont évalués à la fin (ex : (* n (fact (- n 1))))
• Calcul remontant (accumulateur) : la valeur se construit au fur et à mesure, utile pour optimiser la mémoire (tail-recursive)

Exemple descendant (factorielle) :

(define (fact n)
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

Exemple remontant (avec accumulateur) :

(define (fact-acc n acc)
  (if (= n 0)
      acc
      (fact-acc (- n 1) (* acc n))))

(define (fact-tail n)
  (fact-acc n 1))

Le tri par insertion récursif insère le premier élément au bon endroit dans une liste triée :

(define (inserer x lst)
  (cond
    ((null? lst) (list x))
    ((<= x (car lst)) (cons x lst))
    (else (cons (car lst) (inserer x (cdr lst))))))

(define (tri-insertion lst)
  (if (null? lst)
      '()
      (inserer (car lst) (tri-insertion (cdr lst)))))

Un arbre binaire est représenté en Scheme par une liste de 3 éléments : (valeur sous-arbre-gauche sous-arbre-droit)

Exemple d’arbre :

(define arbre '(5 (3 () ()) (8 (6 () ()) ())))

Parcours **infixe** (gauche → racine → droite) :

(define (parcours-infixe arbre)
  (if (null? arbre)
      '()
      (append (parcours-infixe (cadr arbre))
              (list (car arbre))
              (parcours-infixe (caddr arbre)))))

Tu peux aussi faire des parcours préfixes (racine d’abord) ou suffixes (feuilles d’abord).

Écris une fonction Scheme somme qui prend une liste de nombres et retourne leur somme.

; Résultat attendu :
(somme '(1 2 3)) ; → 6

Vérifier