J'ai une fonction récursive, comme suit, où b> = 0Combien de fois cette fonction récursive itérée?
def multiply(a,b):
if b == 0:
return 0
elif b % 2 == 0:
return multiply(2*a, b/2)
else:
return a + multiply(a, b-1)
Je voudrais savoir combien de fois la fonction se déroulera en termes de a et b. Merci.
Je peux me tromper ici, mais je pense que votre fonction ne fonctionne pas comme vous le souhaitez. En récursivité, la chose la plus importante en tant que critère de fin de propper, car il courra pour toujours. Maintenant, votre critère de fin est a==0, mais avec chaque appel récursif, vous ne diminuez pas a. Il suffit de faire un stylo & simulation de papier avec a = 5 et vérifier si elle s'arrêterait à tout moment.
Désolé, j'ai réalisé que j'ai fait une faute de frappe dans le cas de base. Je l'ai mis à jour. – alexcons
Vous l'avez compris? – alexcons
Au travail en ce moment, pourrait avoir le temps de jeter un coup d'oeil dans la soirée. Mais je pense que tu peux le faire toi aussi! Essayez d'utiliser une approche algorithmique pour résoudre la récurrence. Cela pourrait être très utile je pense: http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/ –
Si la représentation binaire de b (appelez B) se termine par 1, comme xxxx1 que l'appel suivant à multiplier a B = xxxx0.
Si B se termine par 0, comme xxxx0, la valeur suivante de B est xxxx. Avec cela, le chiffre de la représentation binaire de b ajoute un appel s'il est 0, et deux appels s'il est égal à 1. Sommation du nombre total d'appels égale à length of initial B + number of ones in initial B.
Cette méthode semble brisée. Essayez 'multiply (1, 0)', par exemple, et vous aurez une boucle récursive infinie. – Jesper
Oui, j'ai fait une faute de frappe. C'est corrigé maintenant. – alexcons
Indice: utilisez la représentation binaire de b et vérifiez la valeur utilisée dans l'appel multiple suivant(). – Ante