Objectifs d'apprentissage

À la fin de cette section, vous devriez être capable de :

• Définir une fonction récursive pour générer les nombres de Fibonacci.

Suite de Fibonacci à l'aide de la récursivité

La suite de Fibonacci est une suite dans laquelle chaque nombre est la somme des deux nombres précédents de la suite. Les deux premiers nombres sont 0 et 1. Ainsi, en partant de 0 et 1, le troisième nombre est 0 + 1 = 1, et le nombre suivant est 1 + 1 = 2. La suite de nombres est 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... .

La récursivité peut être utilisée pour calculer le n-ième nombre de Fibonacci. Les cas de base sont 0 et 1. Par la suite, le n-ième nombre s'obtient en additionnant le (n - 1)-ième et le (n - 2)-ième nombre. Ainsi, fib(n) = fib(n - 1) + fib(n - 2), ce qui constitue une définition récursive se terminant par les cas de base f(0) = 0 et f(1) = 1.

Pour une récursivité qui effectue plusieurs appels de fonction dans le cas récursif, il est utile de suivre le déroulement de la récursivité. Une structure utilisée pour suivre les appels effectués par une fonction récursive est appelée un arbre de récursivité (recursion tree). L'animation ci-dessous retrace l'arbre de récursivité pour un appel à une fonction récursive calculant le nombre de Fibonacci pour n = 5.

    """ Recursive Fibonacci function """

    def fib(n):
      # Base case
      if n == 0 or n == 1:
        return n
      # Recursive case
      elif n > 1:
        return fib(n - 1) + fib(n - 2)
      # Error case
      else:
        print("Fibonacci numbers begin at 0.")
        return

    # Test code
    print(fib(7))

    13

Plus grand commun diviseur (PGCD)

Le plus grand commun diviseur (GCD) de deux entiers positifs est un entier qui est un diviseur des deux entiers. Ex. : Le PGCD de 6 et 9 est 3 car 3 x 2 = 6 et 3 x 3 = 9.

Le PGCD se trouve facilement à l'aide de la méthode d'Euclide. La méthode d'Euclide soustrait récursivement le plus petit entier du plus grand entier jusqu'à atteindre un cas de base où les entiers sont égaux. Le plus grand commun diviseur est la valeur entière obtenue lorsque le cas de base est atteint.

    """ Find GCD using recursive implementation of Euclid's method """

    def gcd(a, b):
      if a == b: # Base case
        return a
      elif a < b: # Recursive case
        return gcd(a, b - a)
      else:
        return gcd(a - b, a)

    # Test code
    print(gcd(24, 30))

    6