Lors de l'utilisation de Java/Kotlin pour la programmation est recommandé d'utiliser Tail récursion ou la version itérative? Y a-t-il une différence de performance?

Question

J'essaie de connaître les bonnes pratiques en programmation et je suis coincé avec cette question. Je sais qu'en Java, les fonctions récursives peuvent être (parfois) une douleur dans le cul, et j'essaie d'implémenter autant que possible la version queue de cette fonction. Cela vaut-il la peine de le faire ou devrais-je le faire à l'ancienne? Est-il une différence entre ces deux fonctions (en Kotlin):

tailrec fun tail_fibonacci(n : BigInteger, fib1 : BigInteger = BigInteger.ZERO , fib2 : BigInteger = BigInteger.ONE) : 
BigInteger { 
    return when(n){ 
     BigInteger.ZERO -> fib1 
     else -> tail_fibonacci(n.minus(BigInteger.ONE),fib1.plus(fib2),fib1) 
    } 
} 

fun iterative_fibonacci(n: BigInteger) : BigInteger { 
    var count : BigInteger = BigInteger.ONE 
    var a : BigInteger = BigInteger.ZERO 
    var b : BigInteger = BigInteger.ONE 
    var c : BigInteger 
    while(count < n){ 
     count += BigInteger.ONE 
     c = a + b 
     a = b 
     b = c 
    } 
    return b 
} 

Answer 1

La plus grande différence que je vois est les signatures: tandis que iterative_fibonacci prend un argument et est tout à fait clair, tail_fibonacci prend trois, et bien que les valeurs par défaut sont fournies, cela pourrait surprendre l'utilisateur. Vous pouvez, cependant, faire une fonction de wrapper pour cela, et même faire de la tailrec une fonction local one.

Il ne devrait pas beaucoup de différence dans le bytecode résultant les deux fonctions sont compilées à l'exception de n.minus(BigInteger.ONE) vs count += BigInteger.ONE, et vous pouvez le vérifier par vous-même avec a Kotlin bytecode viewer. En ce qui concerne les performances, il ne devrait pas y avoir de différence prévisible entre les deux implémentations (notez aussi que la JVM optimise le code à l'exécution avec le compilateur JIT), mais bien sûr la fonction tailrec est beaucoup plus efficace qu'une récursive ordinaire serait. En ce qui concerne le style de code (fortement basé sur l'opinion), de nombreuses solutions récursives ont une apparence plus naturelle (et plus proche de la notation mathématique), d'autres non (par exemple, lorsque de nombreux paramètres se retrouvent dans un désordre complet). Donc, je pense que tailrec devrait être utilisé comme un outil de performance (et surtout comme un moyen d'éviter le débordement de la pile, qui nécessite que tous les appels récursifs soient ceux de queue) lorsque vous trouvez une définition récursive plus appropriée pour exprimer ce que le code fait.

Answer 2

Ils sont équivalents en termes de performance. Kotlin optimisera la récursivité sur les fonctions tailrec, ce qui signifie qu'elle est identique à une approche basée sur une boucle. Si vous préférez une approche fonctionnelle ou itérative, choisissez celle qui vous convient le mieux (et celle de votre équipe, le cas échéant), en tenant compte de la lisibilité, de la concision et de l'intuitivité. Ce jugement peut changer d'une méthode à l'autre; une fonction pourrait être plus lisible en utilisant une approche fonctionnelle, alors qu'une autre pourrait bénéficier d'une boucle simple. La bonne chose à propos de Kotlin est qu'il supporte les deux approches, et permet à un développeur d'utiliser l'outil dont ils ont besoin pour le travail.