При использовании Java / Kotlin для программирования рекомендуется использовать рекурсию хвоста или итерационную версию? Есть ли разница в производительности?

Я пытаюсь узнать о хороших практиках в программировании, и я застрял в этом вопросе. Я знаю, что в Java рекурсивные функции могут быть «болью в заднице» (иногда), и я стараюсь реализовать столько, сколько я могу использовать для хвостовой версии этой функции. Стоит ли беспокоиться об этом или делать это по-старому? Есть ли разница между этими двумя функциями (в Котлине):

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 } 

    Самое большое различие, которое я вижу, это подписи: while iterative_fibonacci принимает один аргумент и довольно ясен, tail_fibonacci занимает три, и хотя предусмотрены значения по умолчанию, это может удивить пользователя. Вы можете, однако, создать для него функцию обертки и даже сделать функцию tailrec локальной .

    Не должно быть большой разницы в результирующем байт-коде, с которым скомпилированы две функции, за исключением n.minus(BigInteger.ONE) vs count += BigInteger.ONE , и вы можете проверить его самостоятельно с помощью программы просмотра n.minus(BigInteger.ONE) Kotlin .

    Что касается производительности, не должно быть предсказуемой разницы между двумя реализациями (также обратите внимание, что JVM дополнительно оптимизирует код во время выполнения с JIT-компилятором), но, конечно, функция tailrec намного эффективнее обычной рекурсивной.

    Что касается стиля кода (который основан на высокой оценке), многие решения с хвостом-рекурсией выглядят более естественными (и ближе к математической нотации), а некоторые нет (например, когда есть много параметров, которые заканчиваются полным беспорядком).

    Итак, я думаю, tailrec следует использовать как инструмент производительности (и особенно как способ избежать переполнения стека, который требует, чтобы все рекурсивные вызовы были хвостами), когда вы находите рекурсивное определение, более подходящее для выражения того, что делает код.

    Они эквивалентны с точки зрения производительности. Kotlin будет оптимизировать рекурсию на функции tailrec, что означает, что он идентичен методу, основанному на петле.

    Предпочитаете ли вы, чтобы функциональный или итеративный подход действительно сводился к вашим собственным предпочтениям (и, если применимо, вашей команде), учитывая удобочитаемость, краткость и интуитивность. Это суждение может меняться от метода к методу; одна функция может быть более читаемой с использованием функционального подхода, где другая может выиграть от простого цикла.

    Хорошая вещь о Kotlin заключается в том, что она поддерживает оба подхода и позволяет разработчику использовать инструмент, который им нужен для работы.

    Intereting Posts