Bonjour Dut,
Je ne suis pas sûre que ma réponse t’aide vraiment car pour faire une récurrence en programmation, il faudrait savoir les fonctions que tu utilises dans ce domaine, ce qui n’est pas le cas.
Je t’indique quelques idées éventuelles…
Tout d’abord , en mathématiques, pour une récurrence simple.
Soit P une propriété dépendant d’un naturel n.
On veut prouver par récurrence que P est vraie pour tout n de N
a) On commence par prouver que P est vraie pour n=0, c’est à dire que P(0) est vraie : c’est l’initialisation
b) On suppose que P est vraie pour une valeur n de N, c’est à dire que P(n) est vraie.
Avec cette hypothèse, on démontre que P est vraie pour la valeur n+1, c’est à dire que P(n+1) est vraie : c’est la transmission ( on dit aussi hérédité)
On peut ainsi conclure que P(n) est vraie pour tout n de N.
Pour répondre à ta première question.
Il faut prouver par récurrence , pour toute liste L , que L . [ ]=L (j'ai noté . la concaténation ; j'ignore comme elle est indiquée dans ton cours)
Initialisation pour L=[ ][\ ][ ] (liste de longueur nulle)
[ ][\ ][ ].[ ].[\ ].[ ]=[ ][\ ][ ] est vraie. c’est trivial.
Transmission
Une explication possible mais j’ignore totalement si elle s’adapte à ton cours de programmation.
Pour passer d’une liste de longueur n à une liste de longueur n+1, j’ai vu , en consultant cette notion sur le web,qu' il y a une fonction cons (abrévation de « consécutif » je suppose ) qui permet d’ajouter une élément à gauche d’une liste.
Exemple : cons(3,[7 8 9])=[3 7 8 9]
J’utilise cette fonction cons pour la transmission.
On suppose que pour une liste de longueur n : L . [ ]=L
Soit L’ la liste cons(a, L) obtenue en ajoutant l’élément a à gauche de la liste L (L’ est donc composé de n+1 éléments)
Il faut prouver que L '. [ ]=L’
Pour cela :
L’ . [ ]=cons(a , L) . [ ]
Vu que a est à gauche de L, lui même suivi de [ ], on peut écrire
L’ . [ ]=cons(a , L . [ ])
Vu que par hypothèse de la récurrence L . [ ]=L , on peut écrire
L’. [ ]=cons(a , L)
Vu que cons(a , L)=L’, on peut tirer la conclusion
L’. [ ]=L’
(ce qu’il fallait démontrer)
J’ignore si cette fonction cons fait partie de ton cours...je n’ai pas trouvé mieux.
Tu peux faire une raisonnement de même type pour ta seconde question.
Bonne lecture !