La fonction F peut-elle être un sous-programme ? Dans ce cas c'est facile.
Soit "LISTE" la liste entrée en paramètre de F.
1. création d'une liste vierge "ETSIL"
2. soit A = list.head de la "LISTE"
3. on applique A+list sur "ETSIL"
4. list.tail sur "LISTE"
5. Si list.empty (de "LISTE") = 0 alors reprendre à la ligne 2, sinon aller à 6
6. afficher "ETSIL"
7. fin

Bonjour,
Je ne suis pas très familier avec ce genre de syntaxe, mais est-ce que le programme suivant te convient ?

F(liste)
{
if list.empty(liste) then
else F(list.tail(liste)) + list.head(liste)
}

Si par hasard l'instruction Then suivie de rien ne convient pas, alors on peut faire un peu plus compliqué :

F(liste)
{
if list.empty(list.tail(liste)) then liste
else F(list.tail(liste)) + list.head(liste)
}

Klim.

La taille de la liste est définie, plafonnée,  ou le programme doit faire avec ce qui vient ?

@gwen: la taille de la liste n'est pas connue à l'avance. Ça serait trop facile sinon
@Klim: Bravo ! Mais presque : ta solution suppose que {}.tail = {}, autrement dit que la queue d'une liste vide est une liste vide. Or l'énoncé ne précise rien de tel, au contraire : tail renvoyant la liste privée de son premier élément on pourrait en déduire que tail ne fonctionne QUE lorsque la liste n'est pas vide (le contraire est vrai aussi et en pratique c'est le genre de détails qui sont laissés à l'appréciation du développeur ^^).
Bref, la modification à apporter est mineure, si tu l'intègres la solution sera parfaite.

Ce langage doit également permettre la création de liste je suppose.

public function F(List list){
if(! list.empty()){
return list.head()+F(list.tail())
}
}

Bonjour

je propose le programme suivant :

Définition F (l : liste d'entier) :=
if l.empty then l
else if (l.tail).empty then l
else (F l.tail).head + (F (l.head + F (F l.tail).tail))

Moralement on utilise l'idée que
-F (A + l) = (F l) "+" A où  "+" est le + avec les types des arguments inversés.
-F(F l) = l.

OK, du coup, je te propose de résoudre F(F(liste)) !

Mince, je ne vois pas. F(F(liste)) = Identité, F-1(liste)=F(liste), ça ne m'avance pas... J'y remettrai peut-être le nez demain...

Au final, bonnes réponses de Klim, Cogito et w9Lyl6n et merci aux autres participants.

Pour résoudre ce problème :
supposons qu'on ait une fonction F qui marche pour les listes de N éléments ou moins, et considérons une liste L de N+1 éléments.
- L.tail comporte N éléments, donc F(L.tail) nous renverra L.tail inversée
- F(L.tail).head retourne donc le dernier élément de L. Il ne reste plus qu'à l'ajouter à tous les autres
- F(L.tail).tail retourne tous les éléments sauf les premiers / derniers (soit N-1 éléments au total), mais inversés. F(F(L.tail).tail) retourne donc ces mêmes éléments dans l'ordre original (puisque F(F(liste)) = liste, comme l'indiquait l'indice)
- Par conséquent, L.head + F(F(L.tail).tail) correspond aux N premiers éléments de la liste, et donc F(L.head + F(F(L.tail).tail)) à ces mêmes éléments en ordre inverse
- Et pour finir, F(L.tail).head + F(L.head + F(F(L.tail).tail)) correspond à notre liste L complète et inversée.

Les cas L={} et L=singleton sont assez simples à gérer pour initialiser notre fonction F:

F(Liste L)
{
  if(L.empty) return L   // Cas d'une liste vide
  else if (L.tail.empty) return L  // Cas d'un singleton
  else return F(L.tail).head + F(L.head + F(F(L.tail).tail)) // Cas récursif
}

Et voilà !

La question qui se pose est "pourquoi diable utiliserai-je un langage aussi tordu !?"
La réponse est la suivante: en informatique, les listes d'éléments peuvent être impléméntées de diverses manières, la plus répandue étant celle des "listes chainées". Un élément de cette liste comprend 2 valeurs
- la première, disons VALUE, correspond à la valeur stockée
- la seconde, disons NEXT, correspond à l'adresse en mémoire de l'élément suivant (un pointeur en langage technique).

Une liste est donc définie par son premier élément, avec comme opérations disponibles:
-"head" c'est à dire la partie VALUE de mon élément
- "tail", c'est à dire l'élément pointé par l'adresse NEXT de mon élément courant (lui-même indiquant via des NEXT successifs tous les suivants)
- "empty", si je considère un élément qui n'existe pas.

Connaitre l'implémentation de la liste permet entre autres de définir des algorithmes optimisés pour cette implémentation.