Une fonction récursive est une fonction qui s'appelle elle-même dans la fonction. Par exemple, le code suivant est une fonction récursive.
def hello
puts 'hello!'
hello
end
hello
Dans la fonction appelée hello, la fonction hello est appelée à nouveau après avoir sorti la chaîne de caractères «bonjour!». À propos, lorsque j'exécute le code ci-dessus, la chaîne «bonjour!» Est affichée tout le temps. (S'il s'agit de ruby, il se terminera de force par "Erreur de pile système")
Le code ci-dessus atteint le but en créant simplement une fonction récursive, mais comme une fonction récursive qui produit une chaîne de caractères n'est pas intéressante, prenons le «calcul d'échelle» comme un problème de base d'implémentation d'une fonction récursive. J'ai écrit le code pour calculer la puissance de n. Tout d'abord, implémentons-le sans utiliser de fonction récursive.
res = 1
while n > 0
res *= n
n -= 1
end
puts res
Est-ce que c'est comme ça?
De plus, ruby a une méthode pratique appelée méthode times, donc si vous l'utilisez, ce sera comme suit.
res = 1
n.times do |i|
res *= (i + 1)
end
puts res
Dans les deux cas, la puissance peut être calculée en passant un nombre naturel à «n». Implémentons cela avec une fonction récursive. Le code ressemble à ceci:
def factorial(n)
if n == 0
1
else
n * factorial(n - 1)
end
end
Si vous passez un nombre naturel à la fonction «factorielle», le programme renverra le résultat de la multiplication.
Si vous n'y êtes pas habitué, il est difficile de comprendre de quel type de flux de traitement il s'agit, alors suivons le traitement en utilisant le cas de n = 3 comme exemple.
Si vous passez n = 3 comme argument à factional, le bloc if-else évalue n et se branche. Puisque «n = 3», le traitement de «else» s'exécute et «3 * factional (2)» est renvoyé.
Cependant, comme nous appelons la fonction factional sur la valeur de retour, le processus s'exécute également ici et le résultat est retourné. factional (2) renvoie 2 * factional (1).
De même, factional (1) renvoie1 * factional (0).
Ici, factional (0) retournera 1 en fonction de la condition du bloc if-else.
En conséquence, factional (3) retournera 3 * 2 * 1 * 1, et vous obtiendrez la réponse que vous voulez, 3! = 6.
Lors de la création d'une fonction récursive, ** une condition pour terminer le processus ** est requise. Une telle condition est appelée un ** cas de base **. Si le cas de base n'est pas défini, la fonction récursive se terminera dans une boucle infinie. Un cas de base est essentiel pour éviter les boucles infinies. Dans ce code de calcul de multiplication, le cas "n = 0" est le cas de base. Il est également important de créer un processus qui vous permettra d'atteindre le ** scénario de base. ** Même si vous préparez un cas de base, si vous n'atteignez pas le cas de base, le processus ne se terminera pas. Par exemple, le code suivant entraînera une boucle infinie.
def factorial(n)
if n == 0.5
1
else
n * factorial(n - 1)
end
end
La condition de «if» est un point décimal. Puisque n est un nombre naturel, il n'y a pas de cas où n est une fraction. Dans un tel exemple, le cas de base ne peut pas être atteint.
Etre capable d'écrire un traitement en boucle avec des fonctions récursives élargit la gamme de programmation. En outre, l'idée de fonctions récursives est importante (apparemment, toujours à l'étude) lors de la mise en œuvre d'algorithmes tels que la recherche de priorité en profondeur. Dans un exemple simple comme ce calcul de multiplication, il semble plus facile de comprendre s'il est implémenté dans une boucle normale, mais lors de l'implémentation d'un algorithme tel que la recherche de priorité de profondeur, il est simple d'utiliser une fonction récursive. Je pense qu'il peut être implémenté avec un code simple.
qiita: Quel genre de monde se développera lorsque vous apprendrez les fonctions récursives
Recommended Posts