Dans le monde de l'informatique, la récursivité est une méthode selon laquelle la solution d'un problème dépend d'instances plus petites du même problème. Il s'agit d'un processus dans lequel une fonction s'appelle elle-même en tant que sous-programme. Cela permet à la fonction d'être appelée avec moins d'arguments, réduisant ainsi la quantité d'informations d'état qui doivent être conservées par la fonction, et fournissant un moyen très élégant et concis d'exprimer des solutions à certains types de problèmes. La récursivité est souvent considérée comme un concept difficile à appréhender pour les débutants. Cependant, lorsqu'il est bien compris, il peut être un outil extrêmement puissant dans l'arsenal d'un programmeur. Elle permet de créer un code plus propre et plus concis, et peut souvent être utilisée pour résoudre des problèmes complexes à l'aide de solutions simples et élégantes.

Dans cette leçon, nous appliquerons la récursivité à la suite de Fibonacci, qui est une série de nombres où un nombre est l'addition des deux derniers nombres, c'est-à-dire 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, et ainsi de suite. La séquence commence à 0 et le nième nombre est donc la somme des (n-1)ème et (n-2)ème nombres.

Vues récursives dans SmartPy

Dans SmartPy, la récursivité est mise en œuvre en permettant à une fonction de s'appeler elle-même à l'intérieur de sa propre définition. Cette méthode est extrêmement utile lorsqu'il s'agit de problèmes qui peuvent être décomposés en sous-problèmes identiques plus petits. Une vue récursive dans SmartPy est essentiellement une vue qui utilise la récursivité. Une vue est une fonction SmartPy qui ne modifie pas le stockage du contrat mais qui peut lire à partir de celui-ci. Lorsque nous parlons d'une vue récursive, nous entendons une fonction de vue qui s'appelle elle-même au cours de son exécution.

Séquence de Fibonacci

La suite de Fibonacci est un ensemble de nombres où chaque nombre est la somme des deux précédents, en partant de 0 et de 1. Cette séquence, bien que simple, constitue un excellent point de départ pour comprendre la récursivité en raison de sa nature récursive.

La suite de Fibonacci est définie par la relation de récurrence :

SCSS
F(n) = F(n-1) + F(n-2)

Les conditions initiales étant F(0) = 0 et F(1) = 1. Cela signifie que pour obtenir le n-ièmenombre de la suite de Fibonacci, il faut additionner le(n-1)-ième et le(n-2)-ième nombre. C'est précisément cette nature récursive qui fait de la suite de Fibonacci un outil parfait pour comprendre la récursivité. Maintenant que nous avons une meilleure compréhension de la récursivité et de son application à la suite de Fibonacci, plongeons dans le code SmartPy qui implémente une vue récursive pour calculer la suite de Fibonacci.

Guide du code

Le code SmartPy donné définit un contrat, FibonacciView, qui calcule la séquence de Fibonacci à l'aide d'une vue récursive. C'est un excellent exemple pour comprendre comment les fonctions récursives sont créées et utilisées dans SmartPy.

Python
import smartpy as sp


