Devoir sur la récursivité

L'usage de la calculatrice n'est pas autorisé.

Le barème est donné à titre indicatif

Durée : 55 min

Exercice 1 (2 points)

Écrire une fonction récursive qui teste la présence d'un caractère dans une chaîne de caractères.

Corrigé

def recherche(ch,car):
  if ch==[]:
    return False
  else:
    return car==ch[0] or recherche(ch[1:],car)

Exercice 2 (2 points)

Représenter ce qui s'affiche sur la fenêtre graphique à l'exécution du code suivant :

from turtle import *
def dessine(n):
    if n>0:
        forward(n)
        left(45)
        dessine(n-5)
dessine(100)

Corrigé

Exercice 3 (3 points)

Écrire deux fonctions récursives imbriquées, pair(n:int)->bool et impair(n:int)->bool de sorte qu'elles soient définies l'une par rapport à l'autre de manière récursive:

• pair(n) est vrai si impair(n-1) est vrai

• impair(n) est vrai si pair(n-1) est vrai

• pair(0) est vrai

• impair(1) est vrai

Corrigé

def pair(n):
  if n<=1:
    return n==0:
  else:
    return impair(n-1)

def impair(n):
  if n<=1:
    return n==1
  else:
    return pair(n-1)

Exercice 4 (3 points)

Écrire un programme récursif permettant de décomposer un entier \(N\) en facteurs premiers. (Exemple : \(432 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 \times 3\)).

Corrigé

def fp(N,d,ch):
  if N==1:
      return ch
  else:
      if N%d==0:
          return ch+'*'+ str(d)+fp(N/d,d,ch)
      else:
          return ch+fp(N,d+1,ch)
print(fp(12,2,''))

Une autre version, avec des listes...

def decomp(N):
if N==1:
    return []
else:
    d=2
    while N%d!=0:
        d=d+1
    return [d]+decomp(N//d)

Exercice 5 (3 points)

À l'aide du module turtle, donne une fonction récursive qui permettrait de dessiner la figure suivante:

Corrigé

def gradu(n,l):
  if n==0:
    forward(l)
  else:
    gradu(n-1,l/2)
    left(90)
    forward(l/4)
    backward(l/4)
    right(90)
    gradu(n-1,l/2)