Comment créer une fonction récursive

Difficile de faire une fonction récursive

Il est difficile de créer une fonction récursive, n'est-ce pas? Il existe de nombreux articles de commentaires sur les fonctions récursives, mais il semble qu'il y ait peu d'articles qui expliquent comment créer des fonctions récursives, expliquant uniquement le code des fonctions récursives qui existent déjà. ..

Si vous étudiez l'article sur la création d'une fonction récursive, article en anglais ici montre le déroulement de la création d'une fonction récursive. Je l'ai expliqué d'une manière facile à comprendre. J'ai essayé de traduire le contenu de l'article en anglais par moi-même, alors j'aimerais le partager.

1. Qu'est-ce qu'une fonction récursive?

En un mot, une fonction qui contient son propre appel. Pour plus de détails, veuillez vous référer à d'autres articles.

2. Deux fonctions qui composent une fonction récursive

Tout d'abord, comprenons les fonctions qui composent une fonction récursive. Deux fonctions sont nécessaires pour construire une fonction récursive:

  1. ** Fonction d'arrêt **: partie de sa propre fonction
  2. ** Fonction récursive **: La partie où la fonction s'appelle elle-même

Par exemple, considérons une fonction récursive qui inverse une chaîne. Divisons-le en deux fonctions ci-dessus:

def reverse_string(str1):
    #Fonction d'arrêt
    if len(str1)<2:
        return str1

    #Fonction récursive
    return reverse_string(str1[1:])+str1[0]

Je pense qu'il est relativement facile de convertir la partie de la fonction d'arrêt en code. D'un autre côté, ** il peut être difficile de convertir des fonctionnalités récursives en code **. Par conséquent, je vais expliquer le flux de conversion de cette fonction récursive en code.

3. Flux de conversion des fonctions récursives en code

Convertissez la fonctionnalité récursive en code avec le flux suivant:

  1. Déterminez le problème à résoudre </ font> avec une fonction récursive.
  2. Considérez le problème simple en une étape </ font> de résolution du problème </ font>.
  3. Un problème simple en une étape </ font> peut être résolu par la fonction que je vais créer ** je crois de tout mon cœur **! À partir de la version 4.3, vous pouvez résoudre le problème simple en une étape </ font> (je crois de tout mon cœur). Soit la solution sol1.
  4. Utilisez sol1 pour exprimer la solution (appelons-le sol) du problème à résoudre </ font>.

Si résolution du problème </ font> est un problème lié à n problèmes, problème simple en une étape </ font> est une image d'un problème lié à n-1 problèmes. .. Je montrerai concrètement le sens de l'explication du préambule avec l'exemple du chapitre 5.

4. Flux pour créer une fonction récursive

Au chapitre 3, nous avons créé un flux qui convertit les fonctions récursives en code. Maintenant, résumons les flux qui composent la fonction récursive.

  1. Créer un nom de fonction récursive
  2. Convertissez la fonction d'arrêt en code
  3. Convertissez la fonctionnalité récursive en code
  4. Déterminez le problème à résoudre </ font> avec une fonction récursive.
  5. Considérez le problème simple en une étape </ font> de résolution du problème </ font>.
  6. Un problème simple en une étape </ font> peut être résolu par la fonction que je vais créer ** je crois de tout mon cœur **! Appelons la fonction fun.
  7. Vous pouvez résoudre le problème simple en une étape </ font> en s'amusant. Soit la solution sol1.
  8. Utilisez sol1 pour exprimer la solution (appelons-le sol) du problème à résoudre </ font>.

5. Exemple

Créons une fonction récursive qui résout l'exemple suivant selon le flux du chapitre 3.

** Problème: inversez la chaîne de caractères. (Ex: abc → cba) **

Soit str1 la chaîne de caractères que vous souhaitez inverser. (Codé en Python.)

  1. Soit le nom de la fonction récursive chaîne_inverse:

    def reverse_string(str1):
    
  2. Convertissez la fonction d'arrêt en code:

    def reverse_string(str1):
        #Fonction d'arrêt
        #Si la longueur de la chaîne de caractères est 1, elle sort de la fonction.
        if len(str1)<2:
            return str1
    
  3. Convertissez la fonctionnalité récursive en code

  4. Problème à résoudre </ font>: Inversez la chaîne str1

  5. Problème simple en une étape </ font>: Inverse "une chaîne de caractères dans laquelle le premier caractère est supprimé de la chaîne de caractères" (cela s'appelle str1_rem). Ici, exprimons str1_rem dans le code:

    ```python
    def reverse_string(str1):
        #Fonction d'arrêt
        #Si la longueur de la chaîne de caractères est 1, elle sort de la fonction.
        if len(str1)<2:
            return str1
    
        #Supprimer le premier caractère de la chaîne str1
        str1_rem=str1[1:]
    ```
    
  6. Un problème simple en une étape </ font> peut être résolu par votre propre fonction (reverse_string) ** Je crois de tout mon cœur **!

  7. La solution obtenue par la fonction reverse_string pour problème simple en une étape </ font> est sol1 (je crois de tout mon cœur). Autrement dit, sol1 = reverse_string ("une chaîne obtenue en soustrayant le premier caractère de la chaîne") (je crois de tout mon cœur):

    ```python
    def reverse_string(str1):
        #Fonction d'arrêt
        #Si la longueur de la chaîne de caractères est 1, elle sort de la fonction.
        if len(str1)<2:
            return str1
    
        #Supprimer le premier caractère de la chaîne str1
        str1_rem=str1[1:]
    
        #reverse_la chaîne est str1_Je crois de tout mon cœur que je peux faire marche arrière avant.
        sol1=reverse_string(str1_rem)
    ```
    
  8. À partir de sol1, exprimez la solution (sol) du problème de résolution </ font>. Si "le premier caractère de la chaîne de caractères" est ajouté après sol1, il devient sol. Mathématiquement, sol = sol1 + "le premier caractère de la chaîne de caractères":

    ```python
    def reverse_string(str1):
        #Fonction d'arrêt
        #Si la longueur de la chaîne de caractères est 1, elle sort de la fonction.
        if len(str1)<2:
            return str1
    
        #Supprimer le premier caractère de la chaîne str1
        str1_rem=str1[1:]
    
        #sol1 est str1_Je crois de tout mon cœur qu'il s'agit d'une chaîne de caractères inversée avant.
        sol1=reverse_string(str1_rem)
    
        #Express sol de sol1
        sol=sol1+str1[0]
        
        return sol
    ```
    

** Curieusement, cela crée une fonction récursive **! ..

Si vous raccourcissez le code ci-dessus,

def reverse_string(str1):
    if len(str1)<2:
        return str1
    return reverse_string(str1[1:])+str1[0]

Il devient.

6. Impressions

Si l'article japonais est difficile à comprendre, les détails sont souvent écrits dans l'article anglais. Avant de vous y habituer, il est recommandé d'écrire le flux ci-dessus avant de coder. Dans un premier temps, pratiquons avec un exemple simple. Par exemple, le problème de l'affichage de tous les éléments d'un tableau.

Merci

Nous remercions ceux qui ont commenté et ceux qui l'ont corrigé.

Recommended Posts