GCD récursif ne renvoyant pas les résultats attendus

Question

Cette fonction en Python consiste à trouver récursivement le plus grand commun diviseur de 2 entiers. Mais je n'étais pas capable de le faire fonctionner comme il se doit dans le test

def gcdRecur(a, b): 
    if a > b: 
     (a,b) = (b,a) 
    if b%a == 0: 
     #print("b%a == 0") 
     print ("a is " + str(a)) 
     return a 
    else: 
     gcdRecur(b%a,b) 



print("gcdRecur(45, 42) " + "should be 3, and we got " + str(gcdRecur(45, 42))) 
print("gcdRecur(6, 12) " + "should be 6, and we got " + str(gcdRecur(6, 12))) 
print("gcdRecur(12, 16) " + "should be 4, and we got " + str(gcdRecur(12, 16))) 
print("gcdRecur(17, 12) " + "should be 1, and we got " + str(gcdRecur(17,12))) 

Answer 1

comme mon commentaire dit. Il vous manque un return dans votre instruction else.

else: 
    return gcdRecur(b%a,b) 

Vous avez besoin de l'instruction return ici car vous devez chaîner le retour de votre récursif. En utilisant la fonction Sven Marnach qui peut être trouvé ici: https://stackoverflow.com/a/5537507/4099813

Nous pouvons prendre la fonction de trace Sven a écrit et voir ce qui se passe et pourquoi vous avez besoin de la déclaration de retour. (Nous avons besoin de modifier sa fonction pour accepter plusieurs arguments:

def trace(f): 
    indent = 0 
    def g(*x): 
     nonlocal indent 
     print('| ' * indent + '|--', f.__name__, x) 
     indent += 1 
     value = f(*x) 
     print('| ' * indent + '|--', 'return', repr(value)) 
     indent -= 1 
     return value 
    return g 

def gcdRecur(a, b): 
if a > b: 
    (a,b) = (b,a) 
if b%a == 0: 
    return a 
else: 
    gcdRecur(b%a,b) 

gcdRecur = trace(gcdRecur) 

gcdRecur(45,42) 

qui, lorsqu'il a couru, il nous donne:

|-- gcdRecur (45, 42) 
| |-- gcdRecur (3, 45) 
| | |-- return 3 
| |-- return None 

avis qu'il est de retour Aucun parce que vous n'avez pas dit qu'il doit retourner la valeur qu'il trouve dans le prochain niveau de récursivité

Ajout du return à la déclaration else va céder:

|-- gcdRecur (45, 42) 
| |-- gcdRecur (3, 45) 
| | |-- return 3 
| |-- return 3