Bonjour , comme spécifié en titre , j'ai un petit problème avec une fonction utilisant la récursion en scala , 

j'essaye d'écrire une fonction de trie , trie par insertion pour être exact , en utilisant la récursion , j'ai écris 2 fonction , une premiere "Insertion" qui prend une List[Int] (que l'on suppose est trié) et un entier , cette fonction insere l'entier dans la liste récusivement , et elle semble avoir aucun problème , contrairement à la deuxième fonction 

voici le code de la première fonction :

 def insertion(l : List[Int] , n :Int ) : List[Int] = {
    l match {
    
      case x :: Nil => if (x> n) n::x::Nil
                 else x::n::Nil

      case p :: i =>
              if (p> n ) n :: p::  i
              else   p :: insertion(i , n)
                           
    }
  }

et voici la deuxième fonction qui utilise la premième mais qui semble ne pas marche 

def triInsertion(l: List[Int]): List[Int] = {
    l match {
    case x :: z ::Nil => if(z<x) z::insertion(x::Nil , x)
                        else x::z::Nil
    
     case n :: i :: u => if(i<n ) i::triInsertion(n::u) 
                        else n::triInsertion(i::u)
    }
  }

j'ai déroulé cette fonction à la main et je sais à peut prêt pourquoi elle marche pas , mais je vois pas comment y remédié si quelqu'un peut m'aider s'il vous plaît

peut-être introduire d'autre fonctions auxiliaires ?

-
Edité par Freecs11 16 février 2021 à 18:09:12

Salut,

Tes cas de base sont compliqués. Utilise plutôt la liste vide comme cas de base. Insérer x dans la liste vide, c'est renvoyer la liste avec juste x, et trier la liste vide, c'est renvoyer la liste vide. Ça fait même que tes fonctions sont incorrectes. Là, tu ne peux pas insérer d'éléments dans une liste vide ou trier une liste vide.

Et finalement, le tri par insertion en récursif, c'est ça.

• Si la liste est vide, on renvoie la liste vide.
• Sinon, la liste est de la forme x::q. On trie q, ça nous donne une liste triée dans laquelle on insère x.

def insertion(l: List[Int], n: Int): List[Int] = l match {
  case Nil           => n::Nil
  case x::q if x < n => x::insertion(q, n)
  case _             => n::l
}

def triInsertion(l: List[Int]): List[Int] = l match {
  case Nil  => Nil
  case x::q => insertion(triInsertion(q), x)
}

Les > sont à remplacer par > (c'est l'éditeur Markdown d'OC qui déconne). Tu remarqueras que j'ai modifié le pattern matching de insertion avec 3 cas, un cas pour la liste vide, un cas si le premier élément est plus petit que l'élément à insérer, et un cas pour toutes les autres listes.

-
Edité par yo@n97one 16 février 2021 à 22:16:53

Merci beaucoup yo@n97one pour l'explication détaillé , effectivement vos cas de bases semblent plus pratique et plus simple à comprendre , je ne savais pas que l'on pouvais effectué le if à cette endroit x) , encore merci

aussi dans la fonction insertion , le cas universelle ' case _ => ; n::l' il ne sera jamais atteint non ? vu qu'on ai toujours soit dans Nil soit dans une liste x::q ou x::Nil ?

> aussi dans la fonction insertion , le cas universelle ' case _ => ; n::l' il ne sera jamais atteint non ? vu qu'on ai toujours soit dans Nil soit dans une liste x::q ou x::Nil ?

Le deuxième cas de la fonction insertion est « case x::q if x > n », c'est-à-dire que c'est le cas où l'élément à insérer est plus grand que le premier élément de la liste. Il y a donc bien un troisième cas, celui où l'élément à insérer est plus petit que le premier élément de la liste. On est dans ce troisième cas si on veut par exemple insérer 3 dans la liste [5, 7, 12].

En fait, quand on écrit case x::q if x > n, le cas c'est pas seulement x::q c'est la liste de la forme x::q et on a également x > n.