Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre à l'essai
    Incompréhension sur le retour d'une fonction récursive
    Bonjour,
    Sur ce code qui détecte si un item est un palindrome ou non:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    # let rec palindrome(s) = 
        let lenItem = String.length(s) in 
            if lenItem <= 1 then true else 
            if s.[0] = s.[lenItem - 1]
            then palindrome(String.sub(s)(1)(lenItem - 2)) 
            else false;;



    si je trace palindrome sur:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    # palindrome("sages");;


    ça donne:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    palindrome <-- "sages"
    palindrome <-- "age"
    palindrome --> false
    palindrome --> false
    - : bool = false


    Je ne comprends pas pourquoi le premier retour est faux.

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    ...
    if s.[0] = s.[lenItem - 1]
    then palindrome(String.sub(s)(1)(lenItem - 2))
    ...


    "s" et bien égal à "s" on peut donc passer à la sous chaîne suivante et comparer "a" et "g" qui pour le coup ne sont pas égaux.
    Pour un résultat identique j'ai une variante avec cette fois des opérateurs booléens:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    # let rec palindrome(s) =
        let lenItem = String.length(s) in
            (lenItem <= 1) ||
            (s.[0] = s.[lenItem -1]) &&
            (palindrome(String.sub(s)(1)(lenItem -2)));;


    Et j'avoue que:

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    ...
    (s.[0] = s.[lenItem -1]) &&
    (palindrome(String.sub(s)(1)(lenItem -2)));;
    ...


    qui code que les deux expressions sont vraies simultanément me laisse plus que dubitative...

  2. #2
    Membre émérite
    Je ne comprends pas bien ce qui te fait douter, toutes tes propositions sont correctes (même si ce n'est pas tout à fait ce qu'écrirait un expert).

    palindrome "sages" retourne faux parce que palindrome "age" retourne faux.

    Je pense qu'un expert aurait écrit quelque chose comme ceci :

    Code OCaml :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    let rec palindrome s low high =
      low >= high || (s.[low] = s.[high] && palindrome s (low+1) (high-1))
     
    let palindrome s =
      palindrome s 0 (String.length s - 1);;
    Du même auteur: le cours OCaml, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  3. #3
    Membre à l'essai
    Citation Envoyé par SpiceGuid Voir le message

    palindrome "sages" retourne faux parce que palindrome "age" retourne faux.
    Évidemment,... je crois que mes neurones ont du mal à boucler dans la recursivité...
    En tous cas merci pour ton salutaire déclic.

    Citation Envoyé par SpiceGuid Voir le message


    Je pense qu'un expert aurait écrit quelque chose comme ceci :

    Code OCaml :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    let rec palindrome s low high =
      low >= high || (s.[low] = s.[high] && palindrome s (low+1) (high-1))
     
    let palindrome s =
      palindrome s 0 (String.length s - 1);;

    J'aime bien, surtout low et high,... très classe.
    Je te les pique:

    Code OCaml :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    # let palindrome(s) = 
            let rec build(low)(high) = 
                low >= high || (s.[low] = s.[high] && build(low + 1)(high - 1)) in
            build(0)(String.length(s) -1);;