Comprendre la récursion en Python avec if case

Question

En résolvant cette codewars challenge je suis tombé sur un exemple de récurrence que je ne comprends pas.

Le défi consiste à donner les nième nombres suivants, en supposant une séquence initiale de 3 nombres de germes, où les nième nombres sont déterminés en ajoutant les trois derniers chiffres de la séquence.

Ainsi, pour la liste de séquences de semences de [1,2,3] et étant donné n = 5, on pourrait renvoyer le suivant:

1 + 2 + 3 = 6
2 + 3 + 6 = 11

réponse:
[1, 2, 3, 6, 11]

je résolu le problème de ce qui suit:

def tribonacci(sequence,n): 
if n <=3: 
    return sequence[:n] 
else: 
    for i in range(n-3): 
     sequence.append(sum(signature[-3:]))   
    return sequence 

En examinant les autres solutions, je suis tombé sur cette solution très élégante qui utilise la récursivité:

def tribonacci(sequence,n): 
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n) 

Ma question est: pourquoi ne pas courir tout à l'infini? J'ai du mal à comprendre pourquoi cela se termine avec la ième itération. Il ne semble pas que la fonction de 'n' soit stipulée n'importe où, sauf dans le cas if.

A titre d'expérience, j'ai modifié le code d'ignorer le moins que ou égal à longueur de séquence cas, comme ceci:

def tribonacci(sequence,n): 
    return tribonacci(sequence + [sum(sequence[-3:])],n) 

Et cela ne fonctionne infiniment et les erreurs sur avec une erreur d'exécution de profondeur de récursivité max.

Donc, évidemment, l'option case est ce qui semble contrôler la terminaison, mais je ne vois pas pourquoi. J'ai utilisé la récursivité moi-même dans les résolutions (par exemple en créant une fonction d'affacturage), mais dans cet exemple vous soustrayez n-1 pendant que vous itérez donc il y a un processus de terminaison. Je ne vois pas cela se produire ici. Je suppose que je ne comprends pas complètement comment fonctionne la fonction de retour. Je lisais comme:

retour liste n-élément si n est inférieur/égal à la longueur de la séquence

autre

exécuter à nouveau la fonction

Peut-être que je devrais vraiment être en train de lire comme:

retourner la liste n-item si n est inférieur/égal à la longueur de séquence

autre

retour liste n-article après itérer la fonction suffisamment de fois pour remplir un n-article Liste

Answer 1

A chaque niveau de récursivité, la séquence devient plus à cause de concaténation (+). Finalement, il deviendra assez long pour que n devienne inférieur à la longueur.

Answer 2

Vous pouvez réécrire ceci:

a = b if p else c 

comme ceci:

if p: 
    a = b 
else: 
    a = c 

Sachant que, vous pouvez voir que ceci:

def tribonacci(sequence,n): 
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n) 

est le même que:

def tribonacci(sequence,n): 
    if n <= len(sequence): 
     return sequence[:n] 
    else: 
     return tribonacci(sequence + [sum(sequence[-3:])],n) 

Maintenant, vous devriez être en mesure de voir qu'il y a une condition contrôlant que la récursion ne dure pas éternellement.