@sp.module
def main() :
 class FibonacciView(sp.Contract) :
      """Contrat avec une vue récursive pour calculer la somme des nombres de Fibonacci."""

        @sp.onchain_view()
 def fibonacci(self, n) :
          """Retourne la somme des nombres de fibonacci jusqu'à n.

            Args :
 n (sp.int) : nombre de nombres de Fibonacci à additionner.
            Retour :
 (sp.int) : la somme des nombres de fibonacci
 " " " 
 sp.cast(n, int)
 if n < 2 :
 return n
 else :
 n1 = sp.view("fibonacci", sp.self_address(), n - 1, int).unwrap_some()
 n2 = sp.view("fibonacci", sp.self_address(), n - 2, int).unwrap_some()
                return n1 + n2


if "templates" not in __name__:

   @sp.add_test(name="FibonacciView basic scenario", is_default=True)
 def basic_scenario() :
 sc = sp.test_scenario(main)
        sc.h1("Scénario de base.")
        sc.h2("Origine.")
        c1 = main.FibonacciView()
 sc += c1
 sc.verify(c1.fibonacci(8) == 21)

Ce contrat FibonacciView possède une fonction de vue récursive, fibonacci, qui renvoie le nième nombre de Fibonacci.

La fonction est décorée avec @sp.onchain_view(), indiquant qu'il s'agit d'une opération en lecture seule sur le stockage du contrat. Cette fonction prend un entier n comme argument, représentant la position dans la séquence de Fibonacci que nous voulons récupérer.

À l'intérieur de la fonction, nous transformons d'abord n en un entier pour plus de sécurité. La partie récursive de la fonction vient ensuite. Si n est inférieur à 2, nous renvoyons simplement n car les deux premiers nombres de la suite de Fibonacci sont 0 et 1. Si n est supérieur ou égal à 2, nous calculons le nième nombre de Fibonacci en appelant récursivement la fonction Fibonacci pour n-1 et n-2, puis en additionnant les résultats. Cela correspond à la relation de récurrence définissant la suite de Fibonacci. Les appels sp.view créent ces appels récursifs à la fonction fibonacci elle-même.

Utiliser une boucle pour plus d'efficacité
Bien que la récursivité soit un concept utile à comprendre, il est important de noter qu'elle peut être moins efficace et nécessiter plus de ressources informatiques, en particulier lorsqu'il s'agit de grands nombres. Pour éviter des problèmes tels que le débordement de pile, une approche plus efficace consisterait à utiliser une boucle pour calculer la séquence de Fibonacci et à stocker les nombres de Fibonacci calculés dans un contrat séparé.
Voici un exemple de haut niveau de la manière dont vous pouvez modifier le contrat FibonacciView pour utiliser une boucle :
Ce contrat modifié, FibonacciCalculator, utilise une boucle pour calculer efficacement les nombres de Fibonacci et les stocker dans la mémoire du contrat. Vous pouvez ensuite appeler le point d'entrée calculate_fibonacci pour récupérer le nième nombre de Fibonacci.
Cette approche est plus économe en ressources et convient pour des valeurs plus importantes de n.

Python
@sp.moduledef main() :
 class FibonacciCalculator(sp.Contract) :
      """Contrat permettant de calculer efficacement la suite de Fibonacci."" " def __init__(self) :
 self.init(storage=sp.map(tkey=sp.TInt, tvalue=sp.TInt).set(0, 0).set(1, 1))

       @sp.entry_pointdef calculate_fibonacci(self, n) :
 sp.verify(n >= 0, message="n doit être non négatif")
 storage = self.data
 for i in range(2, n + 1) :
 next_fib = storage[i - 1] + storage[i - 2]
 storage = storage.set(i, next_fib)
 sp.result(storage[n])

Poursuivons avec la section des tests.

Dans la fonction de test basic_scenario, nous créons une nouvelle instance du contrat FibonacciView, nous l'ajoutons à notre scénario, puis nous utilisons sc.verify pour vérifier que le 8e nombre de Fibonacci est 21, ce qui est vrai pour la séquence de Fibonacci.

Exécuter le code dans l'IDE SmartPy

Pour exécuter le code :

1. Ouvrez l'IDE SmartPy.

2. Copiez et collez le code fourni dans l'éditeur.

3. Cliquez sur le bouton "Exécuter". Vous devriez voir le scénario de test s'exécuter sur le côté droit de l'IDE. Vous verrez les opérations effectuées et les contrôles vérifiés.
   Cette leçon a couvert beaucoup de sujets. Nous avons abordé les bases de la récursivité et son utilisation en programmation, les vues récursives dans SmartPy, et même l'application de ces concepts à la suite de Fibonacci. Nous avons également exploré un exemple de code fonctionnel dans SmartPy, et vous avez appris comment exécuter et vérifier ce code dans l'IDE SmartPy.