Je suis nouveau dans le concept de récursion essayant de comprendre comment fonctionne le code suivant

def Max(list):
    if len(list) == 1:
        return list[0]
    else:
        m = Max(list[1:])
        return m if m > list[0] else list[0]

def main():
    list = eval(raw_input(" please enter a list of numbers: "))
    print("the largest number is: ", Max(list))


    main()

J'ai les doutes suivants en regardant le code

1) Comment le découpage fonctionne ici sans donner à la découpe où elle devrait se terminer [0: 9] (de cette manière, comment la liste est découpée)

2) Quand l'instruction ** return m if m> list [0] else list [0] ** sera-t-elle appelée (je pense qu'elle ne sera pas appelée car avant le retour, nous appellerons la fonction plusieurs fois)

3
mdvenkatesh nuhk 10 mars 2019 à 18:07

2 réponses

Meilleure réponse

Bienvenue dans la récursivité - c'est difficile à comprendre, mais il y a une étrange sorte d'élégance/beauté.

Cela m'aide généralement à réfléchir à cela avec un exemple.

Supposons cette liste : 1, 2, 3

Nous allons exécuter Max([1,2,3])

  1. La longueur de la liste est de 3, nous passons donc à la partie else
  2. Nous exécutons Max([2,3]) et sauvegardons le résultat dans m (Récursion #1)
    1. La longueur de [2,3] est != 0, on passe à else
    2. Nous exécutons Max([3]) et sauvegardons le résultat dans m (Récursion #2)
      1. La longueur de [3] est == 1
      2. Nous retournons l'index 0, qui est 3 (Fin de récursion #2)
    3. Nous obtenons une valeur de 3 pour m
    4. Nous arrivons maintenant à l'énoncé return m if m > list[0] else list[0]
    5. Récapitulatif : m = 3 et list=[2,3]
    6. m > list[0] donc on retourne m=3 (Fin de récursion #1)
  3. Récapitulez à nouveau : m=3 et list=[1,2,3]
  4. m > list[0] donc on retourne m=3

Le résultat de Max([1,2,3]) est 3.

Notez que chaque appel à Max dans le code crée des variables "nouvelles" pour m et list qui ne sont visibles qu'à l'intérieur de cette fonction. L'intérieur Max ne connaît pas m et list l'extérieur Max et vice versa.

Le flux d'appels ressemble à ceci :

+----------------+
|   Max([1,2,3]  | +----+
+------^---------+      | Step 1
       |                |
Step 4 |       +--------v------+
       +-------+   Max([2,3])  +---+
   return 3    +---^-----------+   | Step 2
                   |               |
           Step 3  |     +---------v-----+
                   +-----+   Max([3])    |
             return 3    +---------------+

À l'adresse 1) :

Lorsque nous découpons en utilisant [n:], cela signifie : commencez à l'index n et prenez le reste de la liste.

À l'adresse 2) :

Une fois que nous sommes sortis de la récursivité, voir l'exemple ci-dessus.


Lectures complémentaires


Modifier en réponse à votre commentaire

Pour vous aider à comprendre la ligne return m if m > list[0] else list[0], je vous suggère d'essayer de garder une trace mentale de l'état avant l'appel récursif et après l'appel récursif.

L'idée de cette implémentation Max est la suivante : allez récursivement au dernier élément de la liste, puis prenez-le et vérifiez-le par rapport à l'avant-dernier élément si le dernier est plus grand, gardez-le, sinon gardez le deuxième- durer.

Si votre liste ressemblait à ceci [1,6,3,5,4,2], les niveaux de récursivité renverraient ceci :

Le premier nombre entre parenthèses est m et le second est la valeur de list[0]

  • 2 (N/A, 2)
  • 4 (2, 4)
  • 5 (4, 5)
  • 5 (5, 3)
  • 6 (5, 6)
  • 6 (6, 1)

En fin de compte, la fonction commence à la fin de la liste, prend la dernière valeur comme valeur initiale et se déplace vers le début, tout en conservant toujours la valeur la plus grande qui renvoie la plus grande valeur.

(C'est difficile à mettre par écrit, j'espère que vous comprendrez)

2
Maurice 10 mars 2019 à 20:10
  1. C'est une façon normale de trancher. [1:] signifie du premier élément jusqu'à la fin.
  2. La fonction est récursive. Donc, si vous avez une liste d'éléments [4,3], il

1) prend deux fois la branche else de l'instruction if, calcule [4,3][1:] comme [3] et appelle Max([3])).

2) La liste de la deuxième étape de la récursivité a une longueur de 1, elle prend donc la première branche de l'instruction if et renvoie 3 comme éléments.

3) nous sommes de retour au premier appel, où nous comparons la première liste d'éléments [0] = 4 avec le résultat m = 3 et obtenons le plus grand d'entre eux comme valeur de retour.

0
Prodiction 10 mars 2019 à 15:20