Les personnes ayant de l'expérience en programmation doivent être familiarisées avec les fonctions récursives. Nous utilisons souvent la récursivité pour résoudre une série de problèmes complexes. Les algorithmes récursifs sont très efficaces pour la plupart des problèmes, et ils peuvent également optimiser notre code. lors de l'utilisation de la récursivité :
1) La récursion appelle la fonction elle-même dans la fonction elle-même.
2) L'efficacité de la récursivité est relativement faible et il n'est pas recommandé de l'utiliser s'il y a une limite de temps.
3) Il doit y avoir une condition de fin claire dans le processus récursif, c'est-à-dire la sortie récursive.
Expliquons les fonctions récursives en détail ci-dessous.
Voyons d'abord l'utilisation simple de la récursivité à travers un exemple :
m=int(input('Entrez un nombre :'))deftest(x):x+=2ifx<100:test(x)else:print('Le dernier x est :',x)test(m)Le résultat est :
Entrez un nombre : 20 et le dernier x est : 100
Analysons cet exemple. Tout d'abord, dans la première ligne de code, nous saisissons un entier. Dans la dernière ligne, m est passé comme paramètre réel à la méthode test(). Dans la méthode test(), x sera ajouté par. 2 d'abord, puis Un jugement, si la valeur de x est inférieure à 100, puis appelez à nouveau cette fonction. Lors de l'appel, la valeur actuelle de x est utilisée comme paramètre réel pour participer à l'appel. =100 est satisfait.
Regardez le schéma ci-dessous :
Autrement dit, si les conditions ne sont pas remplies, il retourne à la couche la plus externe et appelle cette fonction.
Lorsqu'on parle de problèmes classiques des algorithmes récursifs, la séquence de Fibonacci et la Tour de Hanoï sont toujours indissociables. Nous allons expliquer ici comment utiliser la récursivité pour résoudre la séquence de Fibonacci.
Tout d’abord, nous devons savoir que la formule récursive de la séquence de Fibonacci est F(n)=F(n-1)+F(n-2), F(1) et F(2) valent 1. Nous peut utiliser la récursion pour trouver la valeur d'un élément dans la séquence de Fibonacci.
Il existe de nombreuses façons de résoudre les problèmes de séquence de Fibonacci.
Nous utilisons d’abord la méthode récursive couramment utilisée pour résoudre ce problème :
N=int(input(saisir le nombre d'éléments à obtenir :))deffibonacci(n):ifn<=2:#S'il est inférieur ou égal à 2, mettre n à 1 return1else:returnfibonacci(n-1) +fibonacci(n-2)print ("La valeur correspondante est",fibonacci(n))Le résultat est :
Saisissez le nombre d'articles que vous souhaitez obtenir : 4 correspond à 3
Pour cette méthode d'appel récursive, lorsque l'on entre la valeur 4, les opérations suivantes seront effectuées de manière récursive :
fibonacci(3)+fibonacci(2)=fibonacci(2)+fibonacci(1)+fibonacci(2)
On voit alors que la valeur du quatrième terme est 1+1+1=3.
En fait, cette méthode de résolution est une perte de temps car trop d’itérations sont nécessaires. Nous pouvons également utiliser l’espace au lieu du temps pour résoudre ce problème.
Le code est le suivant :
n=int(input(saisissez le nombre de termes à obtenir :))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print (' La valeur correspondante est',fibonacci[n-1])Le résultat est :
Saisissez le nombre d'articles que vous souhaitez obtenir : 4 correspond à 3
De cette façon, nous spécifions d'abord les valeurs des deux premiers éléments de la liste, puis pour le nombre n d'éléments que nous voulons résoudre, nous remplissons directement la liste des nombres de Fibonacci jusqu'à l'élément dont nous avons besoin via la formule, et enfin selon l'index La valeur trouve directement le résultat de sortie correspondant.
C'est tout pour la fonction récursive. Comme mentionné ci-dessus, nous devons accorder une attention particulière à la sortie récursive et aux délais. Dans de nombreux cas, notre utilisation de méthodes récursives entraînera le programme. dépasser le temps spécifié, à ce moment-là, nous devons changer notre façon de penser pour résoudre le problème. La deuxième méthode mentionnée ci-dessus peut aider tout le monde à résoudre le problème